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

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

2009-09-16T13:45:12Z

Cardcaptor เมื่อ 12:35, 16 กันยายน 2552

2009-09-16T12:35:31Z

Cardcaptor เมื่อ 12:35, 16 กันยายน 2552

2009-09-16T12:35:10Z

Cardcaptor เมื่อ 12:34, 16 กันยายน 2552

2009-09-16T12:34:40Z

Cardcaptor เมื่อ 12:33, 16 กันยายน 2552

2009-09-16T12:33:51Z

Cardcaptor เมื่อ 12:32, 16 กันยายน 2552

2009-09-16T12:32:29Z

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ให้่ $\{u,v\} \,$ เป็น edge ใดๆ ใน undirected graph $G = (V,E) \,$ โจทย์ต้…'

2009-09-16T12:32:17Z

หน้าที่ถูกสร้างด้วย 'ให้่ <math>\{u,v\} \,</math> เป็น edge ใดๆ ใน undirected graph <math>G = (V,E) \,</math> โจทย์ต้…'

หน้าใหม่

ให้่ <math>\{u,v\} \,</math> เป็น edge ใดๆ ใน undirected graph <math>G = (V,E) \,</math>

โจทย์ต้องการให้เราพิสูจน์ว่า edge <math>\{u,v\} \,</math> เป็น tree edge หรือไม่ก็ back edge

นั่นคือเท่ากับพิสูจน์ว่า "ถ้า <math>\{u,v\} \,</math> ไม่เป็น tree edge แล้วมันต้องเป็น back edge"

ดังนั้นเราสมมติว่า <math>\{u,v\} \,</math> ไม่เป็น tree edge

สมมติเพื่อไม่ให้เสียนัยทั่วไปว่า <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียกก่อน <math>\mathrm{DFSALL}(v) \,</math>
(ถ้า <math>\mathrm{DFSALL}(v) \,</math> ถูกเรียกก่อนเราก็แค่สลับ <math>u \,</math> กับ <math>v \,</math>)

เมื่อ <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียกให้ทำงาน มันจะจบการทำงานก็ต่อเมื่อ <math>DFSALL \,</math> ได้เข้าไปสำรวจ vertex ทุก vertex
ที่ยังไม่เคยถูกสำรวจซึ่งเราสามารถเดินไปถึงจาก <math>u \,</math> ได้

เนื้่องจากมี edge <math>\{u,v\} \,</math> เราได้ว่าเราสามารถเดินจาก <math>u \,</math> ไปถึง <math>v \,</math> ได้

แต่ ณ เวลาที่ <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียก <math>\mathrm{DFSALL}(v) \,</math> ยังไม่ถูกเรียก เพราะฉะนั้น ณ เวลานั้น <math>v \,</math>
ยังไม่ถูกสำรวจ

ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree

เนื่องจาก edge <math>\{u,v} \,</math> ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ <math>u \,</math> เข้ากับ <math>u \,</math>

@@ แถว 7: / แถว 7: @@
 ดังนั้นเราสมมติว่า <math>\{u,v\} \,</math> ไม่เป็น tree edge
-สมมติเพิ่มเพื่อไม่ให้เสียนัยทั่วไปว่า <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียกก่อน <math>\mathrm{DFSALL}(v) \,</math>
+สมมติเพิ่มเพื่อไม่ให้เสียนัยทั่วไปว่า <math>\mathrm{DFS}(u) \,</math> ถูกเรียกก่อน <math>\mathrm{DFS}(v) \,</math>
-(ถ้า <math>\mathrm{DFSALL}(v) \,</math> ถูกเรียกก่อนเราก็แค่สลับ <math>u \,</math> กับ <math>v \,</math>)
+(ถ้า <math>\mathrm{DFS}(v) \,</math> ถูกเรียกก่อนเราก็แค่สลับ <math>u \,</math> กับ <math>v \,</math>)
-'''ข้อสังเกต:''' เมื่อ <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียกให้ทำงาน มันจะจบการทำงานก็ต่อเมื่อ <math>\mathrm{DFSALL} \,</math> ได้เข้าไปสำรวจ vertex ทุก vertex
+'''ข้อสังเกต:''' เมื่อ <math>\mathrm{DFS}(u) \,</math> ถูกเรียกให้ทำงาน มันจะจบการทำงานก็ต่อเมื่อ <math>\mathrm{DFS} \,</math> ได้เข้าไปสำรวจ vertex ทุก vertex
 ที่ยังไม่เคยถูกสำรวจซึ่งเราสามารถเดินไปถึงจาก <math>u \,</math> ได้
 เนื่องจากมี edge <math>\{u,v\} \,</math> ดังนั้นเราสามารถเดินจาก  <math>u \,</math> ไปถึง <math>v \,</math> ได้
-แต่ ณ เวลาที่ <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียก <math>\mathrm{DFSALL}(v) \,</math> ยังไม่ถูกเรียก เพราะฉะนั้น ณ เวลานั้น <math>v \,</math>
+แต่ ณ เวลาที่ <math>\mathrm{DFS}(u) \,</math> ถูกเรียก <math>\mathrm{DFS}(v) \,</math> ยังไม่ถูกเรียก เพราะฉะนั้น ณ เวลานั้น <math>v \,</math>
 ยังไม่ถูกสำรวจ

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:35, 16 กันยายน 2552
แถว 20:		แถว 20:
	ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree		ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree

−	edge <math>\{u,v\} \,</math> ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ <math>u \,</math> ~~เข้ากับ~~ <math>u \,</math>	+	edge <math>\{u,v\} \,</math> ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ <math>u \,</math> เข้ากับตัว <math>u \,</math> เอง

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:35, 16 กันยายน 2552
แถว 20:		แถว 20:
	ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree		ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree

−	~~เนื่องจาก~~ edge <math>\{u,v\} \,</math> ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ <math>u \,</math> เข้ากับ <math>u \,</math>	+	edge <math>\{u,v\} \,</math> ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ <math>u \,</math> เข้ากับ <math>u \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:32, 16 กันยายน 2552
แถว 20:		แถว 20:
	ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree		ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree

−	เนื่องจาก edge <math>\{u,v} \,</math> ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ <math>u \,</math> เข้ากับ <math>u \,</math>	+	เนื่องจาก edge <math>\{u,v\} \,</math> ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ <math>u \,</math> เข้ากับ <math>u \,</math>

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

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

Cardcaptor เมื่อ 12:35, 16 กันยายน 2552

Cardcaptor เมื่อ 12:35, 16 กันยายน 2552

Cardcaptor เมื่อ 12:34, 16 กันยายน 2552

Cardcaptor เมื่อ 12:33, 16 กันยายน 2552

Cardcaptor เมื่อ 12:32, 16 กันยายน 2552

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ให้่ \{u,v\} \, เป็น edge ใดๆ ใน undirected graph G = (V,E) \, โจทย์ต้…'

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ให้่ $\{u,v\} \,$ เป็น edge ใดๆ ใน undirected graph $G = (V,E) \,$ โจทย์ต้…'