Paths and Cycles

One of the key problems in graphs is navigation. In particular, the problem is finding the shortest path between two vertices, whether that is finding the way out of a maze or navigating a road network. The lengths of the shortest paths give rise to a whole collection of natural measures such as the diameter of a graph. If instead of navigating from one vertex to another you would like to traverse the whole graph in some way, you are looking for cycles. Eulerian and Hamiltonian cycles provide paths that traverse every edge or vertex of graph.

Shortest Path

FindShortestPath — find the shortest path from the source to a target

ShortestPathFunction — represents a function that gives the shortest path in a graph

Distances

GraphDistance — the length of the shortest path between two vertices

GraphDistanceMatrix — the matrix of graph distances between all pairs of vertices

Longest Shortest Paths

VertexEccentricity — length of the longest shortest path to every other vertex

GraphRadius — minimum vertex eccentricity

GraphDiameter — maximum vertex eccentricity

GraphCenter — vertices with minimum eccentricity

GraphPeriphery — vertices with maximum eccentricity

Topological Paths

TopologicalSort — gives vertices in order compatible with graph topology

Cycles

FindEulerianCycle — find a cycle that traverses every edge exactly once

FindHamiltonianCycle — find a cycle that traverses every vertex exactly once

EulerianGraphQ   ▪ HamiltonianGraphQ

MORE ABOUT