ดูต้นฉบับสำหรับ 418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริืทึมเกี่ยวกับกราฟ

== ข้อ 1 ==
ในชั้นเรียนเราได้พูดถึงการเก็บ undirected graph ด้วย adjacency matrix และ adjacency list

ถ้าเราจะเก็บ directed graph ด้วย adjacency matrix และ adjacency list บ้าง จะต้องเปลี่ยนแปลงรูปแบบการจัดเ็ก็บอย่างไรบ้าง?

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 1|เฉลย]]

== ข้อ 2 ==
[Dasgupta, Papadimitriou, Varizari 3.5] กำหนดกราฟแบบมีทิศทาง <math>G = (V,E) \,</math> มาให้ <b>กราฟผันกลับ (reverse)</b> ของ <math>G \,</math> คือกราฟ <math>G^R = (V,E^R) \,</math> โดยที่มีเซตของ vertex เป็นเซตเดียวกันแต่ edge ใน <math>G^R \,</math> คือ edge ใน <math>G \,</math> ที่ถูกกลับข้าง (กล่าวคือ <math>E^R = \{ (v,u)\ |\ (u,v) \in E \} \,</math>)

จงออกแบบอัลกอริทึมที่เมื่อให้ <math>G \,</math> ในรูปแบบ adjacency list ให้คำนวณ <math>G^R \,</math> ในรูปแบบ adjacency เช่นกัน อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(|V| + |E|) \,</math>


[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 2|เฉลย]]

== ข้อ 3 ==
# [Kleinberg & Tardos 3.2] จงออกแบบอัลกอริืทึมที่ตรวจสอบว่า undirected garph <math>G \,</math> ที่ให้มาในรูปแบบ adjacency list มี cycle หรือไม่ ถ้ามีให้พิมพ์ออกมาหนึ่ง cycle (วงไหนก็ได้) อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา <math>O(n+m) \,</math> เมื่อ <math>n \,</math> คือจำนวน vertex <math>m \,</math> คือจำนวน edge
# [Dasgupta, Papadimitriou, Vazirani 3.11] จงออกแบบอัลกอริทึมที่ เมื่อให้ directed graph <math>G = (V,E)\,</math> และให้ edge <math>e \in E \,</math> มา แล้วคำนวณว่ามี cycle ที่มี <math>e \,</math> เป็น edge หนึ่งอยู่ีใน cycle นั้นหรือไม่ ถ้ามีให้พิมพ์ออกมาสักหนึ่ง cycle อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(n+m) \,</math>

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 3|เฉลย]]

== ข้อ 4 ==
สมมติว่าเราอัลกอริทึมในการทำ depth first search ให้สร้างอะเรย์ขนาด <math>n \,</math> ช่อง เมื่อ <math>n \,</math> คือจำนวน vertex เพิ่มขึ้นอีกสองอะเรย์ ได้แก่ <math>\mathrm{pre}[\cdot]</math> และ <math>\mathrm{post}[\cdot]</math> โดยมีตัวแปร global ชื่อ <code>clock</code> ซึ่งมีค่าเริ่มแรกเท่ากับ 1 เป็นตัวช่วย ดังต่อไปนี้

<geshi lang="c">
DFS(u)
{
    pre[u] = clock
    clock = clock + 1
    explored[u] = 1
    
    for i = 1 to d[u] do
    {
        v = a[u][i]
        if explored[v] = 0 then
        {
            parent[v] = u
            DFS(v)
        }
    }

    post[u] = clock
    clock = clock + 1
}
</geshi>

กล่าวคือ <math>\mathrm{pre}[u] \,</math> เป็นเหมือนเวลาที่ <code>DFS(u)</code> เริ่มทำงาน และ <math>\mathrm{post}[u] \,</math> เป็นเวลาที่ <code>DFS(u)</code> ทำงานเสร็จ

นอกจากนี้ในการทำ depth first search เราจะพยายามเรียก <code>DFS(u)</code> ที่ทุก vertex u ในกราฟหามันยังไม่เคยถูกไปถึงด้วย DFS มาก่อน ดังต่อไปนี้

<geshi lang="c">
DFSALL()
{
     for u = 1 to n do
          if explored[u] = 0 then
          {
               parent[u] = 0
               DFS(u)
          }
}
</geshi>

=== ข้อย่อย 4.1 ===
พิจารณากราฟแบบมีทิศทางข้างล่างนี้

