Cardcaptor เมื่อ 15:42, 18 กันยายน 2552

2009-09-18T15:42:52Z

Cardcaptor: หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == ไม่จริง พิจารณากราฟข้างล่างและต้นไม้…'

2009-09-18T15:38:22Z

หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == ไม่จริง พิจารณากราฟข้างล่างและต้นไม้…'

หน้าใหม่

== ข้อย่อย 1 ==
ไม่จริง พิจารณากราฟข้างล่างและต้นไม้ต้นต่อไปนี้

[[Image:Minimum-bottleneck-spanning-tree-counterexample.JPG‎]]

เราได้ว่า <math>T \,</math> เป็น minimum bottleneck spanning tree ของ <math>G \,</math> เนื่องจาก spanning tree ทุกต้นต้องมี edge ที่มี cost เท่ากับ 3 แต่ <math>T \,</math> ไม่ใช่ minimum spanning tree เนื่องจากมันไม่มี edge ที่มี weight 1

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:42, 18 กันยายน 2552
แถว 4:		แถว 4:
	[[Image:Minimum-bottleneck-spanning-tree-counterexample.JPG‎]]		[[Image:Minimum-bottleneck-spanning-tree-counterexample.JPG‎]]

−	เราได้ว่า <math>T \,</math> เป็น minimum bottleneck spanning tree ของ <math>G \,</math> เนื่องจาก spanning tree ทุกต้นต้องมี edge ที่มี cost เท่ากับ 3 แต่ <math>T \,</math> ไม่ใช่ minimum spanning tree เนื่องจากมันไม่มี edge ที่มี weight 1	+	เราได้ว่า <math>T \,</math> เป็น minimum-bottleneck spanning tree ของ <math>G \,</math> เนื่องจาก spanning tree ทุกต้นต้องมี edge ที่มี cost เท่ากับ 3 แต่ <math>T \,</math> ไม่ใช่ minimum spanning tree เนื่องจากมันไม่มี edge ที่มี weight 1
		+
		+	== ข้อย่อย 2 ==
		+	จริง
		+
		+	ให้ <math>T \,</math> เป็น minimum spannning tree สมมติเพื่อให้เกิดข้อขัดแย้งว่ามันไม่ใช่ minimum-bottleneck spanning tree กล่าวคือมันมี edge <math>e \,</math> ที่มี cost มากกว่า bottleneck edge ของ minimum-bottleneck spanning tree
		+
		+	สมมติให้ <math>T' \,</math> เป็น minimum-bottleneck spanning tree ต้นหนึ่ง เราได้ว่า cost ของ edge ทุก edge ใน <math>T' \,</math> จะมีค่าน้อยกว่า cost ของ edge <math>e \,</math> ดังนั้น เมื่อเราเพิ่ม <math>e \,</math> เข้าไปใน <math>T' \,</math> มันจะทำให้เกิด cycle ขึ้นหนึ่ง cycle และเรายังทราบอีกว่า <math>e \,</math> จะเป็น edge ที่มี cost มากที่สุดใน cycle นั้น จาก cycle property เราทราบว่า <math>e \,</math> จะต้องไม่เป็นสมาชิกของ minimum spanning tree ต้นใดเลย เกิดข้อขัดแย้ง

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

Cardcaptor เมื่อ 15:42, 18 กันยายน 2552

Cardcaptor: หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == ไม่จริง พิจารณากราฟข้างล่างและต้นไม้…'