Biconnectedness (ค่ายวันที่ 11 มีนาคม 2551)

กำหนด undirected graph $G=(V,E)\,$ ซึ่งเป็นกราฟต่อเนื่อง ใดๆ

• เราเรียก vertex $v\,$ ว่าเป็น articulation point ถ้่าเราตัด $v\,$ และ edge ที่ต่อกับมันทั้งหมดออกไปออกจากกราฟแล้วจะทำให้กราฟเป็นกราฟไม่ต่อเนื่อง
• เราเรียก edge $e\,$ ว่าเป็น bridge ถ้าเราตัด $e\,$ ออกจากกราฟแล้วจะทำให้กราฟเป็นกราฟไม่ต่อเนื่อง
• เรากล่าวว่า edge สอง edge ใดๆ อยู่ใน biconnected component เดียวกันก็ต่อเมื่อมี simple cycle ที่มี edge ทั้งสองนั้นอยู่ภายใน

จะเห็นได้ว่าความสัมพันธ์ "อยู่ใน biconnected component เดียวกัน" จะแบ่ง edge ออกเป็นกลุ่มๆ ซึ่งเราเรียกกลุ่มเหล่านั้นว่า biconnected component (นั่นแหละ)

ภาพต่อไปนี้แสดง articulation point (vertex สีแดง), bridge (edge เล็กบางสีแดง), และ biconnected component (edge ที่ไม่ใช่ bridge ที่อยู่ใน biconnected component เดียวกัน จะมีสีเดียวกัน) ของกราฟต่อเนื่องกราฟหนึ่ง

การหา articulation point

เราสามารถหา articulation point ทั้งหมดของกราฟที่กำหนดให้ได้ในเวลา $O(|V|+|E|)\,$ โดยการทำ DFS เพื่อคำนวณข้อมูลเสริมบางอย่างของ vertex ทุก vertex ในกราฟ หลังจากนั้น เราจะนำข้อมูลนี้ไปประกอบการตัดสินใจว่า vertex ที่กำหนดให้เป็น articulation point หรือเปล่า

ก่อนจะมาพูดถึงนิยามของข้อมูลเสริมนี้ เรามาสังเกตกันก่อนว่าการที่ vertex $v\,$ ใด ในกราฟจะเป็น articulation point หรือไม่มันจะต้องมีสมบัติอย่างไร ในที่นี้ เราจะสมมติว่าเราได้ทำ DFS บนกราฟนี้ครั้งหนึ่งแล้ว และเราจะแยกการพิจารณาเป็นสองกรณี

1. $v\,$ เป็น root ของ DFS tree

สังเกตว่าถ้า root มีลูกมากกว่าหนึ่งตัว หมายความว่าถ้าเราจะเริ่มเดินจาก vertex ใน subtree ของลูกตัวหนึ่ง ไปยัง vertex ใน subtree ของลูกอีกตัวหนึ่ง เราต้องเดินผ่าน root เสมอ ดังนั้นถ้าตัด root ออกกราฟก็จะขาดออกจากกันเป็นสองส่วน (เพราะไม่มีเส้นทางเชื่อมระหว่าง vertex ใน subtree 2 ต้นใดๆ อีกต่อไป)

แต่ถ้า root มีลูกแค่ตัวเดียว แสดงว่าการเดินทางระหว่าง vertex คู่ใดๆ ในกราฟไม่มีความจำเป็นต้องผ่าน root อีกต่อไป ดังนั้นถ้าตัด root ออกก็จะไม่กระทบกระเทือนต่อความต่อเนื่องกันของกราฟ

ด้วยเหตุนี้ root ของ DFS tree จะเป็น articulation point ก็ต่อเมื่อมันมีลูกอย่างน้อยสองตัวเท่านั้น

2. $v\,$ เป็น internal vertex ของ DFS tree

พิจารณารูปข้างล่างนี้

เราสามารถแบ่งลูกของ $v\,$ ใน DFS ออกได้เป็น 3 กรณี

1. กรณีแรกคือกรณีเหมือน $x\,$ กล่าวคือใน subtree ที่มี root อยู่ที่ $x\,$ มี back edge พุ่งออกมาขึ้นไปต่อกับบรรพบุรุษของ $v\,$ บางตัว
2. กรณีที่สองคือกรณีเหมือน $y\,$ กล่าวคือใน subtree ที่มี root อยู่ที่ $y\,$ มี back edge พุ่งขึ้นออกมาต่อกับ $v\,$ เอง
3. กรณีที่สองคือกรณีเหมือน $z\,$ กล่าวคือใน subtree ที่มี root อยู่ที่ $z\,$ ไม่มี back edge พุ่งขึ้นมาเหนือหรืออยู่ในระดับเดียวกับ $v\,$ เลย

ถ้าเราตัด $v\,$ ออกแล้วจะเกิดอะไรขึ้น?

• ในกรณี $x\,$, subtree ที่มี root อยู่ที่ $x\,$ จะยังไม่ขาดออกจากกราฟเนื่องจากมันยังมี back edge ไปเชื่อมกับส่วนบนของกราฟอยู่
• แต่ในกรณี $y\,$ กับ $z\,$, subtree ที่มี root อยู่ที่ vertex ทั้่งสองจะขาดออกจากกราฟทันที

ดังนั้น $v\,$ จะเป็น articulation point ก็ต่อเมื่อมันมีลูกสักตัวที่มีลักษณะเหมือน $y\,$ หรือ $z\,$ กล่าวคือ ใน subtree ของลูกของลูกตัวนั้นจะไม่มี back edge พุ่งขึ้นไปต่อกับ $v\,$ หรือบรรพบุรุษของ $v\,$

ข้อมูลเสริม $low[v]\,$

ปัญหาสำคัญคือเราจะรู้ได้อย่างไรว่า subtree ที่มี root ที่ลูกของ $v\,$ จะมีหรือไม่มี back edge ที่ต่อขึ้นไปสูงกว่า $v\,$?