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

Cardcaptor เมื่อ 13:44, 16 กันยายน 2552

2009-09-16T13:44:42Z

Cardcaptor: /* กรณีที่ 3 */

2009-09-16T12:37:49Z

กรณีที่ 3

Cardcaptor: /* กรณีที่ 3 */

2009-09-16T12:36:00Z

กรณีที่ 3

Cardcaptor: /* กรณีที่ 2 */

2009-09-16T12:14:41Z

กรณีที่ 2

Cardcaptor เมื่อ 11:43, 16 กันยายน 2552

2009-09-16T11:43:02Z

Cardcaptor เมื่อ 11:21, 16 กันยายน 2552

2009-09-16T11:21:09Z

Cardcaptor เมื่อ 11:08, 16 กันยายน 2552

2009-09-16T11:08:55Z

Cardcaptor: /* กรณีที่ 1 */

2009-09-16T10:58:51Z

กรณีที่ 1

Cardcaptor: /* กรณีที่ 1 */

2009-09-16T10:58:27Z

กรณีที่ 1

Cardcaptor: /* กรณีที่ 1 */

2009-09-16T10:58:11Z

กรณีที่ 1

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

@@ แถว 61: / แถว 61: @@
 สมมติให้ <math>X \vee Y \vee Z \,</math> เป็นจริง กล่าวคือ <math>(u,v) \,</math> เป็น tree, back, หรือ forward edge เราจะได้ว่า
-# ถ้า <math>(u,v) \,</math> เป็น tree edge แล้ว เราจะได้ว่า <math>\mathrm{DFSALL}(v) \,</math> ถูกเรียกหลัง <math>\mathrm{DFSALL}(u) \,</math> เริ่มทำงาน
+# ถ้า <math>(u,v) \,</math> เป็น tree edge แล้ว เราจะได้ว่า <math>\mathrm{DFSALL}(v) \,</math> ถูกเรียกหลัง <math>\mathrm{DFSALL}(u) \,</math> เริ่มทำงาน และ <math>\mathrm{DFSALL}(v) \,</math> จบการทำงานก่อน <math>\mathrm{DFSALL}(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>\mathrm{DFSALL}(v) \,</math> จบการทำงานก่อน <math>\mathrm{DFSALL}(u) \,</math> จะจบการทำงาน ดังนั้น
+# ถ้า <math>(u,v) \,</math> เป็น back edge แล้ว เราจะได้ว่า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> ใน DFS tree ดังนั้น <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียกหลัง <math>\mathrm{DFSALL}(v) \,</math> เริ่มทำงาน และ <math>\mathrm{DFSALL}(u) \,</math> จบการทำงานก่อน <math>\mathrm{DFSALL}(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>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</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}[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>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และ <math>\mathrm{pre}[v], \mathrm{post}[v] \,</math> ไม่มีส่วนร่วมกันแล้ว <math>(u,v) \,</math> จะต้องเป็น cross edge

@@ แถว 66: / แถว 66: @@
 กล่าวคือช่วง <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{DFSALL}(u) \,</math> ถูกเรียกหลัง <math>\mathrm{DFSALL}(v) \,</math> เริ่มทำงาน
@@ แถว 73: / แถว 72: @@
 กล่าวคือช่วง <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> มีส่วนร่วมกันได้

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:14, 16 กันยายน 2552
แถว 38:		แถว 38:

	ดังนั้น <math>(u,v) \,</math> จึงเป็น back edge		ดังนั้น <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{DFSALL}(v) \,</math> ถูกเรียกหลัง <math>\mathrm{DFSALL}(u) \,</math> เริ่มทำงาน
		+	และ <math>\mathrm{DFSALL}(v) \,</math> จบการทำงานก่อน <math>\mathrm{DFSALL}(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{DFSALL}(u) \,</math> ถูกเรียกหลัง <math>\mathrm{DFSALL}(v) \,</math> เริ่มทำงาน
		+	และ <math>\mathrm{DFSALL}(u) \,</math> จบการทำงานก่อน <math>\mathrm{DFSALL}(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

@@ แถว 8: / แถว 8: @@
 '''พิสูจน์:''' เนื่องจาก <math>\mathrm{DFSALL}(v) \,</math> ถูกเรียกให้ทำงานระหว่างที่ <math>\mathrm{DFSALL}(u) \,</math> ทำงานไปแล้วแต่ยังทำให้เสร็จ
 เราจะได้ว่ามีลำดับของ vertex <math>u_1, u_2, \ldots, u_k \,</math> โดยที่ <math>k \geq 0 \,</math> โดยที่ <math>\mathrm{DFSALL}(u) \,</math> เรียก
-<math>\mathrm{DFSALL}(u_1) \,</math> แล้ว <math>\mathrm{DFSALL}(u_1) \,</math> เรียก <math>\mathrm{DFSALL}(u_/) \,</math> เช่นนี้ไปเรื่อยๆ จนกระทั้ง
+<math>\mathrm{DFSALL}(u_1) \,</math> แล้ว <math>\mathrm{DFSALL}(u_1) \,</math> เรียก <math>\mathrm{DFSALL}(u_2) \,</math> เช่นนี้ไปเรื่อยๆ จนกระทั้ง
 <math>\mathrm{DFSALL}(u_k) \,</math> เรียก <math>\mathrm{DFSALL}(v) \,</math>
@@ แถว 19: / แถว 19: @@
 จะต้องเป็น 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{DFSALL}(u) \,</math> เริ่มทำงานก่อน
-เนื่องจาก <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math> เรารู้ว่า DFSALL(v) ถูกเรียกก่อนที่ DFSALL(u) จะทำงานเสร็จ
+<math>\mathrm{DFSALL}(v) \,</math> เนื่องจาก <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math>
-ฉะนั้นจะต้องมี path ใน DFS tree จาก <math>u \,</math> ถึง <math>v \,</math>
+ฉะนั้นจะต้องมี path ใน DFS tree จาก <math>u \,</math> ถึง <math>v \,</math> กล่าวคือ <math>v \,</math> เป็นลูกหลานของ <math>u \,</math>
 ดังนั้น <math>(u,v) \,</math> จึงเป็น tree edge หรือไม่ก็ forward edge

@@ แถว 1: / แถว 1: @@
 == กรณีที่ 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