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

234 DIRECTED GRAPHS [CHAP. 9

Fig. 9-38

9.43. (i)A=[ 0 , 0 , 0 , 0 , 0 ; 0 , 0 , 0 , 1 , 0 ; 1 , 1 , 0 , 1 , 0 ;

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

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

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

(ii)A=[ 0 , 0 , 0 , 0 , 0 , 1 ; 1 , 0 , 1 , 0 , 0 , 1 ; 0 , 0 , 0 , 0 , 1 , 0 ;

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

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

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

9.44. (i)W =[ 7 , 5 , 0 , 0 ; 0 , 0 , 0 , 2 ; 0 , 3 , 0 , 0 ; 4 , 0 , 1 , 0 ];

Q=[AA,AB,ABCD,ABD;BDA,BDCB,BDC,BD;

CBDA,CB,CBDC,CBD;DA,DCB,DC,DCBD],

whereA, B, C, Dare the vertices.

(ii)W=[ 0 , 0 , 1 , 0 , 5 ; 0 , 0 , 0 , 1 , 0 ; 0 , 0 , 0 , 4 , 3 ;

2 , 0 , 0 , 0 , 0 ; 0 , 2 , 0 , 4 , 0 ];

Q=[ACDA,ACEB,AC,ACD,ACE;BDA,BDACEB,

BDAC,BD,BDACE;CDA,CEB,CDAC,CD,CE;

DA,DACEB,DAC,DACD,DACEB;EDA,EB,

EDAC,ED,EDACE]whereA, B, C, D, Eare the

vertices.

9.45. (a) STACK:B,LBEB,ELCLEB,FECL,DFCL,CL,

JC,KJ,
; Vertex:B,LB,EL,FE,DF,CL,JC,KJ

(b) STACK:E,FE,DF,
; Vertex:E,FE,DF

(c) STACK: K, LKCK, ELCL,CK, CL, DFCL,

CLJC, 
; Vertex:K,LK,EL,FE,DF,CL,JC

9.46. QUEUE:K,LKCK,JCECDCLK,JCECDC,JCEC,

FE; Vertex:K,CK,LK,DC,EC,JC,FE; Minimal

Path:FE←EC←CK←orK→CK→EC→FE.