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\,$

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

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

สิ่งที่เราจะทำคือเราจะเก็บว่าสำหรับ vertex $v\,$ ทุกตัว เราจะคำนวณหา vertex ที่ "สูง" ทีุ่สุดใน tree ที่มี back edge พุ่งออกจาก subtree ที่มี root อยู่ที่ $v\,$ ไปถึง

แต่เราจะบอกได้อย่างไรว่า vertex ไหน "สูง" หรือ vertex ไหน "ต่ำ"? คำตอบคือเราสามารถใช้สมบัติวงเล็บของ discovery time เข้ามาช่วยได้ (ถ้าจำไม่ได้ ดูเรื่องสมบัติวงเล็บที่หน้านี้) กล่าวคือ ถ้า $a\,$ อยู่ "สูง" กว่า $b\,$ ใน DFS tree แล้ว $d[a]<d[b]\,$ เสมอ ดังนั้นเราสามารถตัดสินว่า vertex ใดอยู่สูงกว่าหรือต่ำกว่าใน tree ได้โดยการเปรียบเทียบค่า discovery time ของ vertex เหล่านั้น

อย่างไรก็ดี ประเดี๋ยวคุณจะได้รู้ว่าเราไม่ีมีความจำเป็นต้องเก็บ "ตัว vertex" เราแค่เก็บค่า discovery time ที่ต่ำที่สุดก็เพียงพอ เพื่อความสะดวก เราจะนิยามค่า discovery time ที่ต่ำสุดนี้่ว่า $low[v]\,$ ซึ่งมันควรจะมีความหมายตามข้างล่างนี้:

$low[v]\,$ ควรมีค่าเท่ากับ discover time ที่ต่ำที่สุดของ vertex $w\,$ บางตัวที่ back edge $(u,w)\,$ สำหรับ vertex $u\,$ บาง vertex ใน subtree ของ DFS tree ที่มี root อยู่ที่ $v\,$

แต่นิยามข้างบนนี้ยังไม่รัดกุมนัก เพราะถ้าหากมีกรณีที่ subtree ที่มี root อยู่ที่ $v\,$ ไม่มี back edge เลยสักเส้น แล้วเราจะให้ $low[v]\,$ มีค่าเท่าไหร่?

เราอาจจะให้ในกรณีนี้ $low[v]\,$ มีค่าเท่ากับ $\infty \,$ แต่ในเอกสารฉบับนี้จะนิยามค่า $low[v]\,$ ตามหนังสือ CLRS กล่าวคือ เราจะให้ $low[v]\,$ เป็นค่าที่ต่ำที่สุดระหว่าง $d[v]\,$ กับ discovery time ของ vertex ที่ back edge ต่อไปถึง

เราจึงสามารถเขียนนิยาม $low[v]\,$ อย่างเป็นทางการได้ดังนี้

$low[v]={\begin{cases}d[v],\\d[w]\ :\mathrm {where} \ (u,w)\ \mathrm {is} \ \mathrm {a} \ \mathrm {back} \ \mathrm {edge} \ \mathrm {and} \ u\ \mathrm {is} \ \mathrm {a} \ \mathrm {vertex} \ \mathrm {in} \ \mathrm {the} \ \mathrm {subtree} \ \mathrm {rooted} \ \mathrm {at} \ v.\end{cases}}\,$

การคำนวณค่า $low[v]\,$

เราสามารถคำนวณค่า $low[v]\,$ ระหว่างที่ทำ DFS ได้ โดยสังเกตว่าค่า $low[v]\,$ เป็นค่าที่ต่ำที่สุดระหว่าง

1. $d[v]\,$
2. d[w] ถ้า $(v,w)\,$ เป็น back edge และ
3. $low[u]\,$ ถ้า $u\,$ เป็นลูกของ $v\,$

Pseudocode ของ DFS ที่ทำการคำนวณ $low[v]\,$ ไปด้วยมีดังนี้:

function DFS(v)
{
    time = time + 1
    d[v] = time
    visited[v] = true
    low[v] = d[v]

    for edge (v,w) ใดๆ
    {
        if w != parent[v] && visited[w] == true      // กรณีนี้เป็น back edge
            low[v] = min(low[v], d[w])
        else if visited[w] == false                  // กรณีนี้เป็น tree edge เส้นใหม่
        {
            parent[w] = v
            DFS(w)
            low[v] = min(low[v], low[w])
        } 
    }

    time = time + 1
    f[v] = time
}

สังเกตว่าใน pseudocode ข้างบน เราจะเก็บไว้ด้วยว่าพ่อของแต่ละ vertex คืออะไร เพื่อแยกแยะระหว่าง tree edge กับ back edge

ตัดสินว่า vertex เป็น articulation point หรือไม่

ทวนอีกครั้ง: vertex $v\,$ จะเป็น articulation point ถ้าหากว่ามันมีลูก $u\,$ ที่ไม่มี back edge ที่ไปต่อกับ vertex ที่อยู่สูงกว่า $v\,$ ออกมาจาก subtree ที่มี root อยู่ที่ $u\,$

เขียนอีกแบบได้ว่า: vertex $v\,$ จะเป็น articulation point ถ้าหากว่ามันมีลูก $u\,$ ที่ $low[u]\geq d[v]\,$

เขียนเป็น pseudocode ได้ว่า:

function is_articulation_point(v)
{
   for edge (v,u) ใดๆ
       if parent[u] == v   // กล่าวคือ u เป็นลูกของ v
          if low[u] >= d[v]
              return true
   return false
}

ฟังก์ชัน is_articulation_point(v) มี running time $O(\deg(v))\,$ ดังนั้นถ้าเราถาม is_articulation_point สำหรับทุก vertex ในกราฟ เราจะใช้เวลา $O(|V|+|E|)\,$

การหา bridge

เราสามารถตัดสินว่า edge ที่กำหนดให้ bridge ได้หรือไม่ โดยใช้ $low[v]\,$ มาประกอบการตัดสินใจได้คล้ายๆ กับตัดสินว่า vertex เป็น articulation point หรือไม่ข้างต้น แต่การตัดสินว่า edge เป็น bridge หรือไม่สามารถทำได้ง่ายกว่ามาก โดยสามารถทำได้ดังต่อไปนี้

ขั้นแรก: เราตรวจสอบว่า edge ที่ให้มานั้นเป็น tree edge หรือ back edge ถ้าหาก edge ที่ให้มาเป็น back edge มันต้องไม่เป็น bridge อย่างแน่นอน เพราะว่า back edge จะอยู่ใน cycle เสมอ

ขั้นที่สอง: หาก edge ที่กำหนดให้เป็น tree edge ให้เราพิจารณากรณีสามกรณีดังภาพข้างล่างนี้ (ภาพเดิมกับภาพข้างบน)

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

ดังนั้นเราสามารถสรุปได้ว่า

edge $(v,w)\,$ จะเป็น bridge ก็ต่อเมื่อมันเป็น tree edge ซึ่ง (โดยไม่เสียนัยทั่วไป) ถ้า $v\,$ เป็นพ่อของ $w\,$ แล้ว $low[w]>d[v]\,$

เขียนเป็น pseudocode ได้ดังนี้

function is_bridge(v,w)
{
   if parent[v] != w && parent[w] != v       // เช็คว่าไม่เป็น tree edge หรือเปล่า?
       return false

   if parent[v] == w
       return low[v] > d[w]
   else
       return low[w] > d[v]
}

ฟังก์ชัน is_bridge(v,w) มี running time $O(1)\,$ ดังนั้นเราสามารถหา bridge ในกราฟโดยเรียกฟังก์ชันนี้กับ edge ทุก edge ได้ในเวลา $O(|E|)\,$

การระบุ biconnected component

ในหัวข้อนี้เราจะสนใจการใส่เลข $bcc[e]\,$ (ย่อมาจาก biconnected component) สำำหรับ edge $e\,$ แต่ละ edge โดยที่ $e\,$ และ $e'\,$ อยู่ใน biconnected component เดียวกัน ก็ต่อเมื่อ $bcc[e]=bcc[e']\,$

เราทำการใส่เลข $bcc[e]\,$ ได้ใน $O(|V|+|E|)\,$ หลังจากเราคำนวณค่า $low[v]\,$ และ $parent[v]\,$ ข้างต้นเสร็จแล้ว โดยเราจะทำ DFS ลงไปในกราฟอีกครั้ง โดยมีลำดับการเข้าไปเยี่ยมเยือน vertex ต่างๆ เหมือนกับตอนที่เราทำ DFS เพื่อคำนวณ $low[v]\,$ ครั้งแรก

พิจารณาภาพข้างล่าง

เราใช้ข้อสังเกตต่อไปนี้ในการออกแบบอัลกอริทึม

