204512/บรรยาย 8 - ประวัติรุ่นแก้ไข

158.108.236.191: /* Unit Network */

2007-10-08T11:08:43Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T10:48:28Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T10:47:48Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T10:41:11Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T10:10:16Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T10:02:10Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T10:01:37Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T09:58:56Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T09:45:21Z

Unit Network

158.108.236.191: /* Unit Network */

2007-10-08T09:45:07Z

Unit Network

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 11:08, 8 ตุลาคม 2550
แถว 98:		แถว 98:

	เนื่องจาก <math>f\,</math> เป็นจำนวนเต็ม, <math>R\,</math> เป็น unit network, <math>f^-f\,</math> จะต้องเป็น 0 หรือ 1 บนทุกๆ edge ดังนั้น เราสามารถแบ่ง edge ที่ <math>f^-f\,</math> เป็น 1 ให้เป็นกลุ่มของ path จาก <math>s</math> ไปยัง <math>t</math> จำนวน <math>\|f^*\|-\|f\|\,</math> path (อาจมี cycle)		เนื่องจาก <math>f\,</math> เป็นจำนวนเต็ม, <math>R\,</math> เป็น unit network, <math>f^-f\,</math> จะต้องเป็น 0 หรือ 1 บนทุกๆ edge ดังนั้น เราสามารถแบ่ง edge ที่ <math>f^-f\,</math> เป็น 1 ให้เป็นกลุ่มของ path จาก <math>s</math> ไปยัง <math>t</math> จำนวน <math>\|f^*\|-\|f\|\,</math> path (อาจมี cycle)
		+
		+	เนื่องจาก <math>R\,</math> เป็น unit แต่ละ node ที่ไม่ใช่ <math>s</math> หรือ <math>t</math> จะอยู่บน path ได้ไม่เกิน 1 path ซึ่งแสดงว่า <math>f\,</math> จะมี augmenting path ที่มีความยาวไม่เกิน <math>(n-2)/(\|f^*\|-\|f\|)+1\,</math>
		+
		+	หลังจาก <math>\lceil\sqrt{n-2}\rceil</math> blocking step, augmenting path ที่สั้นที่สุดจะประกอบด้วย edge อย่างน้อย <math>\sqrt{n-2}+1</math> edge (จาก Theorem 8.6) ดังนั้น <math>\sqrt{n-2}+1 \le (n-1)/(\|f^\|-\|f\|)+1\,</math> โดยที่ <math>\|f^\|-\|f\| \le \sqrt{n-2}</math> จึงสรุปได้ว่า หลังจาก <math>\lfloor \sqrt{n-2} \rfloor</math> blocking step flow ที่ได้จะเป็น max flow
	{{end-pf}}		{{end-pf}}

@@ แถว 97: / แถว 97: @@
 ''Proof'': พิจารณา blocking step ให้ <math>f\,</math> เป็น flow ปัจจุบัน, <math>f^*\,</math> เป็น maximum flow, และ <math>R\,</math> เป็น residual graph ของ <math>f\,</math> ดังนั้น <math>f^*-f\,</math> จะต้องเป็น flow บน <math>R\,</math>
-เนื่องจาก <math>f\,</math> เป็นจำนวนเต็ม, <math>R\,</math> เป็น unit network, <math>f^*-f\,</math> จะต้องเป็น 0 หรือ 1 บนทุกๆ edge ดังนั้น เราสามารถแบ่ง edge ที่ <math>f^*-f\,</math> เป็น 1 ให้เป็นกลุ่มของ path จาก <math>s</math> ไปยัง <math>t</math> จำนวน <math>|f^*|-|f|\,</math> path
+เนื่องจาก <math>f\,</math> เป็นจำนวนเต็ม, <math>R\,</math> เป็น unit network, <math>f^*-f\,</math> จะต้องเป็น 0 หรือ 1 บนทุกๆ edge ดังนั้น เราสามารถแบ่ง edge ที่ <math>f^*-f\,</math> เป็น 1 ให้เป็นกลุ่มของ path จาก <math>s</math> ไปยัง <math>t</math> จำนวน <math>|f^*|-|f|\,</math> path (อาจมี cycle)
 {{end-pf}}

@@ แถว 97: / แถว 97: @@
 ''Proof'': พิจารณา blocking step ให้ <math>f\,</math> เป็น flow ปัจจุบัน, <math>f^*\,</math> เป็น maximum flow, และ <math>R\,</math> เป็น residual graph ของ <math>f\,</math> ดังนั้น <math>f^*-f\,</math> จะต้องเป็น flow บน <math>R\,</math>
-เนื่องจาก <math>f\,</math> เป็นจำนวนเต็ม, <math>R\,</math> เป็น unit network, <math>f^*-f\,</math> จะต้องเป็น 0 หรือ 1 บนทุกๆ edge
+เนื่องจาก <math>f\,</math> เป็นจำนวนเต็ม, <math>R\,</math> เป็น unit network, <math>f^*-f\,</math> จะต้องเป็น 0 หรือ 1 บนทุกๆ edge ดังนั้น เราสามารถแบ่ง edge ที่ <math>f^*-f\,</math> เป็น 1 ให้เป็นกลุ่มของ path จาก <math>s</math> ไปยัง <math>t</math> จำนวน <math>|f^*|-|f|\,</math> path
 {{end-pf}}

@@ แถว 95: / แถว 95: @@
 {{begin-pf}}
-''Proof'': พิจารณา blocking step ให้ <math>f\,</math> เป็น flow ปัจจุบัน, <math>f^*\,</math> เป็น maximum flow, และ <math>R\,</math> เป็น residual graph ของ <math>f\,</math> ดังนั้น <math>f^*-f\,</math> จะต้องเป็น flow บน <math>R\,</math> เนื่องจาก <math>f\,</math> เป็นจำนวนเต็ม, <math>R\,</math> เป็น unit network, <math>f^*-f\,</math> จะต้องเป็น 0 หรือ 1 บนทุกๆ edge
+''Proof'': พิจารณา blocking step ให้ <math>f\,</math> เป็น flow ปัจจุบัน, <math>f^*\,</math> เป็น maximum flow, และ <math>R\,</math> เป็น residual graph ของ <math>f\,</math> ดังนั้น <math>f^*-f\,</math> จะต้องเป็น flow บน <math>R\,</math>
 {{end-pf}}

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:10, 8 ตุลาคม 2550
แถว 93:		แถว 93:

	{{thm-box\|;Theorem 8.8 : สำหรับ unit network อัลกอริทึมของ Dinic จะทำ blocking step ไม่เกิน <math>O(\sqrt n)</math> ครั้ง}}		{{thm-box\|;Theorem 8.8 : สำหรับ unit network อัลกอริทึมของ Dinic จะทำ blocking step ไม่เกิน <math>O(\sqrt n)</math> ครั้ง}}
		+
		+	{{begin-pf}}
		+	''Proof'': พิจารณา blocking step ให้ <math>f\,</math> เป็น flow ปัจจุบัน, <math>f^\,</math> เป็น maximum flow, และ <math>R\,</math> เป็น residual graph ของ <math>f\,</math> ดังนั้น <math>f^-f\,</math> จะต้องเป็น flow บน <math>R\,</math> เนื่องจาก <math>f\,</math> เป็นจำนวนเต็ม, <math>R\,</math> เป็น unit network, <math>f^*-f\,</math> จะต้องเป็น 0 หรือ 1 บนทุกๆ edge
		+	{{end-pf}}

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:02, 8 ตุลาคม 2550
แถว 92:		แถว 92:
	#มี edge ชี้ออกเพียง edge เดียว โดยมีความจุเท่ากับ 1		#มี edge ชี้ออกเพียง edge เดียว โดยมีความจุเท่ากับ 1

−	{{thm-box\|;Theorem 8.8 : สำหรับ unit network อัลกอริทึมของ Dinic จะทำ blocking step ไม่เกิน <math>O(\~~sqr(~~n))</math> ครั้ง}}	+	{{thm-box\|;Theorem 8.8 : สำหรับ unit network อัลกอริทึมของ Dinic จะทำ blocking step ไม่เกิน <math>O(\sqrt n)</math> ครั้ง}}

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:01, 8 ตุลาคม 2550
แถว 91:		แถว 91:
	#มี edge ชี้เข้าเพียง edge เดียว โดยมีความจุเท่ากับ 1 หรือ		#มี edge ชี้เข้าเพียง edge เดียว โดยมีความจุเท่ากับ 1 หรือ
	#มี edge ชี้ออกเพียง edge เดียว โดยมีความจุเท่ากับ 1		#มี edge ชี้ออกเพียง edge เดียว โดยมีความจุเท่ากับ 1
		+
		+	{{thm-box\|;Theorem 8.8 : สำหรับ unit network อัลกอริทึมของ Dinic จะทำ blocking step ไม่เกิน <math>O(\sqr(n))</math> ครั้ง}}

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:58, 8 ตุลาคม 2550
แถว 88:		แถว 88:
	===Unit Network===		===Unit Network===

−	ในกราฟที่มีลักษณะพิเศษบางกรณี อัลกอริทึมของ Dinic สามารถทำงานได้มีประสิทธิภาพมากกว่าใน Theorem 8.7	+	ในกราฟที่มีลักษณะพิเศษบางกรณี อัลกอริทึมของ Dinic สามารถทำงานได้มีประสิทธิภาพมากกว่าใน Theorem 8.7 (ใช้จำนวนรอบดีกว่า Theorem 8.6) เช่นใน unit network ซึ่งทุกๆ edge จะมีความจุเป็นจำนวนเต็ม โดย แต่ละ node <math>v</math> ที่ไม่ใช่ <math>s</math> หรือ <math>t</math> <math>v</math> จะต้องเป็นหนึ่งในสองกรณีต่อไปนี้
		+	#มี edge ชี้เข้าเพียง edge เดียว โดยมีความจุเท่ากับ 1 หรือ
		+	#มี edge ชี้ออกเพียง edge เดียว โดยมีความจุเท่ากับ 1

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:45, 8 ตุลาคม 2550
แถว 88:		แถว 88:
	===Unit Network===		===Unit Network===

−	ในกราฟที่มีลักษณะพิเศษบางกรณี อัลกอริทึมของ Dinic สามารถทำงานได้มีประสิทธิภาพมากกว่าใน Theorem 8.4	+	ในกราฟที่มีลักษณะพิเศษบางกรณี อัลกอริทึมของ Dinic สามารถทำงานได้มีประสิทธิภาพมากกว่าใน Theorem 8.7

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:45, 8 ตุลาคม 2550
แถว 87:		แถว 87:

	===Unit Network===		===Unit Network===
		+
		+	ในกราฟที่มีลักษณะพิเศษบางกรณี อัลกอริทึมของ Dinic สามารถทำงานได้มีประสิทธิภาพมากกว่าใน Theorem 8.4