Discrete Mathematics and Proof

Weighted and directed graphs

When every link of a network carries a price, a distance or a travel time, or can be used in one direction only, what is the cheapest way through it, and what can still be counted?

Unlocks

Spanning trees and minimum spanning treesDiscrete Mathematics and Proof Finding a shortest pathDiscrete Mathematics and Proof

Where you are 4 in Graphs, vertices and edges

Logic, proof and discrete math6

Introductory graph theory10

Graphs, vertices and edges4

Degree, the handshake lemma and complete graphs

Weighted and directed graphs

Graph isomorphism: when two drawings are the same graph Adjacency matrices and their powers

Why this exists

A graph says which pairs are linked and nothing more. A messenger needs the minutes each street takes, the dollars each handoff costs, and which streets run one way. A number on every edge makes a weighted graph, where a route’s weight is a sum and the direct link is not always the cheapest way. A direction on every edge makes a directed graph, the model for one-way streets, for task schedules and for any relation on a finite set. Degree splits into arrows in and arrows out, and the handshake count survives.

Definition

Graphs are written as in Degree, the handshake lemma and complete graphs: G = (V, E) is a simple graph with degrees \deg(v). Walks, paths and cycles are those of Walks, paths, cycles and connected graphs.

A weighted graph is a graph G = (V, E) with a weight function w : E \to \mathbb{R}. The number w(uv) is the weight of the edge uv: miles, minutes or dollars. Here every weight is positive unless said otherwise.
The weight of a walk W = (v_0, v_1, \ldots, v_k) is the sum of w(v_{i-1}v_i) for i = 1, \ldots, k, an edge counted each time it is used. The walk (u) has weight 0.
A cheapest walk from u to v is one of least weight; its weight is the weighted distance d_w(u, v), and d_w(u, v) = \infty if u and v are not joined.
A weight table has a row and a column for each vertex, with w(uv) in row u, column v, left blank when uv is not an edge. A graph’s weight table is symmetric.
A directed graph D = (V, A) is a finite nonempty set V of vertices with a set A of arcs, each an ordered pair (u, v) of two different vertices, drawn as an arrow from its tail u to its head v. The arcs (u, v) and (v, u) are different; D may have one, both or neither. There are no loops and no repeated arcs.
The out-degree \deg^+(v) counts the arcs with tail v, the in-degree \deg^-(v) those with head v.
A directed walk is a sequence (v_0, v_1, \ldots, v_k) with (v_{i-1}, v_i) \in A for each i. A directed path repeats no vertex. A directed cycle is a directed walk with k \ge 2, v_k = v_0 and v_0, \ldots, v_{k-1} all different; (u, v, u) counts, using two arcs.
A weighted directed graph carries w : A \to \mathbb{R}, with walk weights and d_w as above using directed walks. Its weight table, tail as row and head as column, need not be symmetric.

A relation R on a finite set V with no pair (a, a) is a directed graph with an arc (a, b) for each a \mathrel{R} b: its arrow diagram from Relations and their properties: reflexive, symmetric, antisymmetric, transitive.

Intuition

Figure 1Riding times in minutes. The edge DL weighs 14, but the route (D, K, L) weighs 11.

Think of weights as price tags on streets, paid each time a street is ridden. A tag has nothing to do with the drawn length: in Figure 1 the street DL costs 14 minutes, the detour (D, K, L) only 6 + 5 = 11.

Figure 2One-way streets with their riding times. The street between P and Q runs both ways, so it is two arcs.

An arc is a one-way street. It leaves one intersection and enters one, so counting arrows where they leave or where they arrive gives the same total. A two-way street is two arcs, as between P and Q in Figure 2.

Results

1. Cheapest walks are paths. With positive weights, if u and v are joined, a cheapest walk from u to v exists, and every cheapest walk from u to v is a path.

2. Triangle inequality. For all vertices u, v, x,

d_w(u, x) \le d_w(u, v) + d_w(v, x),

and d_w(u, v) \le w(uv) for every edge uv.

3. Heavy edges are never used. If w(uv) > d_w(u, v), no cheapest walk between any two vertices uses the edge uv, and deleting uv changes no weighted distance.

4. Directed handshake. In every directed graph D = (V, A),

\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = \lvert A \rvert.

5. Directed versions. Results 1 to 3 hold in a weighted directed graph with directed walks and arc weights w(u, v). But d_w(u, v) and d_w(v, u) can differ.

Why it is true

Result 1. Proof. Some walk runs from u to v, and cutting out the stretch between two visits to one vertex, until none repeats, leaves a path (Walks, paths, cycles and connected graphs). There are finitely many paths from u to v; let P be one of least weight. If a walk W from u to v is not a path, each cut removes at least one edge of positive weight, so the weight strictly drops, and the path left at the end weighs at least w(P). So w(W) > w(P). \square