• สมมติว่าขณะนี้เรากำลังทำ DFS ครั้งที่สอง และเรามาอยู่ที่ vertex $v\,$ โดยตาม edge $(u,v)\,$ ลงมา และเราได้ให้หมายเลข $bcc[(u,v)]=\alpha \,$
• สำหรับ back edge $(v,w)\,$ ใดๆ มันก็ควรได้หมายเลข $bcc[(v,w)]=\alpha \,$ ไปด้วย เพราะว่ามันอยู่ใน simple cycle เดียวกับ $(u,v)\,$
• สำหรับ tree edge ที่ต่อ $v\,$ กับลูกของมัน มีสามกรณี
  1. กรณี $(v,x)\,$ ซึ่งมี back edge จาก subtree ที่มี root อยู่ที่ x ไปยังบรรพบุรุษของ $v\,$ บางตัว ในกรณีนี้ $bcc[(v,x)]=\alpha \,$ เนื่องจากมันอยู่ใน simple cycle เดียวกับ $(u,v)\,$
  2. กรณี $(v,y)\,$ ซึ่งมี back edge จาก subtree ที่มี root อยู่ที่ y มายัง $v\,$ เอง ในกรณีนี้ $bcc[(v,x)]=\beta \,$ โดยที่ $\beta \neq \alpha \,$ เนื่องจาก $(v,y)$ ไม่ได้อยู่ใน simple cycle เดียวกับ $(u,v)\,$ แล้ว
  3. กรณี $(v,z)\,$ เป็น bridge ในกรณีนี้เราไม่จำเป็นต้องใส่หมายเลขให้ $(v,z)\,$ แต่ edge ใดๆ ก็ตามที่อยู่ใน subtree ที่ีมี $z\,$ เป็น root จะต้องได้หมายเลขไม่ซ้ำกับที่ edge อื่นๆ ในกราฟเคยได้มาแล้ว

เราใช้ข้อสังเกตข้างต้นในการออกแบบอัลกอริทึมดังต่อไปนี้

• อัลกอริทึมของเราจะท่องไปในกราฟแบบ DFS ตามลำดับการเยี่ยมเยือน vertex เหมือนตอนที่เราคำนวณ $low[v]\,$ ตอนแรก
• เราจะเขียนอัลกอริทึมเราในฟังก์ชัน assign_bcc(v, alpha) โดย v คือ vertex ที่เรากำลังจะทำ DFS ส่วน alpha คือหมายเลข biconnected component ที่เราใส่ให้ tree edge ที่นำเรามาสู่ v หาก tree edge นั้นเป็น bridge เราจะให้ alpha มีค่าพิเศษ ในที่นี้สมมติให้เป็น -1
• เราจะให้มีตัวแปร global ชื่อ last_component ซึ่งเป็นหมายเลขของ biconnected component หมายเลขสุดท้ายที่เคยใช้ไปแล้ว เริ่มต้น last_component จะมีค่าเท่ากับ 0 เพื่อให้ biconnected component แรกได้หมายเลข 1
• เมื่อเราพิจารณา vertex v และ edge (v,w) ที่ต่ออยู่กับมัน เราจะได้ว่า
  • ถ้า (v,w) เป็น back edge เราสามารถกำหนด bcc[(v,w)] = alpha
  • ถ้า (v,w) มีลักษณะเหมือน $(v,x)\,$ กล่าวคือ low[w] < d[v] เราสามารถกำหนด bcc[(v,w)] = alpha ได้เช่นกันถ้า alpha มีค่าไม่เท่ากับ -1 หลังจากนั้นเราจะเรียก assign_bcc(w, alpha) เพื่อให้หมายเลขกับ edge ใน subtree ที่มี w เป็น root ต่อไป ถ้า alpha มีค่าเท่ากับ -1 แล้วเราต้องเพิ่มค่า last_component ขึ้นหนึ่งแล้วให้ bcc[(v,w)] = last_component หลังจากนั้นจึงเรียก assign_bcc(w, last_component)
  • ถ้า (v,w) มีลักษณะเหมือน $(v,y)\,$ กล่าวคือ low[w] = d[v] เราจะเพิ่ม last_component ขึ้น 1 แล้วให้ bcc[(v,w)] = last_component หลังจากนั้นเราจะเรียก assign_bcc(w, last_component)
  • ถ้า (v,w) มีลักษณะเหมือน $(v,z)\,$ กล่าวคือ low[w] > d[v] เราจะเรียก assign_bcc(w, -1) ทันที

เมื่อเขียนเป็น pseudocode จะได้ดังต่อไปนี้

function assign_bcc(v, alpha)
{
    for edge (v,w) ใดๆ
        if parent[v] == w      // กรณีเป็น tree edge ที่นำเรามาสู่ v
            continue
        else if d[w] < d[v]    // กรณีเป็น back edge
            bcc[(v,w)] = alpha
        else if low[w] < d[v]
        {
            if alpha == -1
            {
                last_component++;
                bcc[(v,w)] = last_component
                assign_bcc(w, last_component)
            }
            else
            {
                bcc[(v,w)] = alpha
                assign_bcc(w, alpha)
            }
        }
        else if low[w] == d[v]
        {
            last_component++;
            bcc[(v,w)] = last_component
            assign_bcc(w, last_component)
        }
        else
            assign_bcc(w, -1)
}