Graph Theory, Networks and Voronoi Diagrams

In graph theory a graph is not a chart. It is a set of points, called vertices, and a set of connections between them, called edges. A road map is a graph once you keep only which places are joined.

The subject began in 1736, when Euler showed that no walk could cross each of the seven bridges of Königsberg exactly once. His argument used only the connections, never the shape of the town.

What are the parts of a graph?

Vertices, drawn as dots, and edges, drawn as lines. The degree of a vertex is the number of edge ends that meet it.

Add up every degree and the total is twice the number of edges, because each edge adds 1 at each of its two ends. So the number of odd-degree vertices is always even. See Vertices, Edges and Degree.

A simple graph has no loop and at most one edge between any pair of vertices. A complete graph joins every pair, so on n vertices it has $\frac{n\left(n-1\right)}{2}$n(n − 1)/2 edges. A bipartite graph splits the vertices into two sets, and every edge runs from one set to the other. See Simple, Complete and Bipartite Graphs.

A graph is connected when a route joins every pair of vertices. A tree is a connected graph with no cycle, and a tree on n vertices has exactly n − 1 edges: each new vertex needs one edge to join the tree, and a second edge would close a cycle. See Subgraphs, Connectedness and Trees.

A directed graph gives every edge an arrow. Arrows arriving give the in-degree and arrows leaving give the out-degree, and the graph is strongly connected when the arrows lead from any vertex to any other. See Directed Graphs and Strong Connectedness.

How do you store a network as numbers?

In a table with one row and one column for each vertex. Write 1 in row A, column B when an edge joins A to B, and 0 when none does. Without the labels, the numbers are the adjacency matrix. It is symmetric across the main diagonal, and each row total is a degree. See The Adjacency Matrix.

Multiply the matrix by itself. Row i, column j of $A^2$A² counts the walks of length 2 from i to j, because the product adds up, over every middle vertex k, the ways of going from i to k and then to j. In the same way $A^n$Aⁿ counts the walks of length n. See Counting Walks with Matrix Powers.

A weighted graph carries a number on each edge: a distance, a cost or a time. The table holds that weight in place of the 1. See The Weighted Adjacency Table.

What do the route words actually mean?

Each word says what may repeat. A walk is any sequence of edges, each one starting where the last ended. A trail uses no edge twice. A path uses no vertex twice. A circuit is a trail that ends where it began, and a cycle is a circuit that repeats no vertex except the one at both ends. See Walks, Trails, Paths, Circuits and Cycles.

An Eulerian circuit is a closed trail that uses every edge exactly once. A connected graph has one exactly when every vertex has even degree. With exactly two odd vertices the graph has an Eulerian trail instead, from one odd vertex to the other.

The reason is a count. Each time a trail passes through a vertex it uses one edge to arrive and one to leave, so every vertex except the start and the finish needs an even degree, and those two each have one unpaired edge. Any other number of odd vertices allows neither, and Königsberg had four. See Eulerian Trails and Circuits.

A Hamiltonian cycle visits every vertex exactly once and returns to the start. There is no degree test for it, so routes have to be tried one by one. See Hamiltonian Paths and Cycles.

What is the cheapest way to connect everything?

With a minimum spanning tree: a set of edges that joins every vertex, has no cycle, and has the least total weight. Two greedy algorithms find one, meaning each step takes the cheapest edge available without looking ahead.

Kruskal's algorithm sorts the edges by weight and works down the list. Take each edge unless it would close a cycle, and stop when n − 1 edges are in. See Kruskal's Algorithm for a Spanning Tree.

Prim's algorithm grows one tree from a starting vertex: at each step take the cheapest edge that leaves the tree and reaches a new vertex. The matrix method runs it on the weighted table. Cross out the column of each vertex in the tree, find the smallest entry left in the rows of those vertices, circle it, and that vertex joins. See Prim's Algorithm and the Matrix Method.

Routes that must cover everything

The Chinese postman problem asks for the shortest closed route that uses every edge at least once. If every vertex has even degree, an Eulerian circuit does it. Otherwise pair up the odd vertices, find the shortest route between each pair, and walk those edges twice. With four odd vertices there are three ways to pair them, so cost all three and take the cheapest. See The Chinese Postman Problem.

The traveling salesman problem asks for the cheapest cycle that visits every vertex once. No efficient exact method is known, so the answer is trapped between an upper bound and a lower bound. See The Traveling Salesman Problem.

The nearest-neighbor algorithm builds a tour: start at a vertex, always move to the nearest vertex not yet visited, and return home at the end. The best tour cannot cost more than a tour already in hand, so this cost is an upper bound. See The Nearest-Neighbor Upper Bound.

For a lower bound, delete one vertex and every edge that touches it, find a minimum spanning tree of what is left, and add back the two cheapest deleted edges. Every tour uses two edges at the deleted vertex and at least a spanning tree of the rest, so no tour can cost less. See The Deleted-Vertex Lower Bound.

How does a Voronoi diagram answer "what is nearest"?

By dividing the plane before the question is asked. The points equally far from two sites A and B lie on the perpendicular bisector of AB, and that line splits the plane into the side nearer A and the side nearer B.

With more sites, draw the bisector of every pair and keep, for each site, the piece of the plane where it is nearest. Each piece is a cell, so the nearest site to any point is read off from the cell it lies in. See Voronoi Diagrams.

To find the equation of the edge between A at (1, 2) and B at (5, 4), first find the midpoint of AB, which is (3, 3). The gradient of AB is $\left(4-2\right)÷\left(5-1\right)=\frac{1}{2}$(4 − 2) ÷ (5 − 1) = 1/2, so the perpendicular gradient is the negative reciprocal, −2. The edge is the line through (3, 3) with gradient −2: y − 3 = −2(x − 3), which rearranges to y = −2x + 9. See The Equation of a Voronoi Edge.

Adding a new site cuts a new cell out of its neighbors, so the cells around it can only shrink. See Finding the Nearest Site.

The toxic waste dump problem asks for the point farthest from every site. Inside a cell you can always step farther from the nearest site, so the answer is at a Voronoi vertex, where three sites are equally near, or on the border of the region. Test every vertex and every corner and keep the largest circle that contains no site: its center is the answer. See The Toxic Waste Dump Problem.

A Voronoi cell is a polygon, so its area comes from its corners by ordinary mensuration. See The Area of a Voronoi Cell.

The mistakes worth naming

• Mixing up Eulerian and Hamiltonian. Eulerian is about edges and Hamiltonian is about vertices.
• Counting a loop once. A loop adds 2 to the degree, one for each end.
• Taking one edge too many in Kruskal's algorithm. A spanning tree on n vertices has n − 1 edges.
• Treating the nearest-neighbor tour as the best tour. It is an upper bound, and often not a close one.
• Drawing Voronoi edges by eye. Each edge is a perpendicular bisector, so find the midpoint and the perpendicular gradient.
• Trusting the drawing. Two drawings of the same graph can look nothing alike. Only the connections count.

Where this leads next

Matrix powers count walks here in the same way they track probabilities in the matrices and Markov chains guide. A Voronoi edge is found with the midpoint and gradient methods of the coordinate geometry guide. The degree count and the Königsberg argument are counting proofs of the kind set out in the logic and proof guide.

Learn this properly in the app

Math Challenge teaches each of these as an illustrated lesson, with the network drawn and the algorithm run one step at a time, followed by practice questions with worked explanations.