Result 2. Proof. If a distance on the right is \infty there is nothing to prove. Otherwise a cheapest walk from u to v followed by one from v to x is a walk from u to x of weight d_w(u, v) + d_w(v, x), and the cheapest weighs no more. The edge uv alone is a walk of weight w(uv). \square

Result 3. Proof. If a cheapest walk uses uv at some step, replace that step by a cheapest walk from u to v (run backward if the step goes from v to u). The weight drops by w(uv) - d_w(u, v) > 0, a contradiction. So every cheapest walk survives deleting uv, and deleting an edge adds no walks, so no distance changes. \square

Result 4. Proof. Each arc has exactly one tail, so counting arcs tail by tail counts each once: \sum_v \deg^+(v) = \lvert A \rvert. Likewise for heads. \square

Result 5. The proofs above only follow walks forward, so they hold for directed walks. Example 4 shows the two directions differing.

Worked examples

Example 1

Every route to one drop point

Tiihu rides as a bike messenger. Figure 1 shows the dispatch office D, drop points K, L, M, N, and riding times in minutes. List every path from D to N with its weight and find d_w(D, N). Is the street DL ever worth riding?

Solution

By Result 1 a cheapest walk is a path, so listing paths is enough. A path leaves D along DK or DL; following every branch to N gives seven paths.

Path	Weight
(D, K, L, N)	6 + 5 + 8 = 19
(D, K, L, M, N)	6 + 5 + 3 + 4 = 18
(D, K, M, N)	6 + 9 + 4 = 19
(D, K, M, L, N)	6 + 9 + 3 + 8 = 26
(D, L, N)	14 + 8 = 22
(D, L, M, N)	14 + 3 + 4 = 21
(D, L, K, M, N)	14 + 5 + 9 + 4 = 32

So d_w(D, N) = 18, along the path with the most edges. The paths from D to L are (D, L), (D, K, L), (D, K, M, L), (D, K, M, N, L), weighing 14, 11, 18, 27. Since w(DL) = 14 > 11 = d_w(D, L), Result 3 says no cheapest route rides DL.

Example 2

A price table with links nobody should use

Tiihu’s company hands packages between offices W, X, Y, Z. The table gives the price in dollars of a direct handoff; a package may be relayed, paying each handoff. Find every weighted distance and the links on no cheapest route.

	W	X	Y	Z
W		9	4	15
X	9		3	5
Y	4	3		12
Z	15	5	12

Solution

By Result 1 only paths matter, and a path of two or more edges costs at least 3 + 4 = 7, the two smallest prices. So the links XY, WY, XZ, at 3, 4, 5, are cheapest.

The relay (W, Y, X) costs 4 + 3 = 7, so d_w(W, X) = 7 < 9. For Y and Z, a two-edge path under 12 uses two of the prices 3, 4, 5 that share an office: 3 + 4 joins W and X, and 3 + 5 is (Y, X, Z); three edges cost at least 3 + 4 + 5 = 12. So d_w(Y, Z) = 8. For W and Z the two-edge paths cost 14 and 16, and (W, Y, X, Z) costs 4 + 3 + 5 = 12, the least for three edges. So d_w(W, Z) = 12.

The links WX, YZ and WZ outweigh the distances between their ends, so by Result 3 no cheapest route uses them. The prices break the triangle inequality, 9 > 4 + 3; the distances obey it.

Example 3

A relation drawn as a directed graph

On V = \{1, 2, \ldots, 7\} let a \mathrel{R} b mean b = 2a or b = a + 3. Draw R, count its arcs, find the degrees, and find every directed path from 1 to 7.

Solution

The rule b = 2a gives (1, 2), (2, 4), (3, 6), and b = a + 3 gives (1, 4), (2, 5), (3, 6), (4, 7). The pair (3, 6) comes from both rules, but A is a set, so there are 6 arcs (Figure 3).

Figure 3The relation b = 2a or b = a + 3 on \{1, \ldots, 7\}, drawn as a directed graph.

For 1 to 7 the out-degrees are 2, 2, 1, 1, 0, 0, 0 and the in-degrees 0, 1, 0, 2, 1, 1, 1, each list summing to 6 as Result 4 says. The only arc into 7 is (4, 7), the arcs into 4 come from 1 and 2, and the only arc into 2 comes from 1. So the paths are (1, 4, 7) and (1, 2, 4, 7). Every arc has b > a, so numbers rise along a directed walk and there is no directed cycle.