[[Image:Directed-graph-01.JPG‎]]

จงรัน DFSALL บนกราฟข้างบน โดยเวลาไล่ vertex ให้ไล่จาก vertex ที่มีหมายเลขน้อยไปยังมากหมายเลขมาก (ยกตัวอย่างเช่น vertex ที่มี edge พุ่งออกจาก 7 ไปถึง ได้แก่ vertex 6 และ 8 เป็นต้น) แล้วเขียน
# DFS tree
# อะเรย์ <math>\mathrm{parent}[\cdot]</math>
# อะเรย์ <math>\mathrm{pre}[\cdot]</math>
# อะเรย์ <math>\mathrm{post}[\cdot]</math>

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.1|เฉลย]]

=== ข้อย่อย 4.2 ===
หากเราจำแนก edge ในกราฟข้างบนออกเป็น 4 ประเภท ตังต่อไปนี้
* '''Tree edge''' คือ edge ที่อยู่บน DFS tree ที่ได้จากการทำ DFS
* '''Back edge''' คือ edge ที่พุ่งออกจาก vertex ไปหาบรรพบุรุษของมันใน DFS tree
* '''Forward edge''' คือ edge ที่พุ่งออกจาก vertex ไปหาลูกหลานของมันใน DFS tree
* '''Cross edge''' คือ edge อื่นๆ ที่ไม่เข้าพวกทั้งสามข้างต้น
แล้วจงบอกว่า edge ในกราฟเป็น edge แต่ละ edge เป็น edge ชนิดใดบ้าง

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.2|เฉลย]]

=== ข้อย่อย 4.3 ===
ให้ <math>G = (V,E) \,</math> เป็นกราฟแบบมีทิศทาง สมมติว่าเรารัน DFSALL บน <math>G \,</math> แล้ว จงพิสูจน์ "สมบัติวงเล็บ" ต่อไปนี้:

ถ้า <math>u\,</math> และ <math>v\,</math> เป็น vertex สอง vertex ใดๆ ในกราฟแล้ว ภายในข้อเท็จจริงสามข้อต่อไปนี้ จะมีข้อเท็จจริงข้อหนึ่งเป็นจริง และมันจะเป็นจริงเพียงข้อเดียวเท่านั้น
# <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u]\,</math>
# <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v]\,</math>
# ช่วง <math>[\mathrm{pre}[u], \mathrm{post}[u]]\,</math> และช่วง <math>[\mathrm{pre}[v], \mathrm{post}[v]]\,</math> ไม่มีสมาชิกร่วมกันเลย

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.3|เฉลย]]

=== ข้อย่อย 4.4 ===
จงพิสูจน์ว่า สำหรับ edge <math>e = (u,v)\,</math> ใดๆ เราสามารถใช้สมบัติวงเล็บข้างต้นในการจำแนกประเภทของมันได้
* ถ้า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u]\,</math> แล้ว <math>e\,</math> ต้องเป็น tree edge หรือ forward edge
* ถ้า <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{pre}[v]\,</math> แล้ว <math>e\,</math> ต้องเป็น back edge
* ถ้า <math>[\mathrm{pre}[u], \mathrm{post}[u]]\,</math> และ <math>[\mathrm{pre}[v], \mathrm{post}[v]]\,</math> ไม่มีส่วนร่วมกัน แล้ว <math>e\,</math> ต้องเป็น cross edge

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.4|เฉลย]]

=== ข้อย่อย 4.5 ===
ถ้าเรารัน DFSALL บน undirected graph แทนที่จะเป็น directed graph แล้ว จงพิสูจน์ว่าจะไม่มี forward edge หรือ cross edge อยู่เลย (กล่าวคือ edge ทุก edge จะเป็น tree edge หรือ back edge เท่านั้น)

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.5|เฉลย]]

== ข้อ 5 ==
จงออกแบบอัลกอริทึมที่เมื่อรับ directed graph <math>G = (V,E) \,</math> มาหนึ่งกราฟแล้ว คำนวณหา cycle ใน <math>G \,</math> มาหนึ่งวง วงใดก็ได้ ถ้าไม่มี cycle ก็ให้ตอบว่าไม่มี อัลกอริืทึมของคุณควรจะทำงานได้ในเวลา <math>O(|V|+|E|) \,</math>

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 5|เฉลย]]

