ผลต่างระหว่างรุ่นของ "418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริืทึมเกี่ยวกับกราฟ"

รุ่นแก้ไขเมื่อ 14:29, 31 สิงหาคม 2552

เนื้อหา

1 ข้อ 1
2 ข้อ 2
3 ข้อ 3
4 ข้อ 4
- 4.1 ข้อย่อย 4.1
- 4.2 ข้อย่อย 4.2

ข้อ 1

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

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

ข้อ 2

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

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

ข้อ 3

[Kleinberg & Tardos 3.2] จงออกแบบอัลกอริืทึมที่ตรวจสอบว่า undirected garph $G\,$ ที่ให้มาในรูปแบบ adjacency list มี cycle หรือไม่ ถ้ามีให้พิมพ์ออกมาหนึ่ง cycle (วงไหนก็ได้) อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา $O(n+m)\,$ เมื่อ $n\,$ คือจำนวน vertex $m\,$ คือจำนวน edge

[Dasgupta, Papadimitriou, Vazirani 3.11] จงออกแบบอัลกอริทึมที่ เมื่อให้ directed graph $G=(V,E)\,$ และให้ edge $e\in E\,$ มา แล้วคำนวณว่ามี cycle ที่มี $e\,$ เป็น edge หนึ่งอยู่ีใน cycle นั้นหรือไม่ ถ้ามีให้พิมพ์ออกมาสักหนึ่ง cycle อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n+m)\,$

ข้อ 4

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

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

นอกจากนี้ในการทำ depth first search เราจะพยายามเรียก DFS(u) ที่ทุก 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

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

จงรัน DFSALL บนกราฟข้างบน โดยเวลาไล่ vertex ให้ไล่จาก vertex ที่มีหมายเลขน้อยไปยังมากหมายเลขมาก (ยกตัวอย่างเช่น vertex ที่มี edge พุ่งออกจาก 7 ไปถึง ได้แก่ vertex 6 และ 8 เป็นต้น) แล้วเขียน

DFS tree
อะเรย์ $\mathrm {parent} [\cdot ]$
อะเรย์ $\mathrm {pre} [\cdot ]$
อะเรย์ $\mathrm {post} [\cdot ]$

ข้อย่อย 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 ชนิดใดบ้าง

ผลต่างระหว่างรุ่นของ "418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริืทึมเกี่ยวกับกราฟ"

รุ่นแก้ไขเมื่อ 14:29, 31 สิงหาคม 2552

เนื้อหา

ข้อ 1

ข้อ 2

ข้อ 3

ข้อ 4

ข้อย่อย 4.1

ข้อย่อย 4.2

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

@@ แถว 10: / แถว 10: @@
 == ข้อ 3 ==
-จงออกแบบอัลกอริืทึมที่ตรวจสอบว่ากราฟ <math>G \,</math> ที่ให้มาในรูปแบบ adjacency list มี cycle หรือไม่ ถ้ามีให้พิมพ์ออกมาหนึ่ง cycle (วงไหนก็ได้) อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา <math>O(n+m) \,</math> เมื่อ <math>n \,</math> คือจำนวน vertex <math>m \,</math> คือจำนวน edge
+# [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>
+== ข้อ 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>
+=== ข้อย่อย 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 ชนิดใดบ้าง