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

รุ่นแก้ไขปัจจุบันเมื่อ 13:44, 16 กันยายน 2552

เราจะทำการพิสูจน์ข้อความทั้งสามโดยใช้ข้อสังเกตสองข้อต่อไปนี้

ถ้า $\mathrm {DFS} (v)\,$ ถูกเรียกให้ทำงานหลังจาก $\mathrm {DFS} (u)\,$ ทำงาน แต่ก่อนที่ $\mathrm {DFS} (u)\,$ จะทำงานเสร็จ แล้วจะมี path ใน DFS tree จาก $u\,$ ถึง $v\,$

พิสูจน์: เนื่องจาก $\mathrm {DFS} (v)\,$ ถูกเรียกให้ทำงานระหว่างที่ $\mathrm {DFS} (u)\,$ ทำงานไปแล้วแต่ยังทำให้เสร็จ เราจะได้ว่ามีลำดับของ vertex $u_{1},u_{2},\ldots ,u_{k}\,$ โดยที่ $k\geq 0\,$ โดยที่ $\mathrm {DFS} (u)\,$ เรียก $\mathrm {DFS} (u_{1})\,$ แล้ว $\mathrm {DFS} (u_{1})\,$ เรียก $\mathrm {DFS} (u_{2})\,$ เช่นนี้ไปเรื่อยๆ จนกระทั้ง $\mathrm {DFS} (u_{k})\,$ เรียก $\mathrm {DFS} (v)\,$

เนื่องจาก $\mathrm {DFS} (u)\,$ เรียก $\mathrm {DFS} (u_{1})\,$ แสดงว่ามี edge $(u,u_{1})\,$ อยู่ในกราฟ นอกจากนี้ edge $(u,u_{1})\,$ นี้ยังเป็น tree edge อีกด้วย ในทำนองเดียวกัน เราจะได้ว่า edge $(u_{1},u_{2})\,$ , $(u_{2},u_{3})\,$ , $\ldots \,$ , $(u_{k},v)\,$ ก็เป็น tree edge เช่นเดียวกัน ดังนั้นจึงมี path ใน DFS tree จาก $u\,$ ไปยัง $v\,$

กรณีที่ 1

เราจะพิสูจน์ว่าถ้า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ แล้ว edge $(u,v)\,$ จะต้องเป็น tree edge หรือว่า forward edge

พิสูจน์: เนื่องจาก $\mathrm {pre} [u]<\mathrm {pre} [v]\,$ เรารู้ว่า $\mathrm {DFS} (u)\,$ เริ่มทำงานก่อน $\mathrm {DFS} (v)\,$ เนื่องจาก $\mathrm {post} [v]<\mathrm {post} [u]\,$ เรารู้ว่า $\mathrm {DFS} (v)\,$ ถูกเรียกก่อนที่ $\mathrm {DFS} (u)\,$ จะทำงานเสร็จ

ฉะนั้นจะต้องมี path ใน DFS tree จาก $u\,$ ถึง $v\,$ กล่าวคือ $v\,$ เป็นลูกหลานของ $u\,$

ดังนั้น $(u,v)\,$ จึงเป็น tree edge หรือไม่ก็ forward edge

กรณีที่ 2

เราจะพิสูจน์ว่าถ้า $\mathrm {pre} [v]<\mathrm {pre} [u]<\mathrm {post} [u]<\mathrm {post} [v]\,$ แล้ว edge $(u,v)\,$ จะต้องเป็น back edge

พิสูจน์: เนื่องจาก $\mathrm {pre} [v]<\mathrm {pre} [u]\,$ เรารู้ว่า $\mathrm {DFS} (v)\,$ เริ่มทำงานก่อน $\mathrm {DFS} (u)\,$ เนื่องจาก $\mathrm {post} [u]<\mathrm {post} [v]\,$ เรารู้ว่า $\mathrm {DFS} (u)\,$ ถูกเรียกก่อนที่ $\mathrm {DFS} (v)\,$ จะทำงานเสร็จ

ฉะนั้นจะต้องมี path ใน DFS tree จาก $v\,$ ถึง $u\,$ กล่าวคือ $u\,$ เป็นลูกหลานของ $v\,$

ดังนั้น $(u,v)\,$ จึงเป็น back edge

กรณีที่ 3

