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

ข้อย่อย 1

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

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

พิสูจน์:

จาก $c(e)<c(e')\,$ ให้เป็นสมการที่ 1

คูณสมการที่ 1 ทั้งสองข้างด้วย $c(e)\,$ จะได้ $c(e)^{2}<c(e')c(e)\,$ ให้เป็นสมการที่ 2 (เนื่องจาก cost ของทุก edge เป็นบวก)

คูณสมการที่ 1 ทั้งสองข้างด้วย $c(e')\,$ จะได้ $c(e)c(e')<c(e')^{2}\,$ ให้เป็นสมการที่ 3 (เนื่องจาก cost ของทุก edge เป็นบวก)

จากสมการที่ 2 และ 3 จะได้ $c(e)^{2}<c(e')^{2}\,$ จริง

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

ดังนั้นต้องทำการพิสูจน์ว่าสำหรับทุก ๆ edge $e={a,b}\,$ ใน minimum spanning tree $T\,$ นั้น edge $e\,$ ดังกล่าวจะต้องเป็นเป็น edge ใน minmimum spanning tree ต้นหนึ่งของกราฟ $G'\,$ ด้วย

พิจารณา edge $e=\{a,b\}\,$ ใด ๆ ที่อยู่ในต้นไม้ $T\,$ ถ้าเราทำการลบ edge $e\,$ นี้ออกจากต้นไม้ $T\,$ เราจะได้ว่าเกิดการแบ่ง vertex ของกราฟ $G\,$ ออกเป็นสองส่วน ให้เป็น $A\,$ กับ $B\,$ โดยที่ $A\,$ คือเซตของ vertex ที่ไปถึงจาก $a\,$ ได้ ในกราฟ $T\,$ ที่ลบ edge $e\,$ ออกแล้ว ส่วน $B\,$ คือเซตของ vertex ที่ไปถึงจาก $b\,$ ได้ ในกราฟ $T\,$ ที่ลบ edge $e\,$ ออกแล้ว สังเกตว่า $A\,$ และ $B\,$ ไม่เป็นเซตว่าง เนื่องจาก ทั้งสองเซตจะมีสมาชิกอยู่อย่างน้อยหนึ่งตัวคือ $a\,$ และ $b\,$ ตามลำดับ นอกจากนี้ยังได้ว่า $A\cup B=V\,$ ดังนั้น $A\,$ เป็น cut ใน $G\,$

พิจารณา cut set ของ cut $A\,$ เราจะได้ว่า edge $e\,$ เป็น edge ที่มี cost น้อยที่สุดในบรรดา edge ที่ข้าม cut $A\,$ เนื่องจาก edge $e\,$ มีปลายด้านหนึ่งอยู่ใน $A\,$ และปลายอีกด้านหนึ่งอยู่ใน $B\,$ (ถ้าไม่เช่นนั้น เราสามารถเลือก edge ที่มี cost น้อยกว่า edge $e\,$ นี้มาใส่ใน tree แทน เราก็จะได้ tree อีกต้นที่มี cost น้อยกว่า cost ของ $T\,$ จึงขัดแย้งกับที่บอกว่า $T\,$ เป็น minimum spanning tree ใน $G\,$)

พิจารณา cut $A\,$ ซึ่งเป็น cut เดียวกับที่นิยามข้างต้นในกราฟ $G'\,$ จากที่เราได้ทำการพิสูจน์ไปแล้ว จะได้ว่า cost ของ edge $e\,$ ในกราฟ $G'\,$ ซึ่งมีค่าเป็น $c(e)^{2}\,$ นี้จะต้องน้อยที่สุดในบรรดา edge ที่ข้าม cut $A\,$ ในกราฟ $G'\,$ ด้วย นั่นคือ$c(e)<c(e')\,$ สำหรับ edge $e'\,$ ใด ๆ ที่เป็น edge ข้าม cut $A\,$ และ $e\neq e'\,$ แล้ว $c(e)^{2}<c(e')^{2}\,$ และเนื่องจากโจทย์กำหนดให้ cost ของแต่ละ edge ในกราฟไม่ซ้ำกัน จาก cut property เราจะได้ว่า edge $e\,$ นี้จะต้องเป็น edge ใน minimum spanning tree ต้นหนึ่งของกราฟ $G'\,$

ข้อย่อย 2

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

จากตัวอย่างข้างต้น กราฟทางซ้ายเป็นกราฟที่ให้มา จากกราฟจะได้ระยะทางที่สั้นที่สุดจาก $s\,$ ไป $t\,$ คือ edge ที่พุ่งจาก $s\,$ ไปยัง $t\,$ เลย ซึ่งมี cost เป็น 10 แต่เมื่อเอาค่า cost ของแต่ละ edge มายกกำลังสองแล้วจะได้ว่า ระยะทางจาก $s\,$ ไป $t\,$ จะเป็น $s\rightarrow a\rightarrow b\rightarrow t\,$ ซึ่งมี cost เป็น 4+16+49 = 69 ซึ่งน้อยกว่า cost ของedge จาก $s\,$ ไปยัง $t\,$ ที่เคยเป็นระยะทางที่สั้นที่สุดจากกราฟตั้งต้น ซึ่งตอนนี้มี cost เป็น 100