Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 9] DIRECTED GRAPHS 233

Fig. 9-35

9.29. (a)A=[ 0 , 0 , 1 , 0 , 0 ; 1 , 0 , 0 , 0 , 0 ; 0 , 1 , 0 , 0 , 0 ;

1 , 0 , 0 , 0 , 1 ; 1 , 0 , 1 , 1 , 0 ];

P=[ 1 , 1 , 1 , 0 , 0 ; 1 , 1 , 1 , 0 , 0 ; 1 , 1 , 1 , 0 , 0 ;

1 , 1 , 1 , 1 , 1 ; 1 , 1 , 1 , 1 , 1 ; 1 , 1 , 1 , 1 , 1 ]

(b)(X,Z,Y,X);(S, T, S) (c) Unilaterally.

9.30. (a)A=[ 0 , 7 , 0 , 0 ; 3 , 0 , 2 , 0 ; 0 , 0 , 0 , 5 ; 6 , 1 , 4 , 0 ]

(b)Q=[XYX,XY,XYS,XYST;YX,YSTY,YS,YST;

STYX,STY,STYS,ST;TX,TY,TYS,TYST]

9.31. (a)C, F, D, B, E, A; (b)[A:C, E;B:D;

C:D,E, A;D:A, F;E:
;F:B, E]; (c)

See Fig. 9-35(b).

9.32. (a) 5, 6; (b) source:A; (c) See Fig. 9-36(a); none.

9.33. (a) 5, 1; (b) none; (c) See Fig. 9-36(b); (d) all three.

9.34. (a) 7, 11; (b) source:A; sinks:C,D; (c) See

Fig. 9-36(c); (d) only weakly.

Fig. 9-36

9.35. See Fig. 9-37.

Fig. 9-37

9.36. (a) No; (b) yes; (c) no; (d) no.

9.37. (a)AWP; (b)PA; (c) none; (d)WPC.

9.38. (s,4,1,2,1,2,1,2,t)

9.39. Hint:First draw the graph. (a)ASYCZBXTD; (b) none,

the graph is not cycle-free, e.g.,YBAXSYis a cycle; (c)

BTYXACSDZ.

9.40. See Fig. 9-38(a).

9.41. (a) See Fig. 9-38(b). (b) Only weakly connected.

9.42. Hint:Suppose (α=v 1 ,...,vm) is a longest path inG

and does not include vertexu.If(u 1 v 1 ) is an arc, then

β=(u, α)extendsα. Hence (v 1 ,u) is an arc. If (u, v 2 )

is also an arc, thenβ=(v 1 ,u,v 2 ,...,vm)extendsα;

hence (v 2 ,u) is an arc. Similarly(v 3 ,u),..., (vm,u)

are arcs. Henceβ=(α, u)extendsα.This contradicts

the maximality ofα.