ทฤษฎีกราฟ - ต้นไม้

ต้นไม้คือกราฟที่ไม่มีแม้แต่รอบเดียว แสดงโครงสร้างลำดับชั้นในรูปแบบกราฟิก ต้นไม้อยู่ในคลาสที่ง่ายที่สุดของกราฟ แม้จะมีความเรียบง่าย แต่ก็มีโครงสร้างที่หลากหลาย

ต้นไม้มีแอปพลิเคชั่นที่มีประโยชน์มากมายไม่ว่าจะเป็นแผนผังครอบครัวไปจนถึงต้นไม้ที่ซับซ้อนในโครงสร้างข้อมูลของวิทยาการคอมพิวเตอร์

ต้นไม้

ก connected acyclic graphเรียกว่าต้นไม้ กล่าวอีกนัยหนึ่งกราฟที่เชื่อมต่อโดยไม่มีรอบจะเรียกว่าต้นไม้

ขอบของต้นไม้เรียกว่า branches. องค์ประกอบของต้นไม้เรียกว่าโหนด เรียกโหนดที่ไม่มีโหนดลูกleaf nodes.

ต้นไม้ที่มีจุดยอด 'n' มีขอบ 'n-1' หากมีขอบมากกว่า 'n-1' อีกหนึ่งขอบที่เห็นได้ชัดควรจะต้องจับคู่กับจุดยอดสองจุดซึ่งนำไปสู่การสร้างวัฏจักร จากนั้นจะกลายเป็นกราฟวัฏจักรซึ่งเป็นการละเมิดกราฟต้นไม้

Example 1

กราฟที่แสดงที่นี่คือต้นไม้เนื่องจากไม่มีรอบและมีการเชื่อมต่อกัน มันมีสี่จุดยอดและสามขอบกล่าวคือสำหรับขอบ 'n' จุดยอด 'n-1' ตามที่กล่าวไว้ในคำจำกัดความ

Note - ต้นไม้ทุกต้นมีจุดยอดอย่างน้อยสองจุดในระดับหนึ่ง

Example 2

ในตัวอย่างข้างต้นจุดยอด 'a' และ 'd' มีระดับหนึ่ง และอีกสองจุดยอด 'b' และ 'c' มีดีกรีสอง เป็นไปได้เพราะหากไม่สร้างวัฏจักรควรมีขอบด้านเดียวอย่างน้อยสองขอบที่ใดก็ได้ในกราฟ มันไม่มีอะไรเลยนอกจากสองขอบที่มีองศาหนึ่ง

ป่าไม้

ก disconnected acyclic graphเรียกว่าป่า กล่าวอีกนัยหนึ่งการรวบรวมต้นไม้ที่ไม่ปะติดปะต่อกันเรียกว่าป่า

Example

กราฟต่อไปนี้ดูเหมือนกราฟย่อยสองกราฟ แต่เป็นกราฟที่ขาดการเชื่อมต่อเพียงเส้นเดียว ไม่มีรอบในกราฟนี้ ดังนั้นเห็นได้ชัดว่ามันเป็นป่า

ต้นไม้ที่ทอดยาว

ให้ G เป็นกราฟที่เชื่อมต่อกันแล้วกราฟย่อย H ของ G เรียกว่าต้นไม้ทอดของ G ถ้า -

• H คือต้นไม้
• H ประกอบด้วยจุดยอดทั้งหมดของ G.

ต้นไม้ที่ทอด T ของกราฟที่ไม่ได้บอกทิศทาง G คือกราฟย่อยที่มีจุดยอดทั้งหมดของ G

Example

ในตัวอย่างข้างต้น G คือกราฟที่เชื่อมต่อและ H คือกราฟย่อยของ G

เห็นได้ชัดว่ากราฟ H ไม่มีรอบมันเป็นต้นไม้ที่มีขอบหกด้านซึ่งน้อยกว่าจำนวนจุดยอดทั้งหมด ดังนั้น H จึงเป็นต้นไม้ Spanning ของ G.

อันดับวงจร

ให้ 'G' เป็นกราฟที่เชื่อมต่อกับ 'n' จุดยอดและขอบ 'm' ต้นไม้ที่ทอด 'T' ของ G มีขอบ (n-1)

ดังนั้นจำนวนขอบที่คุณต้องลบจาก 'G' เพื่อให้ได้ต้นไม้ที่ขยาย = m- (n-1) ซึ่งเรียกว่าอันดับวงจรของ G

สูตรนี้เป็นจริงเพราะในต้นไม้ที่ทอดคุณต้องมีขอบ 'n-1' จากขอบ 'm' คุณต้องคงขอบ 'n – 1' ไว้ในกราฟ

ดังนั้นการลบขอบ 'n – 1' จาก 'm' จะทำให้ขอบถูกลบออกจากกราฟเพื่อให้ได้ต้นไม้ที่ทอดยาวซึ่งไม่ควรสร้างเป็นวัฏจักร

Example

ดูกราฟต่อไปนี้ -

สำหรับกราฟที่ให้ในตัวอย่างข้างต้นคุณมีขอบ m = 7 และจุดยอด n = 5

อันดับวงจรคือ -

G = ม. - (n - 1)

= 7 - (5 - 1)

= 3

Example

ให้ 'G' เป็นกราฟที่เชื่อมต่อกับจุดยอดหกจุดและระดับของจุดยอดแต่ละจุดคือสาม ค้นหาอันดับวงจรของ 'G'

โดยผลรวมของระดับของทฤษฎีบทจุดยอด

n Σ i=1deg (V _i ) = 2 | E |

6 × 3 = 2 | E |

| E | = 9

อันดับวงจร = | E | - (| V | - 1)

= 9 - (6 - 1) = 4

ทฤษฎีบทของ Kirchoff

ทฤษฎีบทของ Kirchoff มีประโยชน์ในการค้นหาจำนวนต้นไม้ที่ทอดยาวซึ่งสามารถสร้างขึ้นจากกราฟที่เชื่อมต่อกัน

Example

เมทริกซ์ 'A' จะถูกเติมเต็มราวกับว่ามีขอบระหว่างจุดยอดสองจุดก็ควรกำหนดเป็น '1' มิฉะนั้น '0'

$$ A = \ begin {vmatrix} 0 & a & b & c & d \\ a & 0 & 1 & 1 & 1 \\ b & 1 & 0 & 0 & 1 \\ c & 1 & 0 & 0 & 1 \\ d & 1 & 1 & 1 & 0 \ end {vmatrix} = \ begin {vmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \ end {vmatrix} $$

โดยใช้ทฤษฎีบทของเคิร์ชอฟควรเปลี่ยนเป็นการแทนที่ค่าแนวทแยงหลักด้วยระดับของจุดยอดและองค์ประกอบอื่น ๆ ทั้งหมดด้วย -1.A

$$ = \ start {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = M $$ $$ M = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = 8 $$ $$ Co \: \: factor \: \: of \: \: m1 \: \: = \ begin {vmatrix } 2 & 0 & -1 \\ 0 & 2 & -1 \\ - 1 & -1 & 3 \ end {vmatrix} $$

ดังนั้นจำนวนต้นไม้ที่ทอด = 8