ทฤษฎีกราฟ 4

Euler Circuit คือ กราฟที่ต้องเดินผ่านทุกด้าน ไม่มีการซ้ำด้าน เริ่มตรงไหนจบตรงนั้นโดยจุดยอดทุกจุดจะมีดีกรีคู่

ภาพประกอบจาก https://www.geeksforgeeks.org/wp-content/uploads/Euler2.png

จากภาพจะพบว่าทุกจุดยอดมีดีกรีคู่ เมื่อมีการเดินผ่านทุกด้านโดยไม่ซ้ำจุดเริ่มต้นและสิ้นสุดจะเป็นจุดเดียวกัน

Euler Path คือ กราฟที่ต้องเดินผ่านทุกด้าน ไม่มีการซ้ำด้าน แต่เริ่มต้นกับสิ้นสุดต้องเป็นคนละจุดสามารถสังเกตได้จากกราฟว่าจะมีสองจุดยอดเท่านั้นที่มีดีกรีเป็นเลขคี่

ภาพประกอบจาก https://www.geeksforgeeks.org/eulerian-path-and-circuit/

จากภาพพบว่ามีสองจุดเท่านั้นที่มีดีกรีคี่ คือ จุด 0 และ จุด 4 เมื่อมีการเดินผ่านทุกด้านพบว่าจุดเริ่มต้นและสิ้นสุดเป็นคนละจุดกัน 

Hamilton Circuit คือ กราฟที่ไม่จำเป็นต้องเดินผ่านทุกด้าน จุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ไม่ซ้ำจุด

ภาพประกอบจาก https://slideplayer.com/slide/7549367/

เมื่อเดินผ่านทุกจุดพบว่าจุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ทั้งสองภาพ

Hamilton Path คือ กราฟที่ไม่จำเป็นต้องเดินผ่านทุกด้าน จุดเริ่มต้นและสิ้นสุดเป็นคนละจุดกัน ไม่ซ้ำจุด

ภาพประกอบจาก https://slideplayer.com/slide/7549367/

เมื่อเดินผ่านทุกจุดพบว่าจุดเริ่มต้นและสิ้นสุดเป็นคนละจุดกัน ทั้งสองภาพ

กราฟแบบถ่วงน้ำหนัก (Weighted simple graphs) คือ กราฟที่เส้นเชื่อมมีน้ำหนักแล้วมีค่าน้ำหนักไม่ติดลบ โดยค่าน้ำหนักจะอยู่บนเส้นเชื่อมต่างๆ ซึ่งสามารถนำมาเสนอในรูปของ Adjacency matric ได้

ภาพประกอบจาก https://www.thecrazyprogrammer.com/2014/03/representation-of-graphs-adjacency-matrix-and-adjacency-list.html

Shortest Path Problem คือการหาเส้นทางที่สั้นที่สุดระหว่างจุดยอดสองจุดภายในกราฟซึ่งสามารถหาได้จากค่าน้ำหนักของเส้นเชื่อมแต่ละเส้น หรือก็คือหาผลรวมของค่าน้ำหนักของกราฟเส้นทางใดที่น้อยก็คือเส้นทางที่สุดซึ่งวิธีการนี้สามารถนำมาใช้ในแอปพลิเคชั่น Google Map ในการเลือกเส้นทางที่ใกล้ที่สุด

Dijkstra’s Algorithm คือการหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นถึงจุดยอดที่ต้องการในกราฟ

โดยมีขั้นตอนดังนี้ กำหนดให้จุดเริ่มต้นเป็น 0 และจุดอื่นที่นอกเหนือจากจุดเริ่มต้นเป็น ∞  จากนั้นพิจารณาจุดที่ต่อกับจุดเริ่มต้นว่ามีน้ำหนักเส้นเชื่อมเท่าใด ให้เลือกค่าน้ำหนักผลรวมที่น้อยที่สุดแล้วเขียนลงบนจุดพิจารณาทุกจุดที่เชื่อมกับจุดเริ่มต้นแล้วเลือกจุดที่มีค่าน้ำหนักรวมน้อยที่สุด ทำเช่นนี้ไปเรื่อยๆจนได้คำตอบ

 

ภาพประกอบจาก  http://www.wikiwand.com/th/

Warshall ’s Algorithm มีวิธีการดังนี้

ขั้นตอนแรกคือเขียน Adjacency matric ของกราฟดังกล่าวออกมา จากนั้นให้เลือกแถวที่ 1 หลักที่ 1 สังเกตที่แถวและหลักว่า แถวและหลักใดไม่เป็น 0 ให้ลากเส้นลงมาตัด ให้ทำเช่นนี้ไปเรื่อยๆโดยเลือกแถวและหลักถัดมาจนกว่าจะครบ

Floyd’s Algorithm มีขั้นตอนวิธีการคล้ายคลึงกับ Warshall’s Algorithm แต่จะมีข้อแตกต่างกันที่จุดยอดที่ไม่มีเส้นเชื่อมถึงกันจะแทนด้วยเครื่องหมาย ∞

จากกราฟจะดำเนินการตามวิธีของ Floyd’s Algorithm ได้ดังภาพข้างล่างโดยทำการเลือกแถวที่ 1 หลักที่ 1 แล้วสังเกตว่าหลักและแถวใดที่ไม่ใช่เครื่องหมาย ∞ ให้ลากเส้นมาตัดกันทำเช่นนี้ไปเรื่อยๆจนครบ

ภาพประกอบจาก https://www.slideshare.net/NishithLakhlani/floyd-warshall-algorithm-5438235

ขอขอบคุณแหล่งข้อมูลจาก

:  http://www.mwit.ac.th/~noon/style/graph.pdf

  http://maths.sci.ku.ac.th/suriya/Slide/Discrete/Slide6-1.pdf
  http://th.tni.wikia.com/wiki

  http://staff.cs.psu.ac.th/pennee/344-281/09-Graph-Lec.pdf
  http://www.scimath.org/lesson-mathematics/item/7334-2017-06-17-14-37-32
  https://www.geeksforgeeks.org/a-search-algorithm/
  https://cs.winona.edu/lin/cs440/ch08-2.pdf
  https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
  หนังสือ Discrete Mathematics and Its Applications