Introduction to Graph Theory Part 4 : Eulerian path

Degrees ของ vertice คือ จำนวน edges ที่เชื่อมกับ vertice นั้น



Eulerain's path และ Eulerian circle


ลองเล่นเกมส์นี้ดู ลากเส้นด้วยปากกาผ่านจุดทุกจุดที่กำหนดให้ โดยไม่ยกปากกาและห้ามไม่ให้ลากเ


รูปที่ 1

ถ้าเริ่มต้นที่จุด A (สามารถเริ่มจุดก็ได้) ผลที่ได้อาจเป็นตามที่แสดงในรูปที่ 2 เส้นทางที่ได้มาเรียกว่า "Eulerain path" หรือ "Eulerian trail (walk)"


รูปที่ 2

ถ้าหากเพิ่มกติกาว่าจุดเริ่มต้นและจุดสุดท้ายต้องเป็นจุดเดียวกัน อาจได้ผลดังรูปที่ 3 เส้นทางที่ได้มาเรียกว่า "Eulerian circle" หรือ "Eulerian circuit" หรือ "Eulerian tour"


รูปที่ 3

• Eulerain path คือเส้นทาง (path) ภายใน graph ที่ไปสู่ vertices ทุก vertices โดยไม่ใช้ edge ซ้ำกันเลย


• Eulerain circuit คือ Eulerain path ที่นำกลับมาสู่ vertice เริ่มต้น



ตัวอย่างการใช้ Eulerian circuit


1. การเดินทาง

ปัญหา : ต้องการเตินทางท่องเที่ยวโดยรถยนต์ในจังหวัดทางภาคเหนือตามรูปที่ 4 ต้องการแวะให้ครบทุกจังหวัดโดยเริ่มตันที่เชียงใหม่ ใช้เส้นทางหลวงระหว่างจังหวัดและไม่ต้องการใช้เส้นทางซ้ำ และปิดการเดินทางที่เชียงใหม่


รูปที่ 4

การหาคำตอบ : การแก้ปัญหาข้อนี้คือการสร้าง Eulerian circuit จาก graph นี้ 



หรือ



2. Floor plan

ปัญหา 2.1 : จากรูป Floor plan ที่ให้มา เป็นไปได้หรือไม่ที่จะเดินไปยังห้องทุกห้องโดยไม่มีใช้เส้นทางซ้ำ

ปัญหา 2.2 : จากรูป Floor plan ที่ให้มา เป็นไปได้หรือไม่ที่จะเดินจากห้อง A ไปทุกห้องโดยการผ่านประตูทุกบานโดยไม่เดินซ้ำทางเดิม และกลับสู่ห้อง A


รูปที่ 5

เส้นทางการเดินที่จะไปยังทุกห้องโดยไม่ต้องเดินย้อนกลับทางเดิม คือการสร้าง Eulerain path ขึ้นมา อาจเริ่มต้นจากห้องใดห้องหนึ่งก็ได้ ในที่นี้จะเริ่มจาก A,B,C,D,E,F,G ตามลำดับ แต่ในคำถามที่สองเป็นคำถามเกี่ยวกับการสร้าง Eulerian circle เพื่อให้เห็นภาพชัดขึ้น จะสร้าง graph ขึ้นมา


รูปที่ 6

การพยายามหา Eulerian circle ในปัญหาข้อนี้จะไม่สามารถทำได้ เพราะลักษณะของ graph ขัดกับ Euler's theorm ที่ว่าไว้ดังนี้


A connected graph has an Euler cycle if and only if every vertex has even degree.

vertex C,D,E และ F มี degrees เป็น 3 ดังนั้นปัญหาที่ 2.2 จึงไม่สามารถแก้ได้


Hamilton path, Hamilton circle


Hamilton path คือ path ที่ผ่านแต่ละ vertex ใน graph เพียง 1 ครั้ง (Eulerian path อาจผ่าน vertext ซ้ำได้) และ Hamilton circle คือ Hamilton path ที่ต้องวนกลับมาที่ vertex เริ่มต้น


รูปที่ 6 ตัวอย่าง graph ที่มี Hamilton circles

Eulerian circle อนุญาตให้เข้าถึง vertex ซ้ำได้ แต่ไม่อนุญาตให้ใช้ edge ซ้ำ


Hamilton circle ไม่อนุญาตให้เข้าถึง vertex ซ้ำ ทำให้ไม่สามารถใช้ edge ซ้ำไปด้วย


รูปที่ 7

รูปที่ 7 (a) เส้นทางตามเส้นสีแดงสามารถแสดงในรูปของ edges ได้หลายแบบ เช่น (A,C,D,E,B,A) , (A,B,E,D,C,A), ฯล ทุก edges จะเป็นทั้ง Eulerian circle และ Hamilton circle ส่วนรูปที่ 7 B path ตามเส้นสีฟ้าจะเป็นได้แต่ Eulerian circle เท่านั้น เพราะ vertex C ถูกใช้ซ้ำ ตัวอย่างนี้แสดงให้เห็นความต่างระหว่าง circle ทั้งสองชนิด

ความคิดเห็น

แสดงความคิดเห็น