เราจะพิสูจน์ว่าถ้า $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ ไม่มีส่วนร่วมกันแล้ว $(u,v)\,$ จะต้องเป็น cross edge

พิสูจน์: ให้ประพจน์ $P\,$ แทนข้อความ " $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ ไม่มีส่วนร่วมกันแล้ว"

ใ้ห้ประพจน์ $Q\,$ แทนข้อความ " $(u,v)\,$ เป็น cross edge"

เราต้องการพิสูจน์ว่า $P\rightarrow Q\,$

cross edge คือ edge ที่ไม่ใช่ tree edge, back edge, หรือ forward edge ดังนั้นเราสามารถพิสูจนฺ์ว่า $(u,v)\,$ เป็น cross edge ได้โดยการพิสูจน์ข้อความ $P\rightarrow (\neg X\wedge \neg Y\wedge \neg Z)\,$ เมื่อ

$X\,$ คือข้อความ " $(u,v)\,$ เป็น tree edge"
$Y\,$ คือข้อความ " $(u,v)\,$ เป็น back edge"
$Z\,$ คือข้อความ " $(u,v)\,$ เป็น forward edge"

เนื่องจาก $P\rightarrow (\neg X\wedge \neg Y\neg Z)\equiv (X\vee Y\vee Z)\rightarrow \neg P\,$ เราจึงจะทำการพิสูจน์ข้อความ $(X\vee Y\vee Z)\rightarrow \neg P\,$ แทน

สมมติให้ $X\vee Y\vee Z\,$ เป็นจริง กล่าวคือ $(u,v)\,$ เป็น tree, back, หรือ forward edge เราจะได้ว่า

ถ้า $(u,v)\,$ เป็น tree edge แล้ว เราจะได้ว่า $\mathrm {DFS} (v)\,$ ถูกเรียกหลัง $\mathrm {DFS} (u)\,$ เริ่มทำงาน และ $\mathrm {DFS} (v)\,$ จบการทำงานก่อน $\mathrm {DFS} (u)\,$ จะจบการทำงาน ดังนั้น $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ กล่าวคือช่วง $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ มีส่วนร่วมกัน
ถ้า $(u,v)\,$ เป็น back edge แล้ว เราจะได้ว่า $u\,$ เป็นลูกหลานของ $v\,$ ใน DFS tree ดังนั้น $\mathrm {DFS} (u)\,$ ถูกเรียกหลัง $\mathrm {DFS} (v)\,$ เริ่มทำงาน และ $\mathrm {DFS} (u)\,$ จบการทำงานก่อน $\mathrm {DFS} (v)\,$ จะจบการทำงาน ดังนั้น $\mathrm {pre} [v]<\mathrm {pre} [u]<\mathrm {post} [u]<\mathrm {post} [v]\,$ กล่าวคือช่วง $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ มีส่วนร่วมกัน
ถ้า $(u,v)\,$ เป็น forward edge แล้ว เราสามารถใช้การให้เหตุผลในข้อ 1 แสดงได้ว่า ช่วง $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ มีส่วนร่วมกันได้

ทั้งสามกรณีให้ข้อสรุปว่า $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ มีส่วนร่วมกัน กล่าวคือประพจน์ $Q\,$ ไม่เป็นจริง

ดังนั้นเราสามารถสรุปได้ว่าถ้า $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ ไม่มีส่วนร่วมกันแล้ว $(u,v)\,$ จะต้องเป็น cross edge

@@ แถว 1: / แถว 1: @@
+เราจะทำการพิสูจน์ข้อความทั้งสามโดยใช้ข้อสังเกตสองข้อต่อไปนี้
+<blockquote>
+ถ้า <math>\mathrm{DFS}(v) \,</math> ถูกเรียกให้ทำงานหลังจาก <math>\mathrm{DFS}(u) \,</math> ทำงาน
+แต่ก่อนที่ <math>\mathrm{DFS}(u) \,</math> จะทำงานเสร็จ แล้วจะมี path ใน DFS tree จาก <math>u \,</math> ถึง <math>v \,</math>
+</blockquote>
+'''พิสูจน์:''' เนื่องจาก <math>\mathrm{DFS}(v) \,</math> ถูกเรียกให้ทำงานระหว่างที่ <math>\mathrm{DFS}(u) \,</math> ทำงานไปแล้วแต่ยังทำให้เสร็จ
+เราจะได้ว่ามีลำดับของ vertex <math>u_1, u_2, \ldots, u_k \,</math> โดยที่ <math>k \geq 0 \,</math> โดยที่ <math>\mathrm{DFS}(u) \,</math> เรียก
+<math>\mathrm{DFS}(u_1) \,</math> แล้ว <math>\mathrm{DFS}(u_1) \,</math> เรียก <math>\mathrm{DFS}(u_2) \,</math> เช่นนี้ไปเรื่อยๆ จนกระทั้ง
+<math>\mathrm{DFS}(u_k) \,</math> เรียก <math>\mathrm{DFS}(v) \,</math>
+เนื่องจาก <math>\mathrm{DFS}(u) \,</math> เรียก <math>\mathrm{DFS}(u_1) \,</math> แสดงว่ามี edge <math>(u, u_1) \,</math> อยู่ในกราฟ
+นอกจากนี้ edge <math>(u, u_1) \,</math> นี้ยังเป็น tree edge อีกด้วย ในทำนองเดียวกัน เราจะได้ว่า edge <math>(u_1, u_2) \,</math>, <math>(u_2, u_3) \,</math>,
+<math>\ldots \,</math>, <math>(u_k, v) \,</math> ก็เป็น tree edge เช่นเดียวกัน ดังนั้นจึงมี path ใน DFS tree จาก <math>u \,</math> ไปยัง <math>v \,</math>
 == กรณีที่ 1 ==
-เราต้องการพิสูจน์ว่าถ้า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> แล้ว edge <math>(u,v) \,</math>
+เราจะพิสูจน์ว่าถ้า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> แล้ว edge <math>(u,v) \,</math>
 จะต้องเป็น tree edge หรือว่า forward edge
