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$

Def

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

$C\subseteq V$เป็น connected coponent ใน G ตัว ทุกๆ โหนดใน C มี path ไปถึงทุกๆ โหนดใน C และ
ไม่มี path ไปยังโหนด v อื่นๆ ที่ $V\in V-C$
Cycle คือ path ที่มีจุดเริ่มต้นเป็นจุดเดียวกับจุดสิ้นสุด ดังรูป

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 มี $\geq n$ edge G มี Cycle

เพราะฉะนั้น G ไม่มี Cycle , G มี $1\leq n-1$ edge

---

Spanning tree

ให้กราฟ G = (V,E) เรียก tree ว่าเป็น spanning tree ถ้า $E'\subseteq E$

---

ปัญหา minimum spanning tree

ให้กราฟ G = (V,E) พร้อมด้วยฟังก์ชั่นน้ำหนัก w บนเส้นเชื่อม ต้องการหา spanning tree

T ที่ผลรวมของ weight บนเส้นเชื่อมน้อยที่สุด

---

Greedy framework

ทุกๆ เส้นเชื่อมจะมี

• ไม่มีสี(unknow)
• สีน้ำเงิน(accept)
• สีแดง(reject)

---

Invariant

---

Blue Rule และ Red Rule

---

Blue Forest

---

Buruvka

---

Prim's Algorithm

---

Kruskal's Alogorithm

---

Path Compress

---