Example 4

Directed distances need not be symmetric

In Figure 2, find d_w(P, T), d_w(T, P) and d_w(Q, R).

Solution

The only arc into T is (R, T), so a walk from P to T costs at least d_w(P, R) + 3. The arcs into R are (P, R) at 7 and (S, R) at 5. Before first reaching R, a walk from P gets to S only by (P, Q, S), since T is entered only from R, so arriving through S costs at least 4 + 6 + 5 = 15. So d_w(P, R) = 7 and d_w(P, T) = 7 + 3 = 10, by (P, R, T).

Going back, T’s only arc leads to S, S’s only arc to R, and the only arc into P is (Q, P). So the only path is (T, S, R, Q, P), and d_w(T, P) = 2 + 5 + 2 + 4 = 13, not 10.

From Q the arcs go to S and P, each with one way on to R: (Q, S, R) costs 6 + 5 = 11 and (Q, P, R) costs 4 + 7 = 11. So d_w(Q, R) = 11, by two different cheapest paths.

Example 5

Out-degree at least one forces a directed cycle

Prove that if every vertex of a directed graph D has out-degree at least 1, then D has a directed cycle. What does this say about a schedule of tasks?

Solution

Proof. Start at any vertex v_0. It has an arc out, to some v_1, which has an arc out, to some v_2, and so on. D has finitely many vertices, so some vertex repeats. Take j as small as possible with v_j = v_i for some i < j. Then v_i, \ldots, v_{j-1} are all different and (v_i, \ldots, v_j) is a closed directed walk. There are no loops, so v_{i+1} \ne v_i and j - i \ge 2: it is a directed cycle. \square

In a task schedule the vertices are tasks, with an arc (s, t) when s must finish before t starts. A directed cycle makes the schedule impossible: its first task done should have waited for the one before it. By the contrapositive, a schedule with no directed cycle has a task that nothing waits on.

Boundaries

Positive weights. With zero weights a cheapest path still exists, but a cheapest walk may repeat a vertex. With negative weights cheapest routes can fail to exist: if a route can pass a closed walk of negative weight, going around once more always lowers the total, so no walk is cheapest.
No loops. A relation with pairs (a, a) has loops. A loop adds 1 to both degrees of its vertex, so Result 4 holds, but Example 5’s cycle could then have length 1.
Finite vertex sets. On the integers the arcs (n, n + 1) give every out-degree 1 and no directed cycle, so Example 5 needs finiteness.
A weight table is not a matrix to multiply. Counting walks by multiplying matrices is Adjacency matrices and their powers.

Where this goes next

Listing paths, as in Example 1, fails in a large network; Finding a shortest path finds every d_w(u, v) from one start without a list. Spanning trees and minimum spanning trees asks the same data for the cheapest set of edges that keeps every vertex reachable. In an equivalence relation every arc has its reverse, so its arrow diagram is really a graph whose components are the classes.

Exercises

Weighted graphs

In Figure 1, find the weight of the walk (D, K, L, K, M). Then find d_w(K, N) and a cheapest path from K to N.
Each street ridden also costs Tiihu 10 minutes at its end, so add 10 to every weight in Figure 1. Find the new cheapest path from D to N and its weight.
The table gives riding distances in miles between four drop points. Find every weighted distance and the edges on no cheapest route.

	A	B	C	E
A		7	2	9
B	7		4	3
C	2	4		8
E	9	3	8

A triangle has edge weights 4, 7 and x, with x > 0. For which x is every edge a cheapest route between its own endpoints?
In a weighted graph, d_w(u, v) = 10 and d_w(v, x) = 7. Which values can d_w(u, x) take? Show that both ends of your range occur.

Directed graphs

Let V = \{1, 2, 3, 4, 5\} with arcs (1, 2), (1, 3), (2, 3), (3, 1), (3, 4), (4, 2), (5, 4). Find every in-degree and out-degree, name the vertex no other vertex can reach, and give a directed cycle of length 2 and one of length 3.
A directed graph has 10 vertices and 24 arcs, and every out-degree is 2 or 3. How many vertices have out-degree 3? What is the sum of the in-degrees?
On \{1, 2, \ldots, 8\} let a \mathrel{R} b mean b - a \in \{2, 5\}. Count the arcs, find the degrees, list every directed path from 1 to 8, and explain why there is no directed cycle.
In Figure 2, find d_w(T, Q), d_w(S, P) and d_w(Q, T), each with a cheapest path.
In Figure 2, the street from S to R closes. Which trips become impossible?
Tiihu’s morning has five tasks: print labels p, sort packages s, load bags \ell, check brakes b, ride out r. Labels come before sorting, sorting before loading, and loading and the brake check before riding out. Find every order of the tasks that respects this. Then a new rule puts riding out before printing labels. Show no order works.
The table gives one-way riding times in minutes, the row being the start. Find d_w(F, J), d_w(J, F), d_w(H, F) and d_w(J, H), and the arcs on no cheapest route.

