https://theory.cpe.ku.ac.th/wiki/index.php?action=history&feed=atom&title=418531_%E0%B8%A0%E0%B8%B2%E0%B8%84%E0%B8%95%E0%B9%89%E0%B8%99_2552%2F%E0%B9%82%E0%B8%88%E0%B8%97%E0%B8%A2%E0%B9%8C%E0%B8%9B%E0%B8%B1%E0%B8%8D%E0%B8%AB%E0%B8%B2%E0%B8%AD%E0%B8%B1%E0%B8%A5%E0%B8%81%E0%B8%AD%E0%B8%A3%E0%B8%B4%E0%B8%97%E0%B8%B6%E0%B8%A1%E0%B9%80%E0%B8%81%E0%B8%B5%E0%B9%88%E0%B8%A2%E0%B8%A7%E0%B8%81%E0%B8%B1%E0%B8%9A%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F%2F%E0%B9%80%E0%B8%89%E0%B8%A5%E0%B8%A2%E0%B8%82%E0%B9%89%E0%B8%AD_6.4
418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.4 - ประวัติรุ่นแก้ไข
2026-04-29T01:54:06Z
ประวัติรุ่นแก้ไขของหน้านี้ในวิกิ
MediaWiki 1.33.1
https://theory.cpe.ku.ac.th/wiki/index.php?title=418531_%E0%B8%A0%E0%B8%B2%E0%B8%84%E0%B8%95%E0%B9%89%E0%B8%99_2552/%E0%B9%82%E0%B8%88%E0%B8%97%E0%B8%A2%E0%B9%8C%E0%B8%9B%E0%B8%B1%E0%B8%8D%E0%B8%AB%E0%B8%B2%E0%B8%AD%E0%B8%B1%E0%B8%A5%E0%B8%81%E0%B8%AD%E0%B8%A3%E0%B8%B4%E0%B8%97%E0%B8%B6%E0%B8%A1%E0%B9%80%E0%B8%81%E0%B8%B5%E0%B9%88%E0%B8%A2%E0%B8%A7%E0%B8%81%E0%B8%B1%E0%B8%9A%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F/%E0%B9%80%E0%B8%89%E0%B8%A5%E0%B8%A2%E0%B8%82%E0%B9%89%E0%B8%AD_6.4&diff=7403&oldid=prev
Aoy เมื่อ 06:25, 16 กันยายน 2552
2009-09-16T06:25:59Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="th">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">←รุ่นแก้ไขก่อนหน้า</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">รุ่นแก้ไขเมื่อ 06:25, 16 กันยายน 2552</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >แถว 1:</td>
<td colspan="2" class="diff-lineno">แถว 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[อ้างอิงจาก Algorithm Design, by KLEINBERG and TARDOS, PEARSON Addison Wesley]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[อ้างอิงจาก Algorithm Design, by KLEINBERG and TARDOS, PEARSON Addison Wesley]</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">พิสูจน์: โดยใช้ข้อขัดแย้ง สมมติให้ <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 อยู่อย่างน้อยหนึ่งตัวเสมอ</ins></div></td></tr>
</table>
Aoy
https://theory.cpe.ku.ac.th/wiki/index.php?title=418531_%E0%B8%A0%E0%B8%B2%E0%B8%84%E0%B8%95%E0%B9%89%E0%B8%99_2552/%E0%B9%82%E0%B8%88%E0%B8%97%E0%B8%A2%E0%B9%8C%E0%B8%9B%E0%B8%B1%E0%B8%8D%E0%B8%AB%E0%B8%B2%E0%B8%AD%E0%B8%B1%E0%B8%A5%E0%B8%81%E0%B8%AD%E0%B8%A3%E0%B8%B4%E0%B8%97%E0%B8%B6%E0%B8%A1%E0%B9%80%E0%B8%81%E0%B8%B5%E0%B9%88%E0%B8%A2%E0%B8%A7%E0%B8%81%E0%B8%B1%E0%B8%9A%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F/%E0%B9%80%E0%B8%89%E0%B8%A5%E0%B8%A2%E0%B8%82%E0%B9%89%E0%B8%AD_6.4&diff=7402&oldid=prev
Aoy เมื่อ 06:11, 16 กันยายน 2552
2009-09-16T06:11:23Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="th">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">←รุ่นแก้ไขก่อนหน้า</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">รุ่นแก้ไขเมื่อ 06:11, 16 กันยายน 2552</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >แถว 1:</td>
<td colspan="2" class="diff-lineno">แถว 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">อ.วัฒนา</del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[อ้างอิงจาก Algorithm Design, by KLEINBERG and TARDOS, PEARSON Addison Wesley]</ins></div></td></tr>
</table>
Aoy
https://theory.cpe.ku.ac.th/wiki/index.php?title=418531_%E0%B8%A0%E0%B8%B2%E0%B8%84%E0%B8%95%E0%B9%89%E0%B8%99_2552/%E0%B9%82%E0%B8%88%E0%B8%97%E0%B8%A2%E0%B9%8C%E0%B8%9B%E0%B8%B1%E0%B8%8D%E0%B8%AB%E0%B8%B2%E0%B8%AD%E0%B8%B1%E0%B8%A5%E0%B8%81%E0%B8%AD%E0%B8%A3%E0%B8%B4%E0%B8%97%E0%B8%B6%E0%B8%A1%E0%B9%80%E0%B8%81%E0%B8%B5%E0%B9%88%E0%B8%A2%E0%B8%A7%E0%B8%81%E0%B8%B1%E0%B8%9A%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F/%E0%B9%80%E0%B8%89%E0%B8%A5%E0%B8%A2%E0%B8%82%E0%B9%89%E0%B8%AD_6.4&diff=7357&oldid=prev
Aoy: หน้าที่ถูกสร้างด้วย 'อ.วัฒนา'
2009-09-09T10:28:25Z
<p>หน้าที่ถูกสร้างด้วย 'อ.วัฒนา'</p>
<p><b>หน้าใหม่</b></p><div>อ.วัฒนา</div>
Aoy