204512/บรรยาย 5

ทบทวน

Graph

เซตของโหนด $V$
เซตของเส้นเชื่อม $E\subseteq VxV$
ตัวอย่าง

จะกล่าวว่าเส้นเชื่อม (u,v) ติดกับโหนด u และ v

u และ v เป็นจุดปลายของเส้นเชื่อม (u,v)

degree ของโหนดใดๆ คือ จำนวนเส้นเชื่อมที่ติดกับโหนดนี้

path คือ ลำดับของโหนด $V_{1},V_{2},....,V_{k}$ ที่

$(V_{i},V_{i+1})\in E$ สำหรับทุกๆ $1\leq i\leq k$ เรียก $V_{1}$ เป็นจุดเริ่มต้น ,$V_{k}$ เป็นจุดสิ้นสุด

Thm

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

$\sum _{u\in v}deg(u)=2m$

Spanning tree

ปัญหา minimum spanning tree

Invariant

Blue Rule และ Red Rule

Blue Forest

Buruvka

Prim's Algorithm

Kruskal's Alogorithm

Path Compress