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^{*}\,

เป็นส่วนประกอบ

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

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