204512/บรรยาย 5

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

ทบทวน

Graph

เซตของโหนด
เซตของเส้นเชื่อม
ตัวอย่าง
MST1.png

จะกล่าวว่าเส้นเชื่อม (u,v) ติดกับโหนด u และ v
u และ v เป็นจุดปลายของเส้นเชื่อม (u,v)
degree ของโหนดใดๆ คือ จำนวนเส้นเชื่อมที่ติดกับโหนดนี้
path คือ ลำดับของโหนด ที่
สำหรับทุกๆ เรียก เป็นจุดเริ่มต้น , เป็นจุดสิ้นสุด

Thm

ถ้ากราฟ มี m edge ให้ deg(u) แทน degree ของโหนด u

Def

กราฟ G Connected ถ้าทุกๆ โหนด u มี path ไปยังทุกๆ โหนด v

เป็น connected coponent ใน G ตัว ทุกๆ โหนดใน C มี path ไปถึงทุกๆ โหนดใน C และ
ไม่มี path ไปยังโหนด v อื่นๆ ที่
Cycle คือ path ที่มีจุดเริ่มต้นเป็นจุดเดียวกับจุดสิ้นสุด ดังรูป MST2.png
Def. tree คือ กราฟที่ Connected และไม่มี Cycle
Thm. ข้อความข้างล่างนี้ให้ G มี n node

1) G Connected
2) G ไม่มี Cycle
3) G มีเส้นเชื่อม n-1 เส้น
2 ข้อใดๆ จะ imply ข้อที่ 3 และ imply ว่า G เป็น tree

Proof (1,2-->3)

(I) ถ้า G Connected,G จะต้องมีอย่างน้อย n-1 edge
(II) ถ้า G มี edge G มี Cycle
เพราะฉะนั้น G ไม่มี Cycle , G มี edge

Spanning tree

MST3.png


ปัญหา minimum spanning tree

MST4.png


Greedy framework


Invariant

MST5.png


Blue Rule และ Red Rule

MST6.png
MST7.png
MST8.png
MST9.png
MST10.png


Blue Forest

MST11.png


Buruvka

MST12.png
MST13.png
MST14.png


Prim's Algorithm

MST15.png


Kruskal's Alogorithm

MST16.png
MST17.png
MST18.png
MST19.png
MST20.png


Path Compress
MST21.png
MST22.png