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

รุ่นแก้ไขปัจจุบันเมื่อ 06:51, 30 กันยายน 2552

เนื้อหา

1 ข้อ 1
2 ข้อ 2
3 ข้อ 3
4 ข้อ 4
5 ข้อ 5
6 ข้อ 6
7 ข้อ 7

ข้อ 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] จงตัดสินใจว่าข้อความต่อไปนี้เป็นจริงหรือไม่ ถ้าเป็นจริงให้พิสูจน์็ ถ้าเป็นเท็จให้หาตัวอย่างขัดแย้ง

ให้ $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\,$ อยู่

เฉลย

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

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

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

เฉลย

@@ แถว 17: / แถว 17: @@
 == ข้อ 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 ==
@@ แถว 27: / แถว 29: @@
 # ถ้า <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> มาหนึ่งต้น
+[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>
@@ แถว 35: / แถว 39: @@
 # จงออกแบบอัลกอริทึมที่ทดสอบว่าหลังจากเพิ่ม 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|เฉลย]]

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

รุ่นแก้ไขปัจจุบันเมื่อ 06:51, 30 กันยายน 2552

เนื้อหา

ข้อ 1

ข้อ 2

ข้อ 3

ข้อ 4

ข้อ 5

ข้อ 6

ข้อ 7

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