418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.5

[อ้างอิงจาก Algorithm Design, by KLEINBERG and TARDOS, PEARSON Addison Wesley]

แนวคิด จากความจริงในข้อย่อย 6.4 เราจะได้ว่าขณะใดขณะหนึ่งที่เราต้องการ node มาเรียงลำดับนั้น ถ้าเราสามารถหา node ที่ไม่มี node อื่นชี้มายังมันได้เลย เราก็จะสามารถรับประกันได้ว่า edge จะชี้จากซ้ายไปขวาเสมอ ดังนั้นการหา topological ordering ใน DAG ก็ทำได้โดยการหา source node มาเรียงกันเรื่อย ๆ ในแต่ละขั้นตอนนั่นเอง และเมื่อนำ node นั้นมาเรียงแล้วให้ทำการลบ node นั้นและ edge ทุก edge ที่ติดกับมัน ออกจากกราฟ ซึ่งถ้าเราสามารถรับประกันได้ว่า การทำแบบนี้จะมี soure node ให้เราเลือกได้เสมอ เราก็จะได้ topological ordering ตามที่เราต้องการ เราจึงจะทำการพิสูจน์ด้วย induction ว่าใน DAG มี topological ordering เสมอ พิจารณา DAG ที่มีหนึ่งหรือสอง node จะได้ว่ามี topological ordering จริง สมมติให้ DAG มี topological ordering สำหรับ DAG ที่มี $n\,$ node เมื่อให้ DAG ที่มี $n+1\,$ มา เราก็ทำการหา node ที่เป็น source node สมมติให้ node นี้เป็น node $v\,$ ซึ่งจากความจริงข้อ 6.4 จะสามารถหาได้เสมอ เราก็ทำการวาง node $v\,$ ดังกล่าวลงไปใน topological ordering การทำแบบนี้จะทำให้ทุก ๆ edge ชี้ออกจาก node $v\,$ ไปทางขวาเสมอ จากนั้นทำการลบ node $v\,$ และ edge ที่ติดกับมันออกจากกราฟ จะได้ว่ากราฟใหม่ $G-{v}\,$ นี้ก็เป็น DAG เนื่องจากการลบ node ออกจากกราฟที่ไม่มี cycle ไม่สามารถทำให้เกิด cycle ใหม่ขึ้นได้ ตอนนี้เราก็สามารถใช้ induction hypothesis หา topological ordering ของกราฟ $G-{v}\,$ ได้แล้ว เราจะทำการวาง node ที่เป็น source node ของกราฟ $G-{v}\,$ หลังจาก node $v\,$ ใน topological ordering การทำแบบนี้ก็จะได้ว่าทุก ๆ edge ในกราฟชี้จากซ้ายไปขวา ดังนั้นจึงเป็น topological ordering

จากแนวคิดดังกล่าวนำมาเขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c"> </geshi>