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

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

2009-09-30T07:15:39Z

ข้อย่อย 2

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

2009-09-30T06:43:25Z

ข้อย่อย 2

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

2009-09-30T06:26:37Z

ข้อย่อย 1

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

2009-09-30T06:21:19Z

ข้อย่อย 1

Aoy: หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == == ข้อย่อย 2 =='

2009-09-30T06:06:45Z

หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == == ข้อย่อย 2 =='

หน้าใหม่

== ข้อย่อย 1 ==

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

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

	== ข้อย่อย 2 ==		== ข้อย่อย 2 ==
−	จากอัลกอริทึมในข้อย่อย 1 เราจะได้ว่าถ้า <math> T \,</math> ไม่เป็น minimum spanning tree อีกต่อไป เราก็จะทำการหา edge ที่มี cost มากที่สุดใน cycle แล้วลบ edge นั้นทิ้งไป ~~ให้ tree ต้นใหม่ที่ได้เป็น~~ <math> T' \,</math> จะได้ว่าจำนวน edge ที่เหลือใน <math> T' \,</math> คือ <math> \|V\| - 1 \,</math> ~~เนื่องจากเดิม~~ <math> T \,</math> ~~เป็น connected graph ที่มี <math> \|V\| \,</math> การลบ~~ edge ที่อยู่ใน cycle ~~ทิ้งไปหนึ่ง~~ edge ~~ยังทำให้~~ <math> T' \,</math> ~~เป็น connected graph เหมือนเดิม ดังนั้น~~ <math> T' \,</math> นี้เป็น tree และ เป็น tree ที่ span ไปทุก ๆ vertex ของ <math> G \,</math> เนื่องจาก สมมติให้ edge ที่มี cost มากที่สุดใน cycle ที่เราลบไปคือ edge <math> e'=(x,y) \,</math> เนื่องจากก่อนหน้านี้เราเคยมี path จาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ โดยผ่าน edge <math> e' \,</math> นี้ แต่หลังจากลบ edge <math> e' \,</math> ออกไปแล้ว เราก็ยังสามารถเดินทางจาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ โดยการเดินทาง โดยอ้อมจาก <math> x \,</math> ไปหาโหนดที่เชื่อมกับ <math> x \, </math> ให้ โหนดนี้เป็น <math> z \,</math> หลังจากนั้นจาก <math> z \,</math> ไปยัง vertex ที่เชื่อมกับ <math> z \,</math> และเนื่องจาก <math> T \,</math> ~~จะเป็นกราฟเชื่อมโยง~~ ดังนั้นต้องมีทางจาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ใน <math> T' \,</math> ดังนั้น <math> T' \,</math> เป็น spanning tree และ เป็น spanning tree ที่มี cost น้อยที่สุดด้วย เพราะก่อนหน้าที่จะลบ edge <math> e' \,</math> ออกจาก <math> G \,</math> นั้น <math> G \,</math> มี cycle แค่ตัวเดียว และเราทำการลบ edge ที่มี cost มากที่สุดใน cycle ออกไปแล้ว ดังนั้นเราจึงสามารถสรุปได้ว่า <math> T' \,</math> ที่ได้เป็น minimum spanning tree แล้ว	+	เพื่อความง่ายในการอธิบายจะเรียก minimum spanning tree <math> T \,</math> ที่เพิ่ม edge <math> e=(v,w) \,</math> เข้าไปใน <math> G \,</math> นี้ว่ากราฟ <math> T' \,</math> จากอัลกอริทึมในข้อย่อย 1 เราจะได้ว่าถ้า <math> T' \,</math> ไม่เป็น minimum spanning tree อีกต่อไป เราก็จะทำการหา edge ที่มี cost มากที่สุดใน cycle ในกราฟ <math> T' \,</math> แล้วลบ edge นั้นทิ้งไป ให้กราฟใหม่ที่ได้เป็น <math> T'' \,</math> จะได้ว่าจำนวน edge ที่เหลือใน <math> T'' \,</math> คือ <math> \|V\| - 1 \,</math> และเนื่องจากเดิม <math> T' \,</math> มี cycle แค่ตัวเดียว และตอนนี้เราได้ลบ edge ที่อยู่ใน cycle นั้นทิ้งไปหนึ่ง edge แล้ว ดังนั้น <math> T'' \,</math> จึงไม่มี cycle เราจึงสามารถสรุปได้ว่า <math> T'' \,</math> นี้เป็น tree และ เป็น tree ที่ span ไปทุก ๆ vertex ของ <math> G \,</math> เนื่องจาก สมมติให้ edge ที่มี cost มากที่สุดใน cycle ที่เราลบไปคือ edge <math> e'=(x,y) \,</math> เนื่องจากก่อนหน้านี้เราเคยมี path จาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ โดยผ่าน edge <math> e' \,</math> นี้ แต่หลังจากลบ edge <math> e' \,</math> ออกไปแล้ว เราก็ยังสามารถเดินทางจาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ โดยการเดินทาง โดยอ้อมจาก <math> x \,</math> ไปหาโหนดที่เชื่อมกับ <math> x \, </math> ให้ โหนดนี้เป็น <math> z \,</math> หลังจากนั้นจาก <math> z \,</math> ไปยัง vertex ที่เชื่อมกับ <math> z \,</math> และเนื่องจาก <math> T'' \,</math> เป็นกราฟเชื่อมโยง ดังนั้นต้องมีทางจาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ใน <math> T'' \,</math> ดังนั้น <math> T'' \,</math> เป็น spanning tree และ เป็น spanning tree ที่มี cost น้อยที่สุดด้วย เพราะก่อนหน้าที่จะลบ edge <math> e' \,</math> ออกจาก <math> T' \,</math> นั้น <math> T' \,</math> มี cycle แค่ตัวเดียว และเราทำการลบ edge ที่มี cost มากที่สุดใน cycle ออกไปแล้ว ดังนั้นเราจึงสามารถสรุปได้ว่า <math> T'' \,</math> ที่ได้เป็น minimum spanning tree แล้ว

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

	== ข้อย่อย 2 ==		== ข้อย่อย 2 ==
		+	จากอัลกอริทึมในข้อย่อย 1 เราจะได้ว่าถ้า <math> T \,</math> ไม่เป็น minimum spanning tree อีกต่อไป เราก็จะทำการหา edge ที่มี cost มากที่สุดใน cycle แล้วลบ edge นั้นทิ้งไป ให้ tree ต้นใหม่ที่ได้เป็น <math> T' \,</math> จะได้ว่าจำนวน edge ที่เหลือใน <math> T' \,</math> คือ <math> \|V\| - 1 \,</math> เนื่องจากเดิม <math> T \,</math> เป็น connected graph ที่มี <math> \|V\| \,</math> การลบ edge ที่อยู่ใน cycle ทิ้งไปหนึ่ง edge ยังทำให้ <math> T' \,</math> เป็น connected graph เหมือนเดิม ดังนั้น <math> T' \,</math> นี้เป็น tree และ เป็น tree ที่ span ไปทุก ๆ vertex ของ <math> G \,</math> เนื่องจาก สมมติให้ edge ที่มี cost มากที่สุดใน cycle ที่เราลบไปคือ edge <math> e'=(x,y) \,</math> เนื่องจากก่อนหน้านี้เราเคยมี path จาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ โดยผ่าน edge <math> e' \,</math> นี้ แต่หลังจากลบ edge <math> e' \,</math> ออกไปแล้ว เราก็ยังสามารถเดินทางจาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ โดยการเดินทาง โดยอ้อมจาก <math> x \,</math> ไปหาโหนดที่เชื่อมกับ <math> x \, </math> ให้ โหนดนี้เป็น <math> z \,</math> หลังจากนั้นจาก <math> z \,</math> ไปยัง vertex ที่เชื่อมกับ <math> z \,</math> และเนื่องจาก <math> T \,</math> จะเป็นกราฟเชื่อมโยง ดังนั้นต้องมีทางจาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ใน <math> T' \,</math> ดังนั้น <math> T' \,</math> เป็น spanning tree และ เป็น spanning tree ที่มี cost น้อยที่สุดด้วย เพราะก่อนหน้าที่จะลบ edge <math> e' \,</math> ออกจาก <math> G \,</math> นั้น <math> G \,</math> มี cycle แค่ตัวเดียว และเราทำการลบ edge ที่มี cost มากที่สุดใน cycle ออกไปแล้ว ดังนั้นเราจึงสามารถสรุปได้ว่า <math> T' \,</math> ที่ได้เป็น minimum spanning tree แล้ว

@@ แถว 1: / แถว 1: @@
 == ข้อย่อย 1 ==
-เนื่องจาก <math> T \, </math> เป็น minimum spanning tree จึงไม่มี cycle และเป็น tree ที่ span ไปยังทุก  vertex ในกราฟ ดังนั้นเมื่อเพิ่ม edge <math> e=(v,w) \,</math>เข้าไปใน <math> G \,</math> แล้วจะทำให้เกิด cycle ขึ้น ซึ่งหลังจากเพิ่ม edge <math> e=(v,w) \,</math> นี้เข้าไปใน <math> G \,</math> แล้ว tree <math> T \,</math> จะไม่เป็น minimum spanning tree ของกราฟใหม่ ถ้า edge ที่เพิ่มเข้าไปนี้ไม่ได้เป็น edge ที่มี cost มากที่สุดใน cycle แสดงว่า edge ที่มี cost มากที่สุดใน cycle ต้องเป็น edge ที่อยู่ใน <math> T \,</math> ก่อนหน้านี้แล้ว จาก cycle property ที่บอกว่า edge ที่มี cost มากที่สุดใน cycle จะไม่อยู่ใน minimum spanning tree ดังนั้น <math> T \,</math> จึงไม่เป็น minimum spanning tree ของ <math> G \,</math> อีกต่อไป ซึ่งอัลกอริทึมข้างต้นจะใช้เวลาเป็น <math> O(|E|) \,</math> แต่เนื่องจาก <math> T \,</math> เป็น tree จึงมีจำนวน edge ได้ <math> |V| -1 \,</math> ซึ่งหลังจากเพิ่ม edge <math> u=(v,w) \,</math> เข้าไปแล้วจำนวน edge ที่ต้องตรวจสอบอย่างมากคือ <math> |V|-1+1=|V| \,</math> ดังนั้น อัลกอริทึมข้างต้นจริง ๆ ทำงานได้ใน <math> O(|V|) \,</math> ส่วนโครงสร้างข้อมูลที่ใช้เก็บแทนกราฟและ tree ก็ใช้ adjacency list ได้
+เนื่องจาก <math> T \, </math> เป็น minimum spanning tree จึงไม่มี cycle และเป็น tree ที่ span ไปยังทุก  vertex ในกราฟ ดังนั้นเมื่อเพิ่ม edge <math> e=(v,w) \,</math>เข้าไปใน <math> G \,</math> แล้วจะทำให้เกิด cycle ขึ้น ซึ่งหลังจากเพิ่ม edge <math> e=(v,w) \,</math> นี้เข้าไปใน <math> G \,</math> แล้ว tree <math> T \,</math> จะไม่เป็น minimum spanning tree ของกราฟใหม่ ถ้า edge ที่เพิ่มเข้าไปนี้ไม่ได้เป็น edge ที่มี cost มากที่สุดใน cycle แสดงว่า edge ที่มี cost มากที่สุดใน cycle ต้องเป็น edge ที่อยู่ใน <math> T \,</math> ก่อนหน้านี้แล้ว จาก cycle property ที่บอกว่า edge ที่มี cost มากที่สุดใน cycle จะไม่อยู่ใน minimum spanning tree ดังนั้น <math> T \,</math> จึงไม่เป็น minimum spanning tree ของ <math> G \,</math> อีกต่อไป ดังนั้นอัลกอริทึมในการตรวจสอบว่า <math> T \,</math> ยังเป็น minimum spanning tree อยู่หรือไม่ ก็คือดูว่า edge ที่เพิ่มเข้าไปนั้นเป็น edge ที่มี cost มากที่สุดใน cycle หรือไม่ ถ้าใช้ <math> T \,</math> ก็ยังเป็น minimum spanning tree เหมือนเดิม แต่ถ้าไม่ใช่ <math> T \,</math> ก็จะไม่ใช่ minimum spanning tree อีกต่อไป ซึ่งอัลกอริทึมข้างต้นจะใช้เวลาเป็น <math> O(|E|) \,</math> แต่เนื่องจาก <math> T \,</math> เป็น tree จึงมีจำนวน edge ได้ <math> |V| -1 \,</math> ซึ่งหลังจากเพิ่ม edge <math> u=(v,w) \,</math> เข้าไปแล้วจำนวน edge ที่ต้องตรวจสอบอย่างมากคือ <math> |V|-1+1=|V| \,</math> ดังนั้น อัลกอริทึมข้างต้นจริง ๆ ทำงานได้ใน <math> O(|V|) \,</math> ส่วนโครงสร้างข้อมูลที่ใช้เก็บแทนกราฟและ tree ก็สามารถใช้ adjacency list ได้
 == ข้อย่อย 2 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:21, 30 กันยายน 2552
แถว 1:		แถว 1:
	== ข้อย่อย 1 ==		== ข้อย่อย 1 ==
		+	เนื่องจาก <math> T \, </math> เป็น minimum spanning tree จึงไม่มี cycle และเป็น tree ที่ span ไปยังทุก vertex ในกราฟ ดังนั้นเมื่อเพิ่ม edge <math> e=(v,w) \,</math>เข้าไปใน <math> G \,</math> แล้วจะทำให้เกิด cycle ขึ้น ซึ่งหลังจากเพิ่ม edge <math> e=(v,w) \,</math> นี้เข้าไปใน <math> G \,</math> แล้ว tree <math> T \,</math> จะไม่เป็น minimum spanning tree ของกราฟใหม่ ถ้า edge ที่เพิ่มเข้าไปนี้ไม่ได้เป็น edge ที่มี cost มากที่สุดใน cycle แสดงว่า edge ที่มี cost มากที่สุดใน cycle ต้องเป็น edge ที่อยู่ใน <math> T \,</math> ก่อนหน้านี้แล้ว จาก cycle property ที่บอกว่า edge ที่มี cost มากที่สุดใน cycle จะไม่อยู่ใน minimum spanning tree ดังนั้น <math> T \,</math> จึงไม่เป็น minimum spanning tree ของ <math> G \,</math> อีกต่อไป ซึ่งอัลกอริทึมข้างต้นจะใช้เวลาเป็น <math> O(\|E\|) \,</math> แต่เนื่องจาก <math> T \,</math> เป็น tree จึงมีจำนวน edge ได้ <math> \|V\| -1 \,</math> ซึ่งหลังจากเพิ่ม edge <math> u=(v,w) \,</math> เข้าไปแล้วจำนวน edge ที่ต้องตรวจสอบอย่างมากคือ <math> \|V\|-1+1=\|V\| \,</math> ดังนั้น อัลกอริทึมข้างต้นจริง ๆ ทำงานได้ใน <math> O(\|V\|) \,</math> ส่วนโครงสร้างข้อมูลที่ใช้เก็บแทนกราฟและ tree ก็ใช้ adjacency list ได้

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