Recap :
Subgraph (กราฟย่อย) : ถ้า \( G_1 \) เป็น subgraph ของ \(G\) แล้ว นั่นคือ ทุก vertices ใน \(G_1 \) ต้องอยู่ใน \(G\) และ ทุก edges ใน \(G_1 \) ต้องอยู่ใน \(G\)
 |
| รูปที่ 1 graph A เป็น subgraph ของ graph B |
Undirected graph คือ graph ที่ edges ที่ไม่ได้บอกถึงทิศทาง
Connected graph คือ graph ที่มีเส้นทางจาก vertice ใดๆ ไปยัง vertices อื่นที่เหลือได้เสมอ
 |
| รูปที่ 2 ตัวอย่าง connected graph |
ข้อสังเกตุ connected graph ไม่จำเป็นต้องมี edge เชื่อมระหว่าง vertices ทุกคู่
Spanning Tree
Spanning tree ได้นำคุณสมบัติทั้ง 4 เรื่องที่กล่าวไว้ใน recap มาใช้ นั่นคือ เป็น supgraph ของ undirected graph ที่เป็น connected graph และไม่มี cyclic graph ที่เพิ่มเติมเข้ามาคือ จำนวน edges ใน spanning tree จะต้องมีจำนวนน้อยที่สุด หากเป็น weighted graph ก็ต้องได้ผลรวมของ weight น้อยที่สุด
 |
| รูปที่ 3 จาก normal (ซ้าย) กับ subgraph ที่เป็นไปได้บางส่วน (ขวา) |
จากรูปที่ 3 ขวามือแสดง subgraph ที่เป็นไปได้บางส่วน ถ้าพิจารณาเฉพาะที่มีอยู่ spanning tree ควรจะเป็น supgraph C หรือ D เพราะมีจำนวนของ edges เพียง 4 ในขณะที่ A เป็น 5 ในขณะที่ B เป็น cyclic graph จึงไม่นำมาพิจารณา โดยหลักการคิดจะเป็นแบบเดียวกันหากใช้ weighted graph
Minimum spanning tree หรือ Minimum weighted spanning tree คือ spanning tree ที่ให้ผลรวามของ weighted edges น้อยที่สุด
 |
| รูปที่ 4 |
ถ้าเปลี่ยน graph ในรูปที่ 3 ให้เป็น weighted graph ตามรูปที่ 4 spanning tree ที่ได้ยังคงเป็นแบบเดิมแต่อาจไม่ใช่ minimum spanning tree ทั้งสอง subgraph ถ้ารวม weight จาก edges จะได้ graph A เป็น 13 ในขณะที่ graph B เป็น 15 ดังนั้น minimum spanning tree คือ subgraph ในรูป A
Prim's Algorithm
Greedy algorithm คือ algorithm ใช้ในการทำ optimization โดยการทำ optimize ในทุกขั้นตอนของการทำงาน
Prim's algorithm เป็น greedy algorithm ที่ใช้หา minimum spanning tree ของ weighted undirected graph ตัวอย่างขั้นตอนการทำงานแสดงได้ดังนี้
1. สมมุติว่า graph ที่ต้องการหา minimum spanning tree เป็นดังนี้ เลือก vertice ที่เป็นจุดเริ่มต้น (เลือก vertice ใดก็ได้) สมมุติว่าเลือก vertice A
2. ที่ vertice A เลือกเส้นทางไปยัง adjacent vertice ที่มี weight น้อยที่สุด (optimization) นั่นคือเส้นทางไปยัง vertice C
3. ที่ vertice C เลือกเส้นทางไปยัง adjacent vertice ที่มี weight น้อยที่สุด นั่นคือเส้นทางไปยัง vertice D
4. ทำซ้ำไปจนครบทุก vertices ใน graph
5. สุดท้ายจะได้ minimum spanning tree
ในการทำงานอาจทำมากกว่า 1 รอบ โดยเปลี่ยน vertice เริ่มต้นไปในทุกรอบเพื่อจะได้แน่ใจว่าผลลัพธ์ที่ได้เป็น minimum spanning tree จริง
Kruskal's Algorithm
Kuskal's algorithm มีวัตถุประสงค์ใช้งานเหมือนกับ Prim's algorithm ต่างกันที่ขั้นตอนการทำงาน
1. ใช้ graph เดียวกับตัวอย่าง Prim's algorithm เป็น input
2. ทำการเรียง weight ของ edges ทั้งหมด จากน้อยไปมาก
3. เลือกมาทีละ edge จากน้อยไปมาก เพื่อทำการสร้าง graph เริ่มจาก \((C,D) \)
4.เลือก \((ฺB,D) \) เติมเข้าไปใน graph
5.เลือก \((ฺA,C) \) เติมเข้าไปใน graph
*6. เลือก \((ฺA,B) \) เติมเข้าไปใน graph ขอให้สังเกตุว่า graph ที่ได้เป็น cyclic graph ซึ่งผิดนิยามของ spanning tree ดังนั้นต้องยกเลิก edge ระหว่าง \((ฺA,B) \) ทำให้ graph ยังคงรูปเดิม
7. เลือก \((ฺA,D) \) เติมเข้าไปใน graph ทำให้เป็น cyclic graph ดังนั้นต้องยกเลิก edge ระหว่าง \((ฺA,D) \) ทำให้ graph ยังคงรูปเดิม
8. เลือก \((ฺB,E) \) เติมเข้าไปใน graph
9. จะเห็นว่า Output graph ที่ได้ก็มีลักษณะเดียวกับที่ได้จาก Prim's algorithm
ความคิดเห็น
แสดงความคิดเห็น