-เนื่องจาก <math>\mathrm{pre}[u] < \mathrm{pre}[v] \,</math> เรารู้ว่า DFSALL(u) เริ่มทำงานก่อน DFSALL(v) และ
+'''พิสูจน์:''' เนื่องจาก <math>\mathrm{pre}[u] < \mathrm{pre}[v] \,</math> เรารู้ว่า <math>\mathrm{DFS}(u) \,</math> เริ่มทำงานก่อน
-เนื่องจาก <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math> เรารู้ว่า DFSALL(v) ถูกเรียกก่อนที่ DFSALL(u) จะทำงานเสร็จ
+<math>\mathrm{DFS}(v) \,</math> เนื่องจาก <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math>
-ฉะนั้นจะต้องมี path ใน DFS tree จาก <math>u \,</math> ถึง <math>v \,</math> ดังนั้น <math>(u,v) \,</math> จึงเป็น tree edge
+เรารู้ว่า <math>\mathrm{DFS}(v) \,</math> ถูกเรียกก่อนที่ <math>\mathrm{DFS}(u) \,</math> จะทำงานเสร็จ
-หรือไม่ก็ forward edge
+ฉะนั้นจะต้องมี path ใน DFS tree จาก <math>u \,</math> ถึง <math>v \,</math> กล่าวคือ <math>v \,</math> เป็นลูกหลานของ <math>u \,</math>
+ดังนั้น <math>(u,v) \,</math> จึงเป็น tree edge หรือไม่ก็ forward edge
+== กรณีที่ 2 ==
+เราจะพิสูจน์ว่าถ้า <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v] \,</math> แล้ว edge <math>(u,v) \,</math>
+จะต้องเป็น back edge
+'''พิสูจน์:''' เนื่องจาก <math>\mathrm{pre}[v] < \mathrm{pre}[u] \,</math> เรารู้ว่า <math>\mathrm{DFS}(v) \,</math> เริ่มทำงานก่อน
+<math>\mathrm{DFS}(u) \,</math> เนื่องจาก <math>\mathrm{post}[u] < \mathrm{post}[v] \,</math>
+เรารู้ว่า <math>\mathrm{DFS}(u) \,</math> ถูกเรียกก่อนที่ <math>\mathrm{DFS}(v) \,</math> จะทำงานเสร็จ
+ฉะนั้นจะต้องมี path ใน DFS tree จาก <math>v \,</math> ถึง <math>u \,</math> กล่าวคือ <math>u \,</math> เป็นลูกหลานของ <math>v \,</math>
+ดังนั้น <math>(u,v) \,</math> จึงเป็น back edge
+== กรณีที่ 3 ==
+เราจะพิสูจน์ว่าถ้า <math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และ <math>\mathrm{pre}[v], \mathrm{post}[v] \,</math> ไม่มีส่วนร่วมกันแล้ว
+<math>(u,v) \,</math> จะต้องเป็น cross edge
+'''พิสูจน์:''' ให้ประพจน์ <math>P \,</math> แทนข้อความ "<math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math>
+และ <math>\mathrm{pre}[v], \mathrm{post}[v] \,</math> ไม่มีส่วนร่วมกันแล้ว"
+ใ้ห้ประพจน์ <math>Q \,</math> แทนข้อความ "<math>(u,v) \,</math> เป็น cross edge"
+เราต้องการพิสูจน์ว่า <math>P \rightarrow Q \,</math>
+cross edge คือ edge ที่ไม่ใช่ tree edge, back edge, หรือ forward edge ดังนั้นเราสามารถพิสูจนฺ์ว่า <math>(u,v) \,</math> เป็น cross edge
+ได้โดยการพิสูจน์ข้อความ <math>P \rightarrow (\neg X \wedge \neg Y \wedge \neg Z) \,</math> เมื่อ
+* <math>X \,</math> คือข้อความ "<math>(u,v) \,</math> เป็น tree edge"
+* <math>Y \,</math> คือข้อความ "<math>(u,v) \,</math> เป็น back edge"
+* <math>Z \,</math> คือข้อความ "<math>(u,v) \,</math> เป็น forward edge"
+เนื่องจาก <math>P \rightarrow (\neg X \wedge \neg Y \neg Z) \equiv (X \vee Y \vee Z) \rightarrow \neg P \,</math> เราจึงจะทำการพิสูจน์ข้อความ
+<math>(X \vee Y \vee Z) \rightarrow \neg P \,</math> แทน
+สมมติให้ <math>X \vee Y \vee Z \,</math> เป็นจริง กล่าวคือ <math>(u,v) \,</math> เป็น tree, back, หรือ forward edge เราจะได้ว่า
+# ถ้า <math>(u,v) \,</math> เป็น tree edge แล้ว เราจะได้ว่า <math>\mathrm{DFS}(v) \,</math> ถูกเรียกหลัง <math>\mathrm{DFS}(u) \,</math> เริ่มทำงาน และ <math>\mathrm{DFS}(v) \,</math> จบการทำงานก่อน <math>\mathrm{DFS}(u) \,</math> จะจบการทำงาน ดังนั้น <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> กล่าวคือช่วง <math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และ <math>\mathrm{pre}[v], \mathrm{post}[v] \,</math> มีส่วนร่วมกัน
+# ถ้า <math>(u,v) \,</math> เป็น back edge แล้ว เราจะได้ว่า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> ใน DFS tree ดังนั้น <math>\mathrm{DFS}(u) \,</math> ถูกเรียกหลัง <math>\mathrm{DFS}(v) \,</math> เริ่มทำงาน และ <math>\mathrm{DFS}(u) \,</math> จบการทำงานก่อน <math>\mathrm{DFS}(v) \,</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> มีส่วนร่วมกัน
+# ถ้า <math>(u,v) \,</math> เป็น forward edge แล้ว เราสามารถใช้การให้เหตุผลในข้อ 1 แสดงได้ว่า ช่วง <math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และ <math>\mathrm{pre}[v], \mathrm{post}[v] \,</math> มีส่วนร่วมกันได้
+ทั้งสามกรณีให้ข้อสรุปว่า <math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และ <math>\mathrm{pre}[v], \mathrm{post}[v] \,</math> มีส่วนร่วมกัน กล่าวคือประพจน์ <math>Q \,</math> ไม่เป็นจริง
+ดังนั้นเราสามารถสรุปได้ว่าถ้า <math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และ <math>\mathrm{pre}[v], \mathrm{post}[v] \,</math> ไม่มีส่วนร่วมกันแล้ว <math>(u,v) \,</math> จะต้องเป็น cross edge

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

รุ่นแก้ไขปัจจุบันเมื่อ 13:44, 16 กันยายน 2552

กรณีที่ 1

กรณีที่ 2

กรณีที่ 3

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