Ch. 7: Digraphs

From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 7.1. Strong Digraphs 7.2. Tournaments 7.3. Excursion: Decision-Making 7.4. Exploration: Wine Bottle Problems

62 flashcards · Mathematics · by lakesare

Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses

What is a digraph DDD , and what is an arc?
A finite nonempty vertex set VVV and a set EEE of ordered pairs of distinct vertices; each pair (u,v)∈E(u, v) \in E(u,v)∈E is an arc (directed edge). No loops, and (u,v)(u, v)(u,v) is a different arc from (v,u)(v, u)(v,u) .
A digraph in which, for every two distinct vertices u,vu, vu,v , at most one of (u,v)(u, v)(u,v) and (v,u)(v, u)(v,u) is an arc, is an oriented graph.
Equivalently, it is obtained by giving each edge of a graph GGG a direction; it is then an orientation of GGG .
When is a digraph HHH a subdigraph of a digraph DDD ?
When V(H)⊆V(D)V(H) \subseteq V(D)V(H)⊆V(D) and E(H)⊆E(D)E(H) \subseteq E(D)E(H)⊆E(D) .
When is a digraph symmetric, and why does the book rarely study symmetric digraphs?
Whenever (u,v)(u, v)(u,v) is an arc, so is (v,u)(v, u)(v,u) . Studying them is the same as studying graphs. Each pair (u,v),(v,u)(u, v), (v, u)(u,v),(v,u) plays the role of one edge uvuvuv .
(u,v)(u, v)(u,v) is an arc of a digraph. Which vertex is adjacent to which, and what are the outdegree od⁡v\operatorname{od} vodv and indegree id⁡v\operatorname{id} vidv ?
uuu is adjacent to vvv , and vvv is adjacent from uuu . od⁡v\operatorname{od} vodv = number of vertices vvv is adjacent to; id⁡v\operatorname{id} vidv = number of vertices vvv is adjacent from. uuu and vvv are both incident with the arc (u,v)(u, v)(u,v) .
The First Theorem of Digraph Theory (Theorem 7.1) If DDD is a digraph of size mmm ( mmm arcs) with V(D)={v1,…,vn}V(D) = \{v_1, \dots, v_n\}V(D)={v1,…,vn} , then ∑i=1nod⁡vi= ?\displaystyle\sum_{i=1}^n \operatorname{od} v_i = \; ?i=1∑nodvi=?
∑i=1nod⁡vi=∑i=1nid⁡vi=m\displaystyle\sum_{i=1}^n \operatorname{od} v_i = \sum_{i=1}^n \operatorname{id} v_i = \boldsymbol{m}i=1∑nodvi=i=1∑nidvi=m Each arc (u,v)(u, v)(u,v) is counted once in od⁡u\operatorname{od} uodu and once in id⁡v\operatorname{id} vidv .
In a digraph, what is a (directed) uuu – vvv walk, and what is its length?
A sequence (u=u0,u1,…,uk=v)(u = u_0, u_1, \dots, u_k = v)(u=u0,u1,…,uk=v) of vertices with uiu_iui adjacent to ui+1u_{i+1}ui+1 for every iii ; its length is kkk , the number of arc occurrences. Every walk in a digraph follows the directions of the arcs.
In a digraph, what is a (directed) trail, and what is a (directed) path?
Trail: a walk with no repeated arc. Path: a walk with no repeated vertex.
In a digraph, what is a circuit, and what is a cycle?
Circuit: a closed trail of length at least 2. Cycle: a closed walk of length at least 2 with no repeated vertex except the first = last. A walk is closed if it starts and ends at the same vertex, open otherwise.
Can a digraph have a cycle of length 2?
Yes: (t,w,t)(t, w, t)(t,w,t) , whenever both (t,w)(t, w)(t,w) and (w,t)(w, t)(w,t) are arcs. So an oriented graph (or a tournament) has no cycle of length 2, but a general digraph can.
In this digraph DDD , which kind of walk is (v,t,w,t,u,v)(v, t, w, t, u, v)(v,t,w,t,u,v) , and which kind is (v,x,y,w,v)(v, x, y, w, v)(v,x,y,w,v) ?
(v,t,w,t,u,v)(v, t, w, t, u, v)(v,t,w,t,u,v) : a circuit but not a cycle ( ttt repeats). (v,x,y,w,v)(v, x, y, w, v)(v,x,y,w,v) : a cycle of length 4. (y,w,v,x,y,w,t)(y, w, v, x, y, w, t)(y,w,v,x,y,w,t) is not even a trail: the arc (y,w)(y, w)(y,w) occurs twice.
What is the underlying graph of a digraph DDD ?
Replace each arc (u,v)(u, v)(u,v) , and each pair (u,v),(v,u)(u, v), (v, u)(u,v),(v,u) , by the single edge uvuvuv . If DDD is an orientation of a graph GGG , then GGG is the underlying graph of DDD . A digraph DDD and its underlying graph GGG .
What is the difference between a connected (weakly connected) digraph and a strong (strongly connected) digraph?
Connected: the underlying graph is connected. Strong: there is a uuu – vvv path and a vvv – uuu path for every two vertices u,vu, vu,v . Connected but not strong: there is no path from zzz to any other vertex.
In a digraph, what is the directed distance d⃗(u,v)\vec{d}(u, v)d(u,v) , and what is a uuu – vvv geodesic?
d⃗(u,v)\vec{d}(u, v)d(u,v) = the length of a shortest uuu – vvv path; a geodesic is a uuu – vvv path of length d⃗(u,v)\vec{d}(u, v)d(u,v) . d⃗(u,v)\vec{d}(u, v)d(u,v) is defined for every pair u,vu, vu,v exactly when DDD is strong. It need not equal d⃗(v,u)\vec{d}(v, u)d(v,u) .
Every vertex of a digraph has positive outdegree and positive indegree. Must the digraph be strong?
No: the condition is necessary for being strong, but not sufficient. Every vertex has od⁡>0\operatorname{od} > 0od>0 and id⁡>0\operatorname{id} > 0id>0 , yet there is no uuu – xxx path.
Theorem 7.2 If a digraph DDD contains a uuu – vvv walk of length lll , then … ?
DDD contains a uuu – vvv path of length at most lll .
If a digraph contains a uuu – vvv walk of length lll , then it contains a uuu – vvv path of length at most lll .What is the key idea of the proof?
Take a shortest uuu – vvv walk WWW . If ui=uju_i = u_jui=uj with i<ji < ji<j , deleting ui+1,…,uju_{i+1}, \dots, u_jui+1,…,uj gives a shorter uuu – vvv walk, a contradiction. So WWW is a path.
Theorem 7.3. Complete: a digraph DDD is strong if and only if … ?
DDD contains a closed spanning walk. (A spanning walk visits every vertex.)
A digraph is strong if and only if it contains a closed spanning walk. (Also used: a uuu – vvv walk always contains a uuu – vvv path.)Why does a closed spanning walk W=(w0,w1,…,wk=w0)W = (w_0, w_1, \dots, w_k = w_0)W=(w0,w1,…,wk=w0) make the digraph strong?
For u=wiu = w_iu=wi and v=wjv = w_jv=wj ( i<ji < ji<j ), WWW splits into a uuu – vvv walk (wi,…,wj)(w_i, \dots, w_j)(wi,…,wj) and a vvv – uuu walk (wj,…,wk=w0,…,wi)(w_j, \dots, w_k = w_0, \dots, w_i)(wj,…,wk=w0,…,wi) , and each walk contains a path.
A digraph is strong if and only if it contains a closed spanning walk.A strong digraph has vertices v1,…,vnv_1, \dots, v_nv1,…,vn . How does the proof build a closed spanning walk?
Concatenate a v1v_1v1 – v2v_2v2 path, a v2v_2v2 – v3v_3v3 path, …, a vn−1v_{n-1}vn−1 – vnv_nvn path and a vnv_nvn – v1v_1v1 path. Each of the first n−1n - 1n−1 paths has its final vertex dropped, so consecutive paths join up without repeating it.
What is an Eulerian circuit in a digraph, and what is an Eulerian digraph?
Eulerian circuit: a circuit containing every arc of DDD . Eulerian digraph: a digraph that contains an Eulerian circuit. Eulerian circuit: (u,v,w,y,z,x,y,x,w,u)(u, v, w, y, z, x, y, x, w, u)(u,v,w,y,z,x,y,x,w,u) .
Theorem 7.4. Complete: a nontrivial connected digraph DDD is Eulerian if and only if … ?
od⁡v=id⁡v\boldsymbol{\operatorname{od} v = \operatorname{id} v}odv=idv for every vertex vvv of DDD . The digraph version of: a nontrivial connected graph is Eulerian iff every vertex has even degree.
A nontrivial connected digraph is Eulerian if and only if od⁡v=id⁡v\operatorname{od} v = \operatorname{id} vodv=idv for every vertex vvv .Why does an Eulerian circuit CCC force od⁡v=id⁡v\operatorname{od} v = \operatorname{id} vodv=idv ?
Each time CCC passes through vvv , it uses one arc entering vvv and one leaving vvv . If vvv is the initial vertex of CCC : the first arc leaves vvv and the last arc enters vvv , which also balances.
DDD is a nontrivial connected digraph with od⁡v=id⁡v\operatorname{od} v = \operatorname{id} vodv=idv for every vertex vvv , and TTT is a trail of maximum length starting at a vertex uuu .Why must TTT end at uuu ?
If TTT ended at v≠uv \ne uv=u , met kkk times, then TTT uses kkk arcs into vvv but only k−1k - 1k−1 out of vvv ; since od⁡v=id⁡v\operatorname{od} v = \operatorname{id} vodv=idv , an unused arc leaves vvv and extends TTT . So TTT is a circuit. This is the first step in showing that od⁡v=id⁡v\operatorname{od} v = \operatorname{id} vodv=idv everywhere makes a connected digraph Eulerian.
DDD is a nontrivial connected digraph with od⁡v=id⁡v\operatorname{od} v = \operatorname{id} vodv=idv for every vertex vvv , and CCC is a circuit of maximum length in DDD .Why does CCC contain every arc of DDD ?
Otherwise some vertex www on CCC has an arc not on CCC ; in D′=D−E(C)D' = D - E(C)D′=D−E(C) , still od⁡=id⁡\operatorname{od} = \operatorname{id}od=id , so a longest trail from www in D′D'D′ is a circuit C′C'C′ . Splicing C′C'C′ into CCC at www gives a longer circuit. www exists because DDD is connected.
These graphs model the streets of two towns. Why can every street of Town A be made one-way so that one can still drive legally between any two places, but not in Town B?
GBG_BGB has a bridge, GAG_AGA has none, and a connected graph has a strong orientation exactly when it has no bridges. A strong orientation DAD_ADA of GAG_AGA .
Robbins' theorem (Theorem 7.5). Complete: a nontrivial connected graph GGG has a strong orientation if and only if … ?
GGG contains no bridges (equivalently, GGG is 2-edge-connected).
Robbins: a nontrivial connected graph has a strong orientation if and only if it contains no bridges.Why does no orientation of a graph with a bridge uvuvuv give a strong digraph?
Say the bridge is oriented as (u,v)(u, v)(u,v) . A vvv – uuu path would be a vvv – uuu path in GGG avoiding uvuvuv , and with uvuvuv it would form a cycle containing the bridge, which is impossible.
Robbins: a nontrivial connected graph has a strong orientation if and only if it contains no bridges.For a bridgeless GGG : take a largest vertex set SSS whose edges can be oriented so that any two vertices of SSS reach each other. Why is S=V(G)S = V(G)S=V(G) ?
Otherwise take an edge uvuvuv with u∈Su \in Su∈S , v∉Sv \notin Sv∈/S . It lies on a cycle (not a bridge); follow the cycle from uuu through vvv to the first vertex www back in SSS , orienting the edges along the way. Then S∪TS \cup TS∪T is larger, where T={v1,…,vt−1}T = \{v_1, \dots, v_{t-1}\}T={v1,…,vt−1} is the set of new vertices. Reaching SSS again at www makes every new vertex reachable from SSS and able to reach SSS . Such an SSS exists to begin with: orient any cycle of GGG as a direct…
Who proved that a connected graph has a strong orientation iff it has no bridges, and where was it published?
Herbert E. Robbins, 1939, in the American Mathematical Monthly. Title: “A theorem on graphs, with an application to a problem of traffic control”, a year after his Harvard Ph.D. under Hassler Whitney. Robbins later co-wrote What Is Mathematics? with Richard Courant.
What is a round robin tournament, and how many rounds does one with 8 teams need?
Every team plays every other team exactly once. 8 teams: 7 rounds of 4 matches. With 7 teams, each round has 3 matches and one team gets a “bye”.
What is a tournament (as a digraph), and how does it model a round robin tournament?
An orientation of a complete graph: for every two distinct vertices u,vu, vu,v , exactly one of (u,v)(u, v)(u,v) and (v,u)(v, u)(v,u) is an arc. Vertices = teams; (u,v)(u, v)(u,v) is an arc if uuu defeats vvv (no ties). So od⁡v\operatorname{od} vodv is the number of matches vvv won.
When are two digraphs DDD and D′D'D′ isomorphic ( D≅D′D \cong D'D≅D′ )?
When there is a bijection ϕ:V(D)→V(D′)\phi : V(D) \to V(D')ϕ:V(D)→V(D′) with (u,v)∈E(D)(u, v) \in E(D)(u,v)∈E(D) if and only if (ϕ(u),ϕ(v))∈E(D′)(\phi(u), \phi(v)) \in E(D')(ϕ(u),ϕ(v))∈E(D′) . Such a ϕ\phiϕ is an isomorphism. Unlike for graphs, ϕ\phiϕ must preserve directions.
Up to isomorphism, how many tournaments are there of order 1, 2, 3, 4 and 5?
1, 1, 2, 4, 12. Growth is fast: there are over 154 billion tournaments of order 12.
When is a tournament transitive?
Whenever (u,v)(u, v)(u,v) and (v,w)(v, w)(v,w) are arcs, (u,w)(u, w)(u,w) is also an arc. A team that beats a team that beats www also beats www .
These are the two tournaments of order 3. Which one is transitive?
T4T_4T4 . T3T_3T3 is a directed triangle: each vertex beats one and loses to one, so transitivity would need the third arc reversed.
How many transitive tournaments of order nnn are there, and what are their outdegrees?
Exactly one (up to isomorphism), with outdegrees 0,1,…,n−10, 1, \dots, n - 10,1,…,n−1 (one vertex of each). It is a strict ranking: the vertex of outdegree iii beats exactly the iii vertices below it.
Theorem 7.6. Complete: a tournament TTT is transitive if and only if … ?
TTT has no cycles.
A tournament is transitive if and only if it has no cycles.Why does a transitive tournament contain no cycle (v1,v2,…,vk,v1)(v_1, v_2, \dots, v_k, v_1)(v1,v2,…,vk,v1) ?
v1v_1v1 is adjacent to v2v_2v2 and adjacent from vkv_kvk , so for some iii , (v1,vi)(v_1, v_i)(v1,vi) and (vi+1,v1)(v_{i+1}, v_1)(vi+1,v1) are arcs. But transitivity applied to (v1,vi)(v_1, v_i)(v1,vi) and (vi,vi+1)(v_i, v_{i+1})(vi,vi+1) gives (v1,vi+1)(v_1, v_{i+1})(v1,vi+1) . Both (v1,vi+1)(v_1, v_{i+1})(v1,vi+1) and (vi+1,v1)(v_{i+1}, v_1)(vi+1,v1) can't be arcs of a tournament.
A tournament is transitive if and only if it has no cycles.Why is a tournament without cycles transitive?
If (u,v)(u, v)(u,v) and (v,w)(v, w)(v,w) are arcs, then (w,u)(w, u)(w,u) is not an arc (it would close the cycle (u,v,w,u)(u, v, w, u)(u,v,w,u) ), so (u,w)(u, w)(u,w) is.
Theorem 7.7 If uuu is a vertex of maximum outdegree in a tournament TTT , then for every vertex vvv of TTT , d⃗(u,v)≤ ?\vec{d}(u, v) \le \; ?d(u,v)≤?
d⃗(u,v)≤2\boldsymbol{\vec{d}(u, v) \le 2}d(u,v)≤2 For teams: if AAA won the most matches and BBB is any other team, then AAA defeated BBB or AAA defeated a team that defeated BBB . ( d⃗\vec{d}d is the directed distance.)
If uuu has maximum outdegree kkk in a tournament, v1,…,vkv_1, \dots, v_kv1,…,vk are the vertices uuu is adjacent to, and www is adjacent to uuu , then d⃗(u,w)=2\vec{d}(u, w) = 2d(u,w)=2 .Why must some viv_ivi be adjacent to www ?
Otherwise www is adjacent to all of v1,…,vkv_1, \dots, v_kv1,…,vk and to uuu , so od⁡w≥k+1>od⁡u\operatorname{od} w \ge k + 1 > \operatorname{od} uodw≥k+1>odu , contradicting the maximality of od⁡u\operatorname{od} uodu .
In a digraph DDD , what are a Hamiltonian path, a Hamiltonian cycle and a Hamiltonian digraph?
A path containing every vertex of DDD ; a cycle containing every vertex of DDD ; a digraph that has a Hamiltonian cycle.
Rédei's theorem (Theorem 7.8). What does every tournament contain?
A Hamiltonian path. So the teams of a round robin tournament can always be ordered A1,A2,…,AnA_1, A_2, \dots, A_nA1,A2,…,An with each AiA_iAi having defeated Ai+1A_{i+1}Ai+1 .
Rédei: every tournament contains a Hamiltonian path. P=(v1,…,vk)P = (v_1, \dots, v_k)P=(v1,…,vk) is a longest path in a tournament and vvv is not on PPP . How does the proof get a contradiction?
(v1,v)(v_1, v)(v1,v) and (v,vk)(v, v_k)(v,vk) are arcs (else PPP extends), so for some iii , vi→v→vi+1v_i \to v \to v_{i+1}vi→v→vi+1 . Inserting vvv gives the longer path (v1,…,vi,v,vi+1,…,vk)(v_1, \dots, v_i, v, v_{i+1}, \dots, v_k)(v1,…,vi,v,vi+1,…,vk) .
Every tournament has a Hamiltonian path (A1,…,An)(A_1, \dots, A_n)(A1,…,An) , each team having beaten the next. Does such a path rank the teams from best to worst?
Not necessarily: a clear ordering exists only when the tournament is transitive. Here (A1,A2,A3)(A_1, A_2, A_3)(A1,A2,A3) , (A2,A3,A1)(A_2, A_3, A_1)(A2,A3,A1) and (A3,A1,A2)(A_3, A_1, A_2)(A3,A1,A2) are all Hamiltonian paths.
Theorem 7.9. Complete: every vertex in a nontrivial strong tournament … ?
Belongs to a triangle (a cycle of length 3).
Every vertex in a nontrivial strong tournament belongs to a triangle.Let UUU be the vertices vvv is adjacent to and WWW the vertices vvv is adjacent from. How does the proof find the triangle?
A vvv – www path ( w∈Ww \in Ww∈W ) starts in UUU and ends in WWW , so it uses an arc (u,w′)(u, w')(u,w′) with u∈Uu \in Uu∈U , w′∈Ww' \in Ww′∈W ; then (v,u,w′,v)(v, u, w', v)(v,u,w′,v) is a triangle. U,W≠∅U, W \ne \emptysetU,W=∅ since TTT is strong, and every vertex other than vvv is in UUU or WWW since TTT is a tournament.
Camion's theorem (Theorem 7.10). Complete: a nontrivial tournament TTT is Hamiltonian if and only if … ?
TTT is strong. One direction holds in every digraph: a Hamiltonian cycle is a closed spanning walk, so the digraph is strong.
C=(v1,…,vk,v1)C = (v_1, \dots, v_k, v_1)C=(v1,…,vk,v1) is a longest cycle in a tournament TTT , and vvv is a vertex not on CCC .Why can't vvv be adjacent to some vertex of CCC and adjacent from another?
Then some viv_ivi is adjacent to vvv with vi+1v_{i+1}vi+1 adjacent from vvv , and (v1,…,vi,v,vi+1,…,vk,v1)(v_1, \dots, v_i, v, v_{i+1}, \dots, v_k, v_1)(v1,…,vi,v,vi+1,…,vk,v1) is a longer cycle. So every vertex off CCC either beats all of CCC or loses to all of CCC . This is the first step in the proofs that strong tournaments are Hamiltonian.
Camion: a nontrivial tournament is Hamiltonian if and only if it is strong. TTT is strong and a longest cycle C=(v1,…,vk,v1)C = (v_1, \dots, v_k, v_1)C=(v1,…,vk,v1) misses some vertices. Every vertex off CCC is adjacent from all of CCC (set UUU ) or adjacent to all of CCC (set WWW ). How does the proof finish?
U,W≠∅U, W \ne \emptysetU,W=∅ since TTT is strong, and a path from CCC to WWW must use an arc (u,w)(u, w)(u,w) with u∈Uu \in Uu∈U , w∈Ww \in Ww∈W . Then (v1,…,vk,u,w,v1)(v_1, \dots, v_k, u, w, v_1)(v1,…,vk,u,w,v1) is a longer cycle.
Whose theorems are the fundamental theorems on traversability in tournaments, and what do they say?
Rédei: every tournament has a Hamiltonian path. Camion: a nontrivial tournament is Hamiltonian iff it is strong.
Theorem 7.11. If TTT is a strong tournament of order n≥4n \ge 4n≥4 , then there exists … ?
A vertex vvv such that T−vT - vT−v is a strong tournament. For n=4n = 4n=4 : there is only one strong tournament of order 4, and since every vertex lies on a triangle, deleting a vertex off one triangle leaves a strong tournament (that triangle).
If TTT is a strong tournament of order n≥4n \ge 4n≥4 , some vertex vvv has T−vT - vT−v strong.Assume n≥5n \ge 5n≥5 and no such vvv , so TTT has no cycle of length n−1n - 1n−1 (a strong tournament is Hamiltonian). What contradiction does the proof reach?
For a longest non-Hamiltonian cycle C=(v1,…,vk,v1)C = (v_1, \dots, v_k, v_1)C=(v1,…,vk,v1) , k≤n−2k \le n - 2k≤n−2 , the off-cycle vertices split into UUU (adjacent from all of CCC ) and WWW (adjacent to all of CCC ), and an arc (u,w)(u, w)(u,w) from UUU to WWW gives the cycle (v1,…,vk−1,u,w,v1)(v_1, \dots, v_{k-1}, u, w, v_1)(v1,…,vk−1,u,w,v1) of length k+1≤n−1k + 1 \le n - 1k+1≤n−1 . vkv_kvk is replaced by u,wu, wu,w , so the new cycle is still not Hamiltonian, contradicting the choice…
A strong tournament has order n≥3n \ge 3n≥3 . For which kkk does it contain an induced strong tournament of order kkk ?
For every kkk with 3≤k≤n3 \le k \le n3≤k≤n . Repeatedly delete a vertex whose removal leaves a strong tournament (always possible from order 4 upward).
What is the tournament of paired comparisons for a person's preferences among some choices?
Vertices = the choices; an arc (X,Y)(X, Y)(X,Y) whenever the person prefers XXX to YYY . Al prefers GM, H, C, T, F in this order: a transitive tournament.
Five family members each rank five cars, so each has a transitive tournament of paired comparisons. The family tournament has an arc (X,Y)(X, Y)(X,Y) when a majority prefers XXX to YYY . Must the family tournament be transitive?
No. In the book's example it is not transitive, so it is unclear which car to buy. (All three children prefer F over GM, both parents GM over F, so the arc is (F,GM)(F, GM)(F,GM) .)
1500 students rank candidates A, B, C (first, second, third choice): 100: A, B, C · 500: A, C, B · 75: B, A, C · 425: B, C, A · 50: C, A, B · 350: C, B, A. Who wins by first choices only, who wins a runoff between the top two, and who wins by paired comparisons?
First choices: A. Runoff: B. Paired comparisons: C. First choices: A 600, B 500, C 400. Runoff A vs B: B wins 850 to 650. C beats A 825 to 675 and B 900 to 600. So by the two most common methods, the winner is not the preferred candidate; A even loses to both others head to head.
A puzzle moves through states by single steps. When is it modeled by a digraph rather than a graph?
When some step from state A to state B can't be undone by a single step from B to A. Vertices = states, arc (A,B)(A, B)(A,B) if one step leads from A to B. If every step is reversible, a graph suffices.
In wine bottle problems, a pouring empties wine from bottle X into bottle Y until Y is full or X is empty.
The bottles have no markings, so these are the only measurable moves.
Bottles A, B, C hold 1, 3 and 4 liters; C is full, A and B are empty. What is the fewest number of pourings to get 2 liters in C and 2 liters in B?
3. Pour C into B, B into A, A into C: states (a,b)=(0,0)→(0,3)→(1,2)→(0,2)(a, b) = (0, 0) \to (0, 3) \to (1, 2) \to (0, 2)(a,b)=(0,0)→(0,3)→(1,2)→(0,2) , with a,ba, ba,b the liters in A and B.Two pourings can't do it: in the digraph of states, the directed distance from (0,0)(0, 0)(0,0) to (0,2)(0, 2)(0,2) is 3.
Bottles A, B, C hold 1, 3 and 4 liters, starting with C full. How is the shortest sequence of pourings found with a digraph?
Vertices = states (a,b)(a, b)(a,b) , with aaa , bbb the liters in A and B; an arc for each single pouring. The answer is the directed distance from (0,0)(0, 0)(0,0) to (0,2)(0, 2)(0,2) . c=4−a−bc = 4 - a - bc=4−a−b , so (a,b)(a, b)(a,b) determines the state: 8 vertices, a∈{0,1}a \in \{0, 1\}a∈{0,1} , b∈{0,1,2,3}b \in \{0, 1, 2, 3\}b∈{0,1,2,3} . An arc from (0,1)(0, 1)(0,1) to (0,0)(0, 0)(0,0) but not back: B's 1 liter can be poured into C, but exactly 1 liter can't be poured from a full C into…