== ข้อ 6 ==
ถ้า <math>G = (V,E) \,</math> เป็น directed graph และ <math>G \,</math> ไม่มี cycle แล้ว เราเรียกว่า <math>G \,</math> เป็น '''directed acyclic graph (DAG)'''

=== ข้อย่อย 6.1 === 
จงพิสูจน์ว่าถ้าเรารัน DFSALL บน <math>G \,</math> ที่เป็น DAG แล้ว สำหรับ edge <math>(u,v) \,</math> ทุก edge เราจะได้ว่า <math>\mathrm{post}[u] > \mathrm{post}[v] \,</math> เสมอ

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.1|เฉลย]]

=== ข้อย่อย 6.2 ===
สำหรับ DAG <math>G \,</math> หนึ่งๆ เราให้ topological ordering ของ <math>G \,</math> คือการนำ vertex ต่างๆ ใน <math>V \,</math> มาเรียงกัน โดยที่ถ้า <math>v \,</math> ตามหลัง <math>u \,</math> ใน topological ordering แล้วจะไม่มี path จาก <math>v \,</math> ไปยัง <math>u \,</math>

จากกราฟต่อไปนี้

[[ไฟล์:pro6_2.JPG]]

จงหา topological ordering สักหนึ่ง ordering

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.2|เฉลย]]

=== ข้อย่อย 6.3 ===
จงออกแบบอัลกอริทึมสำหรับหา topological ordering ของ DAG โดยใช้ DFSALL

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.3|เฉลย]]

=== ข้อย่อย 6.4 ===
ใน directed graph เราเรียก vertex <math>u \,</math> ว่าเป็น '''source''' ถ้าหากมี edge ใดๆ ชี้มายังมันเลย

จงพิสูจน์ว่าใน DAG จะมี source อยู่อย่างน้อยหนึ่ง vertex เสมอ

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.4|เฉลย]]

=== ข้อย่อย 6.5 ===
จงออกแบบอัลกอริทึมสำหรับหา topological ordering ของ DAG โดยใช้ความจริงในข้อย่อย 6.4

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.5|เฉลย]]

== ข้อ 7 ==
[Dasgupta, Papadimitriou, Vazirani 3.18] คุณได้รับ tree <math>T = (V,E) \,</math> (ในรูปแบบ adjacency list) รวมทั้ง root vertex <math>r \in V \,</math>

เรากล่าวคือ vertex <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> ถ้าหากว่ path จาก <math>r \,</math> ไปยัง <math>v \,</math> ต้องผ่าน <math>u \,</math>

คุณต้องการทำการ precomputation ต้นไม้ที่ได้รับมาเพื่อหลังจากนั้นจะได้ตอบคำถามในรูปแบบที่ว่า "กำหนด vertex <math>u \,</math> และ <math>v \,</math> ในกราฟมาให้ จงหาว่า <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> หรือไม่?" ได้โดยใช้เวลา <math>O(1) \,</math> 

จงออกแบบอัลกอริทึมเพื่อทำ precomputation ดังกล่าว รวมทั้งบอกวิธีตอบคำถามโดยใช้ข้อมูลที่ทำการคำนวณมาแล้ว อัลกอริืทึีมในการทำ precomputation ควรทำงานได้ในเวลา <math>O(|V|+|E|) \,</math>

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 7|เฉลย]]

== ข้อ 8 ==
[Dasgupta, Papadimitriou, Vazirani 3.19] คุณได้รับ tree <math>T = (V,E) \,</math> (ในรูปแบบ adjacency list) รวมทั้ง root vertex <math>r \in V \,</math> นอกจากนี้ยังได้รับอะเรย์ของจำนวนเต็ม <math>x[\cdot] \,</math> โดยที่ <math>x[u] \,</math> ถือเป็น "ค่า" ของ vertex <math>u \,</math>

เราจะสร้างอะเรย์ <math>z[\cdot] \,</math> ขึ้นมาใหม่โดยที่
: <math>z[u] = \,</math> ค่า <math>x[v] \,</math> ที่มีค่ามากที่สุดสำหรับ vertex <math>v \,</math> ทุก vertex ที่มี <math>u \,</math> เป็นบรรพบุรุษ (รวมไปถึงตัว <math>u \,</math> เองด้วย)

จงออกแบบอัลกอริทึมเพื่อคำนวนอะเรย์ <math>z[\cdot] \,</math> ซึ่งทำงานได้ในเวลา <math>O(|V| + |E|) \,</math>

[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 8|เฉลย]]