9.11. Summary of Relational Properties 345
Problems for Section 9.1
Exam Problems
Problem 9.1.
The proof of the Handshaking Lemma 9.1.2 invoked the “obvious” fact that in any
finite digraph, the sum of the in-degrees of the vertices equals the number of arrows
in the graph. That is,
Claim.For any finite digraph,G,
X
v 2 V.G/indeg.v/Djgraph.G/j; (9.10)But this Claim might not be obvious to everyone. So prove it by induction on the
number,jgraph.G/j, of arrows.
Problems for Section 9.4
Practice Problems
Problem 9.2.
Let
AWWDf1;2;3g
BWWDf4;5;6g
RWWDf.1;4/;.1;5/;.2;5/;.3;6/g
SWWDf.4;5/;.4;6/;.5;4/g:Note thatRis a relation fromAtoBandSis a relation fromBtoB.
List the pairs in each of the relations below.
(a)SıR.
(b)SıS.(c)S ^1 ıR.Problem 9.3.
Lemma 9.2.5 states that dist.u;v/dist.u;x/Cdist.x;v/. It also states that
equality holds iffxis on a shortest path fromutov.