from \ to	F	H	J
F		4	10
H	9		3
J	2	8

Reasoning

Prove that multiplying every weight by the same number c > 0 leaves the cheapest walks between every two vertices unchanged.
Prove that a directed graph with no directed cycle has a vertex of in-degree 0. In a task schedule, what is such a vertex?
Let R be a relation on a finite set that is irreflexive (no a \mathrel{R} a) and transitive. Prove that its directed graph has no directed cycle, and deduce that some element has no arrow into it.
Refute with a counterexample: “if every edge of a weighted graph is a cheapest route between its own endpoints, then a cheapest path between two vertices has as few edges as possible.”

Answers

6 + 5 + 5 + 9 = 25, with KL counted twice. d_w(K, N) = 12 by (K, L, M, N); every other path costs 13 or more.
(D, L, N), weight 22 + 20 = 42. A path with k edges gains 10k, so (D, K, L, M, N) becomes 58 and the others at least 49. Adding a constant favors fewer edges.
d_w(A, B) = 6 by (A, C, B); d_w(A, C) = 2; d_w(A, E) = 9, by AE and by (A, C, B, E); d_w(B, C) = 4; d_w(B, E) = 3; d_w(C, E) = 7 by (C, B, E). Unused: AB (7 > 6) and CE (8 > 7).
3 \le x \le 11. Each edge must weigh at most the other two together: x \le 4 + 7 and 7 \le 4 + x; 4 \le 7 + x always holds.
3 \le d_w(u, x) \le 17. The upper bound is Result 2; the lower comes from d_w(u, v) \le d_w(u, x) + d_w(x, v). A path u, v, x weighted 10, 7 gives 17; a path u, x, v weighted 3, 7 gives 3.
Out-degrees 2, 1, 2, 1, 1 and in-degrees 1, 2, 2, 2, 0 for 1 to 5, both summing to 7. Vertex 5 has in-degree 0. Length 2: (1, 3, 1). Length 3: (1, 2, 3, 1).
4: 3a + 2(10 - a) = 24 gives a = 4. The in-degrees sum to 24 by Result 4.
9 arcs: (1, 3), (2, 4), (3, 5), (4, 6), (5, 7), (6, 8), (1, 6), (2, 7), (3, 8). Out-degrees 2, 2, 2, 1, 1, 1, 0, 0, in-degrees 0, 0, 1, 1, 1, 2, 2, 2. Paths (1, 3, 8) and (1, 6, 8). Every arc has b > a, so no directed walk returns to its start.
d_w(T, Q) = 9 by (T, S, R, Q) and d_w(S, P) = 11 by (S, R, Q, P), each the only path. d_w(Q, T) = 14, by (Q, S, R, T) and by (Q, P, R, T).
S now has out-degree 0, so no trip starts at S, and T’s only arc leads to S, so from T only S is reachable. From P, Q, R every trip still works.
Arcs (p, s), (s, \ell), (\ell, r), (b, r). The chain p, s, \ell, r is forced and b goes anywhere before r: 4 orders. With (r, p) added, (p, s, \ell, r, p) is a directed cycle, so no order works (Example 5).
d_w(F, J) = 7 by (F, H, J); d_w(J, F) = 2; d_w(H, F) = 5 by (H, J, F); d_w(J, H) = 6 by (J, F, H). Unused arcs: (F, J), (H, F), (J, H).
Every walk’s weight is multiplied by c, and since c > 0, c\,w(W_1) \le c\,w(W_2) exactly when w(W_1) \le w(W_2). So the walks of least weight are the same. \square
Reverse every arc. Directed cycles reverse into directed cycles, so there are still none, and by Example 5 some vertex has out-degree 0; it had in-degree 0 before. \square In a schedule it is a task with nothing required before it, which can start first.
A directed cycle (v_0, v_1, \ldots, v_k = v_0) gives v_0 \mathrel{R} v_1, v_1 \mathrel{R} v_2, and so on, so by transitivity v_0 \mathrel{R} v_0, against irreflexivity. By Exercise 14 some vertex has in-degree 0. \square
Take w(ua) = w(ab) = w(bv) = 1 and w(uc) = w(cv) = 2. Each edge is a cheapest route between its ends, yet d_w(u, v) = 3 by (u, a, b, v), three edges, while (u, c, v) has two edges and weight 4.