Make your own free website on Tripod.com

ทฤษฎีกราฟของออยเลอร์
ออยเลอร์ได้ให้ทฤษฎีที่เกี่ยวกับปัญหานี้ไว้ดังนี้
- เครือข่าย ที่แสดงเป็นกราฟจะประกอบด้วยจุดเชื่อมโยง (Vertices) และเส้นเชื่อมโยงระหว่างจุด เรียกว่า arcs
- จุด ที่มีจำนวนเส้นที่เชื่อมออกไปยังจุดอื่นเป็นจำนวนคี่ เรียกว่า odd และถ้าจุดนั้นมีเส้นเชื่อมออกไปยังจุดอื่นเป็นจำนวนคู่ จะเรียกว่า even
- เส้นทางออยเลอร์ คือเส้นทางที่ลากผ่านเส้นต่าง ๆ ในเครือข่าย โดยแต่ละเส้นลากผ่านได้เพียงครั้งเดียว
- ทฤษฎีของออยเลอร์ กล่าวว่า ถ้าหากว่าเครือข่ายใดมีจุดที่เป็น odd มากกว่าสองขึ้นไป จะไม่มีทางสร้างเส้นทางออยเลอร์ได้
ลองพิจารณาจากปัญหากราฟต่อไปนี้

เฉลยปัญหา

มีเส้นทางออยเลอร์

มีเส้นทางออยเลอร์

ไม่มีเส้นทางออยเลอร์ เพราะมีจุดที่มีจำนวนเส้นเชื่อมออกไปยังจุดอื่นเป็นจำนวนคี่ มากกว่า 2 จุด (4 จุด)

มีเส้นทางออยเลอร์

มีเส้นทางออยเลอร์

ไม่มีเส้นทางออยเลอร์ เพราะมีจุดที่มีจำนวนเส้นเชื่อมออกไปยังจุดอื่นเป็นจำนวนคี่ มากกว่า 2 จุด

การแก้ปัญหาของออยเลอร์

อยเลอร์ เสนอวิธีการแก้ปัญหานี้โดยการแทนพื้นดิน แต่ละแห่งเป็นจุดซึ่งเรียกว่า จุดเชื่อมโยง (Vertices) และเรียกสะพานซึ่งเป็นการเชื่อมระหว่างจุดเหล่านี้ว่า เส้นเชื่อมโยงระหว่างจุด (arcs) ดังนั้นสะพานเคอนิกส์เบอร์กจึงเขียนแทนด้วยเส้นข้ามสะพานระหว่าง Vertices กับ arcs

เมื่อเขียนเส้นเชื่อมระหว่างจุด ปัญหาสะพานทั้งเจ็ด มีลักษณะเป็นกราฟ ดังรูป

ปัญหานี้จึงอยู่ที่การลากเส้นด้วยดินสอโดยการเขียนเส้นโดยไม่ต้องยกดินสอออกจากกระดาษ โดยแต่ละเส้นที่เชื่อมระหว่างจุดจะมีการลากผ่านเพียงครั้งเดียว

สังเกตว่ามีจุด 4 จุด และมีด้าน (arc) อยู่ทั้งหมดเป็นเลขคี่ (ในนี้มี 7 arcs) เริ่มจากจุดใดจุดหนึ่งแล้วลากตามเส้น เพื่อให้ผ่านเส้นครั้งเดียว ลองทดลองดูจะเห็นว่าไม่สามารถทำได้


ขอขอบคุณ   http://www.school.net.th/   ที่เอื้อเฟื้อข้อมูล ค่ะ