http://158.108.32.49/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_4.3
418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.3 - ประวัติรุ่นแก้ไข
2026-05-07T02:32:22Z
ประวัติรุ่นแก้ไขของหน้านี้ในวิกิ
MediaWiki 1.33.1
http://158.108.32.49/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_4.3&diff=7443&oldid=prev
Cardcaptor เมื่อ 13:43, 16 กันยายน 2552
2009-09-16T13:43:48Z
<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;">รุ่นแก้ไขเมื่อ 13:43, 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>ให้ <math>u \,</math> และ <math>v \,</math> เป็น vertex ใดๆ ในกราฟแล้ว เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน คือ</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>ให้ <math>u \,</math> และ <math>v \,</math> เป็น vertex ใดๆ ในกราฟแล้ว เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน คือ</div></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;"></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;"></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">DFSALL</del>(u) ถูกเรียกให้ทำงานก่อน <del class="diffchange diffchange-inline">DFSALL</del>(v)</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">DFS</ins>(u) ถูกเรียกให้ทำงานก่อน <ins class="diffchange diffchange-inline">DFS</ins>(v)</div></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">DFSALL</del>(v) ถูกเรียกให้ทำงานก่อน <del class="diffchange diffchange-inline">DFSALL</del>(u)</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">DFS</ins>(v) ถูกเรียกให้ทำงานก่อน <ins class="diffchange diffchange-inline">DFS</ins>(u)</div></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;"></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;"></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">DFSALL</del>(u) ถูกเรียกให้ทำงานก่อน <del class="diffchange diffchange-inline">DFSALL</del>(v) ในกรณีนี้เราจะได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] \,</math> และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ</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">DFS</ins>(u) ถูกเรียกให้ทำงานก่อน <ins class="diffchange diffchange-inline">DFS</ins>(v) ในกรณีนี้เราจะได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] \,</math> และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ</div></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;"></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;"></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># <math>\mathrm{post}[u] < \mathrm{pre}[v] \,</math> </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># <math>\mathrm{post}[u] < \mathrm{pre}[v] \,</math> </div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l13" >แถว 13:</td>
<td colspan="2" class="diff-lineno">แถว 13:</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>ไม่มีสมาชิกร่วมกันเลย ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์</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>ไม่มีสมาชิกร่วมกันเลย ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์</div></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;"></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;"></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>ในกรณีที่ 2 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[u]\,</math> หมายความว่า <del class="diffchange diffchange-inline">DFSALL</del>(v) ถูกเรียกให้ทำงานระหว่าง <del class="diffchange diffchange-inline">DFSALL</del>(u) กำลังทำงานอยู่</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>ในกรณีที่ 2 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[u]\,</math> หมายความว่า <ins class="diffchange diffchange-inline">DFS</ins>(v) ถูกเรียกให้ทำงานระหว่าง <ins class="diffchange diffchange-inline">DFS</ins>(u) กำลังทำงานอยู่</div></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">DFSALL</del>(v) จะต้องทำงานเสร็จก่อน <del class="diffchange diffchange-inline">DFSALL</del>(u) จะทำงานเสร็จ ด้วยเหตุนี้เราจะได้ว่า <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math> กล่าวคือ </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">DFS</ins>(v) จะต้องทำงานเสร็จก่อน <ins class="diffchange diffchange-inline">DFS</ins>(u) จะทำงานเสร็จ ด้วยเหตุนี้เราจะได้ว่า <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math> กล่าวคือ </div></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><math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์</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><math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์</div></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;"></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;"></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">DFSALL</del>(v) ถูกเรียกให้ทำงานก่อน <del class="diffchange diffchange-inline">DFSALL</del>(u) ได้โดยการใช้เหตุผลแบบเดียวกับข้างบน เพียงแต่สลับบทบาทของ <math>u \,</math> กับ <math>v \,</math> เท่านั้น</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">DFS</ins>(v) ถูกเรียกให้ทำงานก่อน <ins class="diffchange diffchange-inline">DFS</ins>(u) ได้โดยการใช้เหตุผลแบบเดียวกับข้างบน เพียงแต่สลับบทบาทของ <math>u \,</math> กับ <math>v \,</math> เท่านั้น</div></td></tr>
</table>
Cardcaptor
http://158.108.32.49/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_4.3&diff=7421&oldid=prev
Cardcaptor เมื่อ 10:46, 16 กันยายน 2552
2009-09-16T10:46: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;">รุ่นแก้ไขเมื่อ 10:46, 16 กันยายน 2552</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l11" >แถว 11:</td>
<td colspan="2" class="diff-lineno">แถว 11:</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>ในกรณีที่ 1 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{pre}[v] < \mathrm{post}[v] \,</math> </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>ในกรณีที่ 1 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{pre}[v] < \mathrm{post}[v] \,</math> </div></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>ซึ่งหมายความว่าช่วง <math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และช่วง <math>[\mathrm{pre}[v], \mathrm{post}[v]] \,</math></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>ซึ่งหมายความว่าช่วง <math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และช่วง <math>[\mathrm{pre}[v], \mathrm{post}[v]] \,</math></div></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">ไม่มีสมาชิกร่วมกันเลย </ins>ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์</div></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;"></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;"></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>ในกรณีที่ 2 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[u]\,</math> หมายความว่า DFSALL(v) ถูกเรียกให้ทำงานระหว่าง DFSALL(u) กำลังทำงานอยู่</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>ในกรณีที่ 2 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[u]\,</math> หมายความว่า DFSALL(v) ถูกเรียกให้ทำงานระหว่าง DFSALL(u) กำลังทำงานอยู่</div></td></tr>
</table>
Cardcaptor
http://158.108.32.49/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_4.3&diff=7420&oldid=prev
Cardcaptor เมื่อ 10:46, 16 กันยายน 2552
2009-09-16T10:46:32Z
<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;">รุ่นแก้ไขเมื่อ 10:46, 16 กันยายน 2552</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >แถว 4:</td>
<td colspan="2" class="diff-lineno">แถว 4:</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>* DFSALL(v) ถูกเรียกให้ทำงานก่อน DFSALL(u)</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>* DFSALL(v) ถูกเรียกให้ทำงานก่อน DFSALL(u)</div></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;"></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;"></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>DFSALL(u) ถูกเรียกให้ทำงานก่อน DFSALL(v) ในกรณีนี้เราจะได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] \,</math> และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ</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">พิจารณากรณีที่ </ins>DFSALL(u) ถูกเรียกให้ทำงานก่อน DFSALL(v) ในกรณีนี้เราจะได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] \,</math> และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ</div></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;"></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;"></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># <math>\mathrm{post}[u] < \mathrm{pre}[v] \,</math> </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># <math>\mathrm{post}[u] < \mathrm{pre}[v] \,</math> </div></td></tr>
</table>
Cardcaptor
http://158.108.32.49/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_4.3&diff=7419&oldid=prev
Cardcaptor เมื่อ 10:46, 16 กันยายน 2552
2009-09-16T10:46:18Z
<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;">รุ่นแก้ไขเมื่อ 10:46, 16 กันยายน 2552</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l14" >แถว 14:</td>
<td colspan="2" class="diff-lineno">แถว 14:</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;"></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;"></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>ในกรณีที่ 2 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[u]\,</math> หมายความว่า DFSALL(v) ถูกเรียกให้ทำงานระหว่าง DFSALL(u) กำลังทำงานอยู่</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>ในกรณีที่ 2 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[u]\,</math> หมายความว่า DFSALL(v) ถูกเรียกให้ทำงานระหว่าง DFSALL(u) กำลังทำงานอยู่</div></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>ฉะนั้น DFSALL(v) จะต้องทำงานเสร็จก่อน DFSALL(u) <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>ฉะนั้น DFSALL(v) จะต้องทำงานเสร็จก่อน DFSALL(u) <ins class="diffchange diffchange-inline">จะทำงานเสร็จ ด้วยเหตุนี้เราจะได้ว่า <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math> กล่าวคือ </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 class="diffchange diffchange-inline"><math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์</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> </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 class="diffchange diffchange-inline">เราสามารถพิสูจน์กรณีที่ DFSALL(v) ถูกเรียกให้ทำงานก่อน DFSALL(u) ได้โดยการใช้เหตุผลแบบเดียวกับข้างบน เพียงแต่สลับบทบาทของ <math>u \,</math> กับ <math>v \,</math> เท่านั้น</ins></div></td></tr>
</table>
Cardcaptor
http://158.108.32.49/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_4.3&diff=7418&oldid=prev
Cardcaptor เมื่อ 10:46, 16 กันยายน 2552
2009-09-16T10:46:05Z
<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;">รุ่นแก้ไขเมื่อ 10:46, 16 กันยายน 2552</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >แถว 4:</td>
<td colspan="2" class="diff-lineno">แถว 4:</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>* DFSALL(v) ถูกเรียกให้ทำงานก่อน DFSALL(u)</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>* DFSALL(v) ถูกเรียกให้ทำงานก่อน DFSALL(u)</div></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;"></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;"></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>ิพิจารณากรณีที่ DFSALL(u) ถูกเรียกให้ทำงานก่อน DFSALL(v) ในกรณีนี้เราจะได้ว่า <math>\mathrm{<del class="diffchange diffchange-inline">post</del>}[u] < \mathrm{<del class="diffchange diffchange-inline">post</del>}[v] \,</math> และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ</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>ิพิจารณากรณีที่ DFSALL(u) ถูกเรียกให้ทำงานก่อน DFSALL(v) ในกรณีนี้เราจะได้ว่า <math>\mathrm{<ins class="diffchange diffchange-inline">pre</ins>}[u] < \mathrm{<ins class="diffchange diffchange-inline">pre</ins>}[v] \,</math> และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ</div></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;"></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;"></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">* DFSALL(</del>u<del class="diffchange diffchange-inline">) ถูกเรียกใ้ห้ทำงาน </del><math> \,</math></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"># <math>\mathrm{post}[u] < \mathrm{pre}[v] \,</math> </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 class="diffchange diffchange-inline"># <math>\mathrm{post}[u] > \mathrm{pre}[v] \,</math></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> </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 class="diffchange diffchange-inline">ในกรณีที่ 1 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{pre}[v] < \mathrm{post}[v] \,</math> </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 class="diffchange diffchange-inline">ซึ่งหมายความว่าช่วง <math>[\mathrm{pre}[u], \mathrm{post}[</ins>u<ins class="diffchange diffchange-inline">]] \,</math> และช่วง <math>[\mathrm{pre}[v], \mathrm{post}[v]] \,</math></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 class="diffchange diffchange-inline">ไม่ซ้อนทับกันเลย ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์</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> </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 class="diffchange diffchange-inline">ในกรณีที่ 2 เราได้ว่า </ins><math><ins class="diffchange diffchange-inline">\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[u]</ins>\,</math> <ins class="diffchange diffchange-inline">หมายความว่า DFSALL(v) ถูกเรียกให้ทำงานระหว่าง DFSALL(u) กำลังทำงานอยู่</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 class="diffchange diffchange-inline">ฉะนั้น DFSALL(v) จะต้องทำงานเสร็จก่อน DFSALL(u) เสมอ</ins></div></td></tr>
</table>
Cardcaptor
http://158.108.32.49/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_4.3&diff=7417&oldid=prev
Cardcaptor: หน้าที่ถูกสร้างด้วย 'ให้ <math>u \,</math> และ <math>v \,</math> เป็น vertex ใดๆ ในกราฟแล้ว เราจะได…'
2009-09-16T10:30:06Z
<p>หน้าที่ถูกสร้างด้วย 'ให้ <math>u \,</math> และ <math>v \,</math> เป็น vertex ใดๆ ในกราฟแล้ว เราจะได…'</p>
<p><b>หน้าใหม่</b></p><div>ให้ <math>u \,</math> และ <math>v \,</math> เป็น vertex ใดๆ ในกราฟแล้ว เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน คือ<br />
<br />
* DFSALL(u) ถูกเรียกให้ทำงานก่อน DFSALL(v)<br />
* DFSALL(v) ถูกเรียกให้ทำงานก่อน DFSALL(u)<br />
<br />
ิพิจารณากรณีที่ DFSALL(u) ถูกเรียกให้ทำงานก่อน DFSALL(v) ในกรณีนี้เราจะได้ว่า <math>\mathrm{post}[u] < \mathrm{post}[v] \,</math> และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ<br />
<br />
* DFSALL(u) ถูกเรียกใ้ห้ทำงาน <math> \,</math></div>
Cardcaptor