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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

ข้อ 1

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

สมมติว่า เป็น connected graph ที่มี edge แต่ละ edge มี cost ถ้า edge เป็น edge ที่มี cost ต่ำที่สุด ใน (กล่าวคือ สำหรับ edge อื่นๆ ที่ ) แล้วจะมี minimum spanning tree ที่มี edge เป็นส่วนประกอบ

เฉลย

ข้อ 2

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

  1. ให้ เป็นกราฟต่อเนื่องแบบไม่มีทีิศทางที่ cost ของ edge ทุก edge เป็นบวก และไม่มี edge สอง edge ใดๆ มี cost เท่ากัน ให้ เป็น minimum spanning tree ต้นหนึ่งของ สมมติต่อว่าเราเพิ่มค่า cost ของ edge ทุก edge จาก เป็น แล้ว
    จริงหรือไม่ ที่ ยังเป็น minimum spanning tree ของกราฟใหม่อยู่
  2. ให้ เป็นกราฟแบบมีทิศทางที่ cost ของ edge แต่ละ edge เป็นบวก และไม่มี edge สอง edge ใดๆ มี cost เท่ากัน ให้ และ เป็น vertex สอง vertex ใน และให้ เป็น shortest path จาก ไปยัง สมมติต่อว่าเราเพิ่มค่า cost ของ edge ทุก edge จาก เป็น แล้ว
    จริงหรือไม่ ที่ ยังเป็น shotest path จาก ไปยัง อยู่

เฉลย

ข้อ 3

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

เฉลย

ข้อ 4

[Kleinberg & Tardos 4.9] ให้ เป็น connected graph ที่มี vertex อยู่ vertex และมี edge อยู่ edge โดยที่ edge ทุก edge มี cost เป็นบวกและไม่มี edge สอง edge ใดๆ มี cost เท่ากัน

ให้ เป็น spanning tree ของ ต้นหนึ่ง เรานิยาม bottleneck edge ของ ว่าเป็น edge ใน ที่มี cost สูงที่สุด

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

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

เฉลย

ข้อ 5

[Kleinberg & Tardos 4.10] ให้ เป็นกราฟต่อเนื่องแบบไม่มีทิศทางที่ cost สำหรับทุก edge สมมติว่าคุณได้รับ minimum spanning tree ของ มาหนึ่งต้น

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

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

เฉลย

ข้อ 6

[Dasgupta, Papadimitriou, Vazirani 4.12] กำหนดกราฟแบบไม่มีทิศทาง ซึ่ง edge ทุก edge มีความยาวเป็นบวก และกำหนด edge ให้ จงออกแบบอัลกอริทึมเพื่อหา cycle ที่สั้นที่สุดใน ที่มี edge เป็นส่วนประกอบ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา

เฉลย

ข้อ 7

[Dasgupta, Papadimitriou, Vazirani 4.3] กำหนดกราฟแบบไม่มีทิศทาง มาให้ จงออกแบบอัลกอริทึมเพื่อหาว่าใน มีสี่เหลี่ยม หรือไม่ เมื่อสี่เหลี่ยมคือ simple cycle ที่มีความยาวเท่ากับ 4 พอดี อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา

เฉลย