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

 

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

 

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

 

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

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

ทฤษฎีกราฟของออยเลอร์

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

%d bloggers like this: