การประยุกต์ใช้กราฟในชีวิตประจำวัน

ปัญหาการเล่มเกม

มีก้านไม้ขีดอยู่สองกอง กองหนึ่งมีจำนวน ก้านไม้ขีดอยู่ n ก้าน อีกกองหนึ่งมี n + 1 ก้าน การเล่นเกมนี้เล่นกันสองคน ทีมขาวและทีมดำ ซึ่งผลัดกันหยิบไม้ขีด โดยการหยิบไม้ขีดมีเงื่อนไขการหยิบดังนี้

  • ผู้เล่นจะหยิบ หนึ่งก้านจากกองใดกองหนึ่งก็ได้ หรือ

  • จะหยิบก้านไม้ขีดออกจากทั้งสองกอง ละหนึ่งก้าน

  • ผู้หยิบก้านไม้ขีดคนสุดท้ายเป็นผู้ชนะ

ถ้าสมมุติให้ฝ่ายขาวเดินก่อน ให้ลองหาวิธีการเขียนกราฟ เพื่อใช้แทนปัญหานี้

แนวคิดในการแก้ปัญหา


ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์