ระยะทางในทฤษฎีกราฟ (Distance in Graph Theory) ความหมายและหลักการ

ในสาขาคณิตศาสตร์ที่เรียกว่า ทฤษฎีกราฟ (Graph Theory) ระยะทางระหว่างจุดยอด (Vertices) สองจุดในกราฟ คือจำนวนเส้นเชื่อม (Edges) ในเส้นทางที่สั้นที่สุด (Shortest Path) ที่เชื่อมต่อจุดทั้งสองเข้าด้วยกัน ซึ่งมักเรียกกันว่า ระยะทางจีโอเดสิก (Geodesic Distance) หรือ ระยะทางเส้นทางสั้นที่สุด (Shortest-path Distance)

สิ่งสำคัญที่ควรทราบคือ ระหว่างจุดยอดสองจุดอาจมีเส้นทางที่สั้นที่สุดได้มากกว่าหนึ่งเส้นทาง และหากไม่มีเส้นทางใดที่เชื่อมต่อจุดยอดทั้งสองเลย (เช่น อยู่คนละส่วนประกอบที่เชื่อมต่อกัน) ตามธรรมเนียมปฏิบัติจะกำหนดให้ระยะทางนั้นมีค่าเป็น อนันต์ (Infinite)

การคำนวณและตัวแทนในรูปแบบคอมพิวเตอร์

ในทางคอมพิวเตอร์ ระยะทางระหว่างโหนดในกราฟสามารถแสดงได้ด้วย เมทริกซ์ระยะทาง (Distance Matrix) หรือที่เรียกว่าเมทริกซ์เส้นทางสั้นที่สุดระหว่างทุกคู่ (All-pairs shortest-path matrix) ซึ่งเป็นเมทริกซ์จัตุรัสที่ระบุความยาวของเส้นทางที่สั้นที่สุดระหว่างจุดยอดทุกคู่ในกราฟ

เมทริกซ์ระยะทางมีการประยุกต์ใช้ในหลายด้าน เช่น โทรคมนาคม และเคมี โดยในทฤษฎีกราฟทางเคมี มีการใช้ดัชนีทางทอพอโลยีหลายตัวที่สร้างมาจากเมทริกซ์ระยะทางเพื่อระบุลักษณะโครงสร้างของโมเลกุล นอกจากนี้ยังมีการใช้ การฝังตัวเชิงเมตริก (Metric Embeddings) เพื่อแปลงจุดยอดของกราฟให้เป็นจุดในพื้นที่ทางเรขาคณิต (เช่น พื้นที่ยุคลิด) เพื่อรักษาค่าระยะทางให้ใกล้เคียงที่สุด

ระยะทางในกราฟระบุทิศทาง (Directed Graph Distance)

ในกราฟระบุทิศทาง (Directed Graph) เส้นเชื่อมจะมีทิศทางที่กำหนดไว้ ทำให้การเดินทางระหว่างจุดยอดไม่จำเป็นต้องเป็นการเดินทางแบบสองทิศทาง ส่งผลให้ระยะทางจากจุด u ไปยัง v อาจแตกต่างจากระยะทางจาก v ไปยัง u

ด้วยเหตุนี้ ระยะทางในกราฟระบุทิศทางจึงถูกจัดว่าเป็น Quasi-metric แทนที่จะเป็น Metric ปกติ เนื่องจากไม่รับประกันว่า d(u,v) = d(v,u) และในบางกรณี d(u,v) อาจไม่มีนิยามหากไม่มีเส้นทางระบุทิศทางจาก u ไปยัง v

แนวคิดที่เกี่ยวข้อง

ความเยื้องศูนย์ (Eccentricity): ความเยื้องศูนย์ ϵ(v) ของจุดยอด v คือระยะทางที่ไกลที่สุดระหว่าง v และจุดยอดอื่นๆ ทั้งหมดในกราฟ

รัศมีของกราฟ (Radius): รัศมี r ของกราฟคือค่าความเยื้องศูนย์ที่น้อยที่สุดของจุดยอดใดๆ ในกราฟ