กราฟประเภท Biconnectivity
Biconnectivity
กราฟจะเรียกว่าเป็น biconnected ถ้าพบว่าเมื่อตัดจุดใดๆออกไปจากกราฟแล้วจุดที่เหลือยังต่อกันอยู่
โดยการตัดจุดไปไม่ทำให้กราฟแตกออกเป็น 2 กราฟ
ประโยชน์ของ biconnected ถูกนำมาใช้ในการวางระบบเครือข่ายที่มีเสถียรภาพ
เพื่อให้แน่ใจว่าเมื่ออุปกรณ์ต่อเชื่อมในเครือข่ายเสียหายไปสักตัว
จะไม่ทำให้เครือข่ายถูกตัดขาดออกจากกัน
และยังคงมีเส้นทางอื่นๆที่สามารถวิ่งถึงกันได้ แม้ว่าจะเป็นทางอ้อมก็ตาม
ถ้ากราฟไม่ได้เป็น biconnected เราจะพบจุดที่เรียกว่าเป็น articulation point (articulation – แปลว่า ชัดเจน ฟังออก) ซึ่งจุดพวกนี้
ถ้าตัดออกไปจะทำให้กราฟถูกแตกออกจากกันเป็นหลายกราฟ ตัวอย่างเช่นกราฟต่อไปนี้
สังเกตว่าหากเราตัดจุด B, A, G, E, F ออกไปจะไม่ทำให้กราฟแตกออกจากกัน
แต่ถ้าตัดจุด C หรือ จุด D
ออกจะทำให้กราฟแตกออกจากกันดังนี้
วิธีการหา articulation point ในกราฟ ทำได้ตามขั้นตอนดังนี้
1.
ท่องไปในกราฟแบบ depth-first search
และใส่หมายเลขลำดับประจำจุดเอาไว้ (เรียกว่า Num(v))
2.
ท่องไปใน depth-first spanning tree
แบบ post-order traversal โดยทำโหนดลูกให้เสร็จก่อนโหนดแม่
การทำในแต่ละโหนด v ให้คำนวณหาค่า Low โดยเปรียบเทียบหาค่าที่น้อยสุดระหว่าง
ค่าต่อไปนี้
a.
ถ้าไม่มี tree edge ไม่มี
back edge ค่า Low ก็คือ Num ของจุด v เอง
b.
ถ้ามี tree edge ให้เปรียบกับค่า
Low ของทุกๆ tree edge เจอค่า Low
ไหนน้อยสุดให้เอาค่านั้น
c.
ถ้ามี back edge ให้เปรียบกับค่า
Num ของ back edge ถ้า Num นั้นน้อยที่สุด ให้เอา Num นั้น
การใส่ค่า Num(v) จะไม่ยากเท่าไรเพราะเป็นเลขลำดับของการเดินไปตามทางแบบ
depth-first search เท่านั้น เช่นจากกราฟข้างต้น ถ้าเดินไปแบบ depth-first
search โดยเริ่มที่จุด A จะได้เลข Num(v)
ประจำแต่ละจุด v ดังนี้
สำหรับการหาค่า Low(v) เราจะเดินเข้าไปใน
depth-first spanning tree แบบ post-order traversal และค่อยๆกำหนดค่า Low ให้กับโหนดลูกก่อนเสมอ
เมื่อเริ่มเดินเข้าไปแบบ post-order โหนดแรกที่จะถูกทำงานคือ
F ดังนี้
สังเกตว่าโหนด F ไม่มี tree
edge มีแต่ back edge และ back edge มีค่า Num เป็น 4 ซึ่งต่ำกว่า Num
ของตัวมันเอง ดังนั้นค่า Low ของ F ต้องเป็น 4
ถอยกลับขึ้นมาที่ E จะเปรียบเทียบดังนี้
สังเกตว่า E มี tree
edge ชี้มาที่ F ดังนั้นเมื่อเปรียบเทียบ Num
ของ E กับ Low ของ F
ปรากฏว่า Low ของ F มีค่าน้อยกว่า
ดังนั้นเราต้องเลือกค่า Low เป็น 4 ตามค่า
Low ของ F
ถอยกลับขึ้นมาที่ D และเปรียบเทียบหาค่า
Low เป็นดังนี้
สังเกตว่า D มีทั้งเส้น tree
edge และ back edge
o
กรณี tree edge เมื่อเปรียบ Num ของ D กับ Low
ของ E ปรากฏเท่ากันคือ 4
o
กรณี back edge เมื่อเปรียบ Num ของ D กับ Num
ของ A ปรากฏว่า A น้อยกว่าคือ
1 ดังนั้นต้องเลือกค่า 1
เราจะได้ Low ของ D คือ 1
ถอยกลับขึ้นมาที่ C และลงไปที่
G เราคำนวณค่า Low ของ G ดังนี้
โหนด G ไม่มี tree
edge และไม่มี back edge ดังนั้นที่น้อยที่สุดคือ
Num ของตัวมันเอง คือค่า 7
ถอยกลับมาที่โหนด C และเปรียบเทียบดังนี้
โหนด C มี tree edge
2 เส้น เมื่อเทียบแล้วพบว่า Low ของ D คือ 1 เป็นค่าน้อยสุด
ถอยกลับมาที่โหนด B และเปรียบเทียบหาค่า
Low ดังนี้
ถอยกลับมาที่ A จะคำนวณค่า Low
ได้ดังนี้
สุดท้ายเมื่อได้ค่า Num และ Low
ครบทุกจุดแล้ว เราสามารถตรวจสอบได้ว่าจุดไหนเป็น articulation
point โดย
o
ตรวจดูว่าโหนดไหนที่ลูก มีค่า Low
มากกว่าหรือเท่ากับ Num ของแม่
ถือว่าโหนดแม่ตัวนั้นเป็น articulation point
o
ไม่จำเป็นต้องทดสอบกับ root
ตัวอย่างการทดสอบเช่น
o
ที่จุด A เป็น
root ไม่ต้องทดสอบ
o
ที่จุด B กับ C
เทียบดู พบว่า 1 < 2 ดังนั้น B ไม่เป็น articulation point
o
ที่จุด C
o
เทียบกับ D พบว่า
1 < 3 ดังนั้น
ไม่เป็นตามกฏ
o
เทียบกับ G พบว่า 7 >= 3 ดังนั้น C
เป็น articulation point
o
ที่จุด D เทียบกับ E พบว่า 4
>= 4 ดังนั้น D เป็น articulation
point
o
ที่จุด E เที่ยบกับ
F พบว่า 4 < 5 ดังนั้นไม่เป็นตามกฏ
o
ที่จุด F ไม่มีลูก
o
ที่จุด G ไม่มีลูก
ด้วยวิธีการนี้ทำให้พบว่ามี articulation
point อยู่ 2 จุดคือ C กับ
D ดังภาพ
แบบทดสอบ
8. (10 คะแนน) จงสร้าง depth-first
spanning tree และแสดงค่า Num และ Low ของแต่ละ Vertex โดยเริ่มต้นจาก Vertex A
เราท่องเข้าไปแบบ preorder และสร้าง
depth-first spanning tree พร้อมกำหนดค่า Num ได้ดังนี้
และท่องเข้าไปใน depth-first spanning tree
แบบ post-order คำนวณค่า Low ของแต่ละโหนดได้ดังนี้
ตรวจสอบหาจุดที่ลูกมี Low >= Num ของแม่ จะพบจุดต่อไปนี้
สรุปว่า C, E, F เป็น
articulation point
ความคิดเห็น
แสดงความคิดเห็น