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

158.108.183.136: /* ข้อ 9 */

2009-09-16T10:05:15Z

ข้อ 9

2009-09-16T04:46:02Z

ข้อย่อย 6.2

2009-09-16T04:23:20Z

ข้อย่อย 6.2

2009-09-09T10:31:29Z

ข้อย่อย 4.3

2009-09-09T10:31:14Z

ข้อย่อย 4.4

2009-09-09T10:31:00Z

ข้อย่อย 4.5

2009-09-09T10:30:39Z

ข้อย่อย 6.1

2009-09-09T10:30:19Z

ข้อย่อย 6.3

2009-09-09T10:29:59Z

ข้อ 9

2009-09-09T10:29:36Z

ข้อ 8

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

	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 8\|เฉลย]]		[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 8\|เฉลย]]
−
−	~~== ข้อ 9 ==~~
−	~~[Dasgupta, Papadimitriou, Vazirani 3.20] จงออกแบบอัลกอริทึีมเพื่อแก้ป้ญหาต่อไปนี้~~
−
−	: เมื่อกำหนด directed graph <math>G = (V,E) \,</math> ให้ แล้วคำนวณหา vertex <math>s \,</math> ที่เราสามารถเดินจาก <math>s \,</math> ไปยัง vertex อื่นๆ ทุก vertex ได้ทั้งหมด
−
−	~~อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(\|V\|+\|E\|) \,</math>~~
−
−	~~[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 9\|เฉลย]]~~

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:46, 16 กันยายน 2552
แถว 125:		แถว 125:
	จากกราฟต่อไปนี้		จากกราฟต่อไปนี้

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

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

@@ แถว 123: / แถว 123: @@
 สำหรับ 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>
-จงหา topological ordering ในกราฟที่อยู่ในโจทย์ข้อ 4.1 มาสักหนึ่ง ordering
+จากกราฟต่อไปนี้
 [[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.2|เฉลย]]

@@ แถว 91: / แถว 91: @@
 # <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> ไม่มีสมาชิกร่วมกันเลย
 === ข้อย่อย 4.4 ===

@@ แถว 97: / แถว 97: @@
 * ถ้า <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
 === ข้อย่อย 4.5 ===

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

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

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:29, 9 กันยายน 2552
แถว 161:		แถว 161:

	อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(\|V\|+\|E\|) \,</math>		อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(\|V\|+\|E\|) \,</math>
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 9\|เฉลย]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:29, 9 กันยายน 2552
แถว 152:		แถว 152:

	จงออกแบบอัลกอริทึมเพื่อคำนวนอะเรย์ <math>z[\cdot] \,</math> ซึ่งทำงานได้ในเวลา <math>O(\|V\| + \|E\|) \,</math>		จงออกแบบอัลกอริทึมเพื่อคำนวนอะเรย์ <math>z[\cdot] \,</math> ซึ่งทำงานได้ในเวลา <math>O(\|V\| + \|E\|) \,</math>
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 8\|เฉลย]]

	== ข้อ 9 ==		== ข้อ 9 ==