Graph Geodesic

 

A shortest path between two graph vertices  of a graph (Skiena 1990, p. 225). There may be more than one different shortest paths, all of the same length. Graph geodesics may be found using a breadth-first traversal (Moore 1959) or using Dijkstra's algorithm (Skiena 1990, p. 225). One (of possibly several) graph geodesics of a graph  from vertex  to vertex  can be found in the Wolfram Language using FindShortestPath[g, u, v]. The length of the graph geodesic between these points  is called the graph distance between  and .

The length of the maximum geodesic in a given graph is called the graph diameter, and the length of the minimum geodesic is called the graph radius.

The matrix  consisting of all graph distances from vertex  to vertex  is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix.

A graph which possesses a unique geodesic between every pair of vertices is known as a geodetic graph.

---

REFERENCES

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 14, 1994.

Moore, E. F. "The Shortest Path through a Maze." In Proc. Internat. Symp. Switching Th., Part II. Cambridge, MA: Harvard University Press, pp. 285-292, 1959.

Skiena, S. "Shortest Paths." §6.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 225-253, 1990.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength