ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.4"
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
[อ้างอิงจาก Algorithm Design, by KLEINBERG and TARDOS, PEARSON Addison Wesley] | [อ้างอิงจาก Algorithm Design, by KLEINBERG and TARDOS, PEARSON Addison Wesley] | ||
| + | |||
| + | พิสูจน์: โดยใช้ข้อขัดแย้ง สมมติให้ <math> G \, </math> เป็น directed graph ที่ทุก node มี edge ชี้เข้ามาอย่างน้อยหนึ่ง edge เราจะทำการหาข้อขัดแย้ง โดยการหา cycle ในกราฟ <math> G \, </math> ดังกล่าว พิจารณาการหยิบ node <math> v \, </math> ใด ๆ มา และทำการย้อนกลับไปตาม edge ที่ชี้เข้ามาหา node <math> v \, </math> นี้ (สามารถหา edge นี้ได้เสมอ เนื่องจากเราสมมติว่า ทุก node ในกราฟจะมี edge ชี้เข้ามาอย่างน้อยหนึ่ง edge เสมอ) สมมติให้ edge ดังกล่าวเป็น edge <math> (u,v) \, </math> เราก็จะทำการวิ่งย้อนไปที่ node <math> u \, </math> และเนื่องจาก node <math> u \, </math> จะมี edge อย่างน้อยหนึ่ง edge ชี้เข้ามาเสมอ สมมติให้ edge ดังกล่าวเป็น edge <math> (x,u) \, </math> เราก็จะทำการวิ่งย้อนไปที่ node <math> x \, </math> ทำแบบนี้ไปเรื่อย ๆ เมื่อทำไปถึง step ที่ <math> n+1 \, </math> เมื่อ <math> n \, </math> เป็นจำนวน node ในกราฟ เราสามารถสรุปได้ว่า เราจะกลับมา visit node <math> w \, </math> บางตัวสองครั้ง กำหนดให้ <math> C \, </math> เป็น ลำดับของ node ที่เราทำการสำรวจมาจนกระทั่งถึง node ก่อนหน้า node <math> w \, </math> เราก็จะได้ว่า <math> C \, </math> เป็น cycle นั่นเอง เกิดข้อขัดแย้ง ดังนั้น สำหรับ DAG ใด ๆ แล้วจะมี source vertex อยู่อย่างน้อยหนึ่งตัวเสมอ | ||
รุ่นแก้ไขปัจจุบันเมื่อ 06:25, 16 กันยายน 2552
[อ้างอิงจาก Algorithm Design, by KLEINBERG and TARDOS, PEARSON Addison Wesley]
พิสูจน์: โดยใช้ข้อขัดแย้ง สมมติให้ เป็น directed graph ที่ทุก node มี edge ชี้เข้ามาอย่างน้อยหนึ่ง edge เราจะทำการหาข้อขัดแย้ง โดยการหา cycle ในกราฟ ดังกล่าว พิจารณาการหยิบ node ใด ๆ มา และทำการย้อนกลับไปตาม edge ที่ชี้เข้ามาหา node นี้ (สามารถหา edge นี้ได้เสมอ เนื่องจากเราสมมติว่า ทุก node ในกราฟจะมี edge ชี้เข้ามาอย่างน้อยหนึ่ง edge เสมอ) สมมติให้ edge ดังกล่าวเป็น edge เราก็จะทำการวิ่งย้อนไปที่ node และเนื่องจาก node จะมี edge อย่างน้อยหนึ่ง edge ชี้เข้ามาเสมอ สมมติให้ edge ดังกล่าวเป็น edge เราก็จะทำการวิ่งย้อนไปที่ node ทำแบบนี้ไปเรื่อย ๆ เมื่อทำไปถึง step ที่ เมื่อ เป็นจำนวน node ในกราฟ เราสามารถสรุปได้ว่า เราจะกลับมา visit node บางตัวสองครั้ง กำหนดให้ เป็น ลำดับของ node ที่เราทำการสำรวจมาจนกระทั่งถึง node ก่อนหน้า node เราก็จะได้ว่า เป็น cycle นั่นเอง เกิดข้อขัดแย้ง ดังนั้น สำหรับ DAG ใด ๆ แล้วจะมี source vertex อยู่อย่างน้อยหนึ่งตัวเสมอ
