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

Aoy: /* ข้อย่อย 1 */

2009-10-06T10:12:10Z

ข้อย่อย 1

Aoy: /* ข้อย่อย 2 */

2009-09-30T06:05:27Z

ข้อย่อย 2

Aoy: /* ข้อย่อย 2 */

2009-09-30T05:54:00Z

ข้อย่อย 2

Aoy: /* ข้อย่อย 1 */

2009-09-21T14:00:32Z

ข้อย่อย 1

Aoy: หน้าที่ถูกสร้างด้วย '==ข้อย่อย 1 == เราจะทำการพิสูจน์โดยใช้ข้อสังเกตต่อไ…'

2009-09-21T13:56:48Z

หน้าที่ถูกสร้างด้วย '==ข้อย่อย 1 == เราจะทำการพิสูจน์โดยใช้ข้อสังเกตต่อไ…'

หน้าใหม่

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

สำหรับ edge <math> e \,</math> และ edge <math> e' \,</math> ในกราฟ ถ้า <math> c(e) < c(e') \,</math> แล้ว <math> c(e)^2 < c(e')^2 \,</math> ด้วย

''พิสูจน์:''
:จาก <math> c(e) < c(e') \,</math> ให้เป็นสมการที่ 1
:คูณสมการที่ 1 ทั้งสองข้างด้วย <math> c(e) \,</math> จะได้ <math> c(e)^2 < c(e')c(e) \,</math> ให้เป็นสมการที่ 2
:คูณสมการที่ 1 ทั้งสองข้างด้วย <math> c(e') \,</math> จะได้ <math> c(e)c(e') < c(e')^2 \,</math> ให้เป็นสมการที่ 3
:จากสมการที่ 2 และ 3 จะได้ <math> c(e)^2 < c(e')^2 \,</math> จริง

จะพิสูจน์ว่า minimum spanning tree <math> T \, </math> จากกราฟ <math> G \,</math> ที่ได้เป็น minimum spanning tree ของกราฟใหม่จริง

''พิสูจน์:'' จะพิสูจน์โดยข้อขัดแย้ง สมมติให้ <math> T \, </math> ไม่เป็น minimum spanning tree ของกราฟใหม่ ให้ minimum spanning tree ของกราฟใหม่เป็น <math> T' \,</math> แสดงว่า tree <math> T' \,</math> ต้องมี edge อย่างน้อยหนึ่ง edge ที่ไม่อยู่ใน <math> T \,</math> ให้ edge นั้นเป็น edge <math> e = \{ u,v \} \,</math> เมื่อเราลบ edge <math> e \,</math> นี้ออกจาก <math> T' \, </math> จะได้แบ่ง vertex ของกราฟออกเป็นสองส่วน ให้เป็นเซต <math> S \,</math> กับ <math> V - S \,</math> เนื่องจาก edge <math> e \, </math> เป็น edge ที่มีจุดปลายข้างหนึ่งในเซต <math> S \, </math> และปลายอีกข้างหนึ่งอยู่ใน <math> V - S \,</math> (เป็น edge ข้าม cut นั่นเอง) และ edge <math> e \, </math> นี้อยู่ใน minimum spanning tree <math> T' \,</math> ดังนั้น edge <math> e \, </math> ต้องมี cost น้อยที่สุดในบรรดา edge ข้าม cut <math> S \, </math> และ <math> V - S \, </math> นี้แล้ว หรือพูดอีกอย่างคือ <math> c(e) < c(e') \,</math> สำหรับ edge <math> e' \,</math> ใด ๆ ที่เป็น edge ข้าม cut และ <math> e \neq e' \,</math> ซึ่งจากข้อสังเกตข้างต้น เราจะได้ว่า <math> c(e)^2 < c(e')^2 \,</math> ด้วย และเนื่องจากโจทย์กำหนดให้ cost ของแต่ละ edge ในกราฟไม่ซ้ำกัน ดังนั้นในกราฟใหม่ edge <math> e \,</math> นี้ก็จะต้องถูกเพิ่มเข้าไปใน minimum spanning tree ด้วย เนื่องจากเป็น edge ข้าม cut ที่มี cost น้อยที่สุดแล้ว จึงเกิดข้อขัดแย้ง ดังนั้น mimimum spanning tree <math> T \,</math> ที่ได้จากกราฟ <math> G \,</math> จะเป็น minimum spanning tree ของกราฟใหม่ด้วย

==ข้อย่อย 2 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:05, 30 กันยายน 2552
แถว 16:		แถว 16:
	==ข้อย่อย 2 ==		==ข้อย่อย 2 ==
	ข้อความข้างต้นไม่จริง แสดงตัวอย่างขัดแย้งได้ดังต่อไปนี้		ข้อความข้างต้นไม่จริง แสดงตัวอย่างขัดแย้งได้ดังต่อไปนี้
		+
		+	[[ไฟล์:2_2.JPG]]
		+
		+	จากตัวอย่างข้างต้น กราฟทางซ้ายเป็นกราฟที่ให้มา จากกราฟจะได้ระยะทางที่สั้นที่สุดจาก <math> s \, </math> ไป <math> t \,</math> คือ edge ที่พุ่งจาก <math> s \, </math> ไปยัง <math> t \, </math> เลย ซึ่งมี cost เป็น 10 แต่เมื่อเอาค่า cost ของแต่ละ edge มายกกำลังสองแล้วจะได้ว่า ระยะทางจาก <math> s \,</math> ไป <math> t \,</math> จะเป็น <math> s \rightarrow a \rightarrow b \rightarrow t \,</math> ซึ่งมี cost เป็น 4+16+49 = 69 ซึ่งน้อยกว่า cost ของedge จาก <math> s \, </math> ไปยัง <math> t \,</math> ที่เคยเป็นระยะทางที่สั้นที่สุดจากกราฟตั้งต้น ซึ่งตอนนี้มี cost เป็น 100

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

	==ข้อย่อย 2 ==		==ข้อย่อย 2 ==
		+	ข้อความข้างต้นไม่จริง แสดงตัวอย่างขัดแย้งได้ดังต่อไปนี้

@@ แถว 9: / แถว 9: @@
 :คูณสมการที่ 1 ทั้งสองข้างด้วย <math> c(e') \,</math> จะได้ <math> c(e)c(e') < c(e')^2 \,</math> ให้เป็นสมการที่ 3 (เนื่องจาก cost ของทุก edge เป็นบวก)
 :จากสมการที่ 2 และ 3 จะได้ <math> c(e)^2 < c(e')^2 \,</math> จริง
 จะพิสูจน์ว่า minimum spanning tree <math> T \, </math> จากกราฟ <math> G \,</math> ที่ได้เป็น minimum spanning tree ของกราฟใหม่จริง
-''พิสูจน์:'' จะพิสูจน์โดยข้อขัดแย้ง สมมติให้ <math> T \, </math>  ไม่เป็น minimum spanning tree ของกราฟใหม่ ให้ minimum spanning tree ของกราฟใหม่เป็น <math> T' \,</math> แสดงว่า tree <math> T' \,</math> ต้องมี edge อย่างน้อยหนึ่ง edge ที่ไม่อยู่ใน <math> T \,</math> ให้ edge นั้นเป็น edge <math> e = \{ u,v \} \,</math> เมื่อเราลบ edge <math> e \,</math> นี้ออกจาก <math> T' \, </math> จะได้แบ่ง vertex ของกราฟออกเป็นสองส่วน ให้เป็นเซต <math> S \,</math> กับ <math> V - S \,</math> เนื่องจาก edge <math> e \, </math> เป็น edge ที่มีจุดปลายข้างหนึ่งในเซต <math> S \, </math> และปลายอีกข้างหนึ่งอยู่ใน <math> V - S \,</math> (เป็น edge ข้าม cut นั่นเอง) และ edge <math> e \, </math> นี้อยู่ใน minimum spanning tree <math> T' \,</math> ดังนั้น edge <math> e \, </math> ต้องมี cost น้อยที่สุดในบรรดา edge ข้าม cut <math> S \, </math> และ <math> V - S \, </math> นี้แล้ว หรือพูดอีกอย่างคือ <math> c(e) < c(e') \,</math> สำหรับ edge <math> e' \,</math> ใด ๆ ที่เป็น edge ข้าม cut และ <math> e \neq e' \,</math> ซึ่งจากข้อสังเกตข้างต้น เราจะได้ว่า <math> c(e)^2 < c(e')^2 \,</math> ด้วย และเนื่องจากโจทย์กำหนดให้ cost ของแต่ละ edge ในกราฟไม่ซ้ำกัน ดังนั้นในกราฟใหม่ edge <math> e \,</math> นี้ก็จะต้องถูกเพิ่มเข้าไปใน minimum spanning tree ด้วย เนื่องจากเป็น edge ข้าม cut ที่มี cost น้อยที่สุดแล้ว  จึงเกิดข้อขัดแย้ง ดังนั้น mimimum spanning tree <math> T \,</math> ที่ได้จากกราฟ <math> G \,</math> จะเป็น minimum spanning tree ของกราฟใหม่ด้วย
+ดังนั้นต้องทำการพิสูจน์ว่าสำหรับทุก ๆ edge <math> e={a,b}\,</math> ใน minimum spanning tree <math> T\,</math> นั้น edge <math> e \,</math> ดังกล่าวจะต้องเป็นเป็น edge ใน minmimum spanning tree ต้นหนึ่งของกราฟ <math> G' \, </math> ด้วย
 ==ข้อย่อย 2 ==