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

== ข้อ 1 ==
[Kleinberg & Tardos 4.1] จงตัดสินใจว่าข้อความต่อไปนี้เป็นความจริงหรือไม่ ถ้าเป็นจริงให้พิสูจน์็ ถ้าเป็นเท็จให้หาตัวอย่างขัดแย้ง
: สมมติว่า <math>G \,</math> เป็น connected graph ที่มี edge <math>e \,</math> แต่ละ edge มี cost <math>c(e) \,</math> ถ้า edge <math>e^* \,</math> เป็น edge ที่มี cost ต่ำที่สุด ใน <math>G \,</math> (กล่าวคือ <math>c(e^*) < c(e) \,</math> สำหรับ edge <math>e \,</math> อื่นๆ ที่ <math>e \neq e^* \,</math>) แล้วจะมี minimum spanning tree <math>T  \,</math> ที่มี edge <math>e^* \,</math> เป็นส่วนประกอบ

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

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

# ให้ <math>G \,</math> เป็นกราฟต่อเนื่องแบบไม่มีทีิศทางที่ cost ของ edge ทุก edge เป็นบวก และไม่มี edge สอง edge ใดๆ มี cost เท่ากัน ให้ <math>T \,</math> เป็น minimum spanning tree ต้นหนึ่งของ <math>G \,</math> สมมติต่อว่าเราเพิ่มค่า cost ของ edge ทุก edge จาก <math>c_e \,</math> เป็น <math>c_e^2 \,</math> แล้ว
#: จริงหรือไม่ ที่ <math>T \,</math> ยังเป็น minimum spanning tree ของกราฟใหม่อยู่
# ให้ <math>G \,</math> เป็นกราฟแบบมีทิศทางที่ cost ของ edge แต่ละ edge เป็นบวก และไม่มี edge สอง edge ใดๆ มี cost เท่ากัน ให้ <math>s \,</math> และ <math>t \,</math> เป็น vertex สอง vertex ใน <math>G \,</math> และให้ <math>P \,</math> เป็น shortest path จาก <math>s \,</math> ไปยัง <math>t \,</math> สมมติต่อว่าเราเพิ่มค่า cost ของ edge ทุก edge จาก <math>c_e \,</math> เป็น <math>c_e^2 \,</math> แล้ว
#: จริงหรือไม่ ที่ <math>P \,</math> ยังเป็น shotest path จาก <math>s \,</math> ไปยัง <math>t \,</math> อยู่

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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