Examples

This gallery walks through every public feature of mathematicskit.graph_theory: shortest paths, minimum spanning trees, maximum flow/minimum cut, graph coloring, and spectral graph theory.

See also the narrative tutorial:

• Eigenvalues Everywhere

Each script in this gallery is self-contained and can be run directly with python examples/graph_theory/<section>/<script>.py.

Sections

• eulerian – Euler’s Seven Bridges of Königsberg and the odd-degree criterion.

• shortest_paths – Dijkstra, Bellman-Ford, and Floyd-Warshall.

• spanning_tree – Kruskal’s (scipy) vs. Prim’s (hand-rolled) MST.

• max_flow – maximum flow and the corresponding minimum cut.

• coloring – the four color theorem on a planar map, greedy vs. exact backtracking coloring.

• spectral – the graph Laplacian, algebraic connectivity, and spectral bipartition.

Assignment

Kuhn’s Hungarian method for optimal one-to-one assignments.

Kuhn’s Hungarian method: the assignment problem

Kuhn's Hungarian method: the assignment problem

Graph coloring

The four color theorem on a planar map: exact backtracking vs. greedy coloring.

The four color theorem: coloring a planar map

The four color theorem: coloring a planar map

Connected components

Components of graphs, and the giant component of random graphs.

Erdős and Rényi: the birth of the giant component

Erdős and Rényi: the birth of the giant component

Eulerian paths

Euler’s Seven Bridges of Königsberg and the odd-degree criterion.

Euler and the Seven Bridges of Königsberg

Euler and the Seven Bridges of Königsberg

Extremal graph theory

Turán’s theorem: the most edges a graph can have without a large clique.

Turán’s theorem: the densest clique-free graphs

Turán's theorem: the densest clique-free graphs

Hamiltonian cycles

Cycles that visit every vertex exactly once.

Hamilton’s icosian game

Hamilton's icosian game

Bipartite matching

Maximum matchings and König’s minimum vertex covers.

König’s theorem and Hopcroft-Karp matching

König's theorem and Hopcroft-Karp matching

Maximum flow

Maximum flow and the corresponding minimum cut.

Maximum flow and the max-flow min-cut theorem

Maximum flow and the max-flow min-cut theorem

Ranking

PageRank: ranking the vertices of a directed graph by a random walk.

PageRank: ranking pages by a random surfer

PageRank: ranking pages by a random surfer

Heuristic search

A* search: shortest paths guided by an estimate of the remaining distance.

A* search on a grid with obstacles

A* search on a grid with obstacles

Shortest paths

Dijkstra, Bellman-Ford, and Floyd-Warshall.

Dijkstra’s shortest-path algorithm (and when Bellman-Ford is needed)

Dijkstra's shortest-path algorithm (and when Bellman-Ford is needed)

Floyd-Warshall: all-pairs shortest paths

Floyd-Warshall: all-pairs shortest paths

Minimum spanning tree

Kruskal’s (scipy) vs. Prim’s (hand-rolled) MST.

Kruskal’s vs. Prim’s minimum spanning tree

Kruskal's vs. Prim's minimum spanning tree

Kirchhoff’s matrix-tree theorem

Kirchhoff's matrix-tree theorem

Spectral graph theory

The graph Laplacian, algebraic connectivity, and spectral bipartition.

Fiedler’s spectral bipartition of a “barbell” graph

Fiedler's spectral bipartition of a "barbell" graph