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

จาก Theory Wiki
ข้ามไปที่: นำทาง, สืบค้น

เนื้อหา

ข้อ 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) \,

เฉลย

เครื่องมือส่วนตัว
สิ่งที่แตกต่าง
การกระทำ
ป้ายบอกทาง
เครื่องมือเพิ่ม