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

ข้อ 1

[Kleinberg & Tardos 4.1] จงตัดสินใจว่าข้อความต่อไปนี้เป็นความจริงหรือไม่ ถ้าเป็นจริงให้พิสูจน์็ ถ้าเป็นเท็จให้หาตัวอย่างขัดแย้ง

สมมติว่า $G\,$ เป็น connected graph ที่มี edge $e\,$ แต่ละ edge มี cost $c(e)\,$ ถ้า edge $e^{*}\,$ เป็น edge ที่มี cost ต่ำที่สุด ใน $G\,$ (กล่าวคือ $c(e^{*})<c(e)\,$ สำหรับ edge $e\,$ อื่นๆ ที่ $e\neq e^{*}\,$) แล้วจะมี minimum spanning tree $T\,$ ที่มี edge $e^{*}\,$ เป็นส่วนประกอบ

เฉลย

ข้อ 2

[Kleinberg & Tardos 4.2] จงตัดสินใจว่าข้อความต่อไปนี้เป็นจริงหรือไม่ ถ้าเป็นจริงให้พิสูจน์็ ถ้าเป็นเท็จให้หาตัวอย่างขัดแย้ง

1. ให้ $G\,$ เป็นกราฟต่อเนื่องแบบไม่มีทีิศทางที่ cost ของ edge ทุก edge เป็นบวก และไม่มี edge สอง edge ใดๆ มี cost เท่ากัน ให้ $T\,$ เป็น minimum spanning tree ต้นหนึ่งของ $G\,$ สมมติต่อว่าเราเพิ่มค่า cost ของ edge ทุก edge จาก $c_{e}\,$ เป็น $c_{e}^{2}\,$ แล้ว

   จริงหรือไม่ ที่ $T\,$ ยังเป็น minimum spanning tree ของกราฟใหม่อยู่

2. ให้ $G\,$ เป็นกราฟแบบมีทิศทางที่ cost ของ edge แต่ละ edge เป็นบวก และไม่มี edge สอง edge ใดๆ มี cost เท่ากัน ให้ $s\,$ และ $t\,$ เป็น vertex สอง vertex ใน $G\,$ และให้ $P\,$ เป็น shortest path จาก $s\,$ ไปยัง $t\,$ สมมติต่อว่าเราเพิ่มค่า cost ของ edge ทุก edge จาก $c_{e}\,$ เป็น $c_{e}^{2}\,$ แล้ว

   จริงหรือไม่ ที่ $P\,$ ยังเป็น shotest path จาก $s\,$ ไปยัง $t\,$ อยู่

เฉลย

ข้อ 3

[Kleinberg & Tardos 4.8] ให้ $G\,$ เป็น connected graph ที่ไม่มี cost ของ edge สอง edge ใดๆ เท่ากันเลย จงแสดงว่า $G\,$ มี minimum spanning tree เพียงแค่ต้นเดียวเท่านั้น (กล่าวคือ ไม่มี tree สองต้นที่แตกต่างกัน ที่มี cost รวมเท่ากับ cost ของ minimum spanning tree)

เฉลย

ข้อ 4

[Kleinberg & Tardos 4.9] ให้ $G=(V,E)\,$ เป็น connected graph ที่มี vertex อยู่ $n\,$ vertex และมี edge อยู่ $m\,$ edge โดยที่ edge ทุก edge มี cost เป็นบวกและไม่มี edge สอง edge ใดๆ มี cost เท่ากัน

ให้ $T=(V,E')\,$ เป็น spanning tree ของ $G\,$ ต้นหนึ่ง เรานิยาม bottleneck edge ของ $T\,$ ว่าเป็น edge ใน $T\,$ ที่มี cost สูงที่สุด

เรากล่าวว่า spanning tree $T\,$ ของ $G\,$ เป็น minimum-bottleneck spanning tree ถ้าสมมติว่าไ่ม่มี spanning tree $T'\,$ ต้นอื่นของ $G\,$ ที่ bottleneck edge ของมันมี cost ต่ำกว่า bottleneck edge ของ $T\,$

1. ถ้า $T\,$ minimum-bottleneck spanning tree ของ $G\,$ แล้ว $T\,$ เป็น minimum spanning tree ด้วยหรือไม่? จงพิสูจน์หรือไม่ก็ให้ตัวอย่างขัดแย้ง
2. ถ้า $T\,$ minimum spanning tree ของ $G\,$ แล้ว $T\,$ เป็น minimum-bottleneck spanning tree ด้วยหรือไม่? จงพิสูจน์หรือไม่ก็ให้ตัวอย่างขัดแย้ง

เฉลย

ข้อ 5

[Kleinberg & Tardos 4.10] ให้ $G=(V,E)\,$ เป็นกราฟต่อเนื่องแบบไม่มีทิศทางที่ cost $c_{e}\geq 0\,$ สำหรับทุก edge $e\,$ สมมติว่าคุณได้รับ minimum spanning tree $T\,$ ของ $G\,$ มาหนึ่งต้น

ต่อมาสมมติว่าเราเพิ่ม edge edge หนึ่งเข้าไปใน $G\,$ โดย edge นี้ต่อ vertex $v\,$ เข้ากับ vertex $w\,$ และมี cost $c\,$

1. จงออกแบบอัลกอริทึมที่ทดสอบว่าหลังจากเพิ่ม edge ดังกล่าวเข้าไปใน $G\,$ แล้ว $T\,$ ยังเป็น minimum spanning tree อยู่หรือไม่? อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(|E|)\,$ คุณสามารถทำให้มันทำงานในเวลา $O(|V|)\,$ ได้หรือไม่? เวลาตอบจงบอกว่าอัลกอริทึมของคุณแทนกราฟและ spanning tree ด้วยโครงสร้างข้อมูลแบบใดด้วย
2. สมมติว่าหลังจากเพิ่ม edge ดังกล่าวเข้าไปใน $G\,$ แล้ว $T\,$ ไม่เป็น minimum spanning tree จงออกแบบอัลกอริทึมที่ทำการปรับปรุง $T\,$ ให้กลายเป็น minimum spanning tree ใหม่อีกครั้ง อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(|E|)\,$

เฉลย

ข้อ 6

[Dasgupta, Papadimitriou, Vazirani 4.12] กำหนดกราฟแบบไม่มีทิศทาง $G=(V,E)\,$ ซึ่ง edge ทุก edge มีความยาวเป็นบวก และกำหนด edge $e\in E\,$ ให้ จงออกแบบอัลกอริทึมเพื่อหา cycle ที่สั้นที่สุดใน $G\,$ ที่มี edge $e\,$ เป็นส่วนประกอบ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O((|V|+|E|)\log |V|)\,$

เฉลย

ข้อ 7

[Dasgupta, Papadimitriou, Vazirani 4.3] กำหนดกราฟแบบไม่มีทิศทาง $G=(V,E)\,$ มาให้ จงออกแบบอัลกอริทึมเพื่อหาว่าใน $G\,$ มีสี่เหลี่ยม หรือไม่ เมื่อสี่เหลี่ยมคือ simple cycle ที่มีความยาวเท่ากับ 4 พอดี อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา $O(|V|^{3})\,$

เฉลย