Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)
CHAP. 8] GRAPH THEORY 185 Fig. 8-49 8.19. Prove Theorem 8.11: The following are equivalent for a graphG: (i)Gis 2-colorable. (ii ...
186 GRAPH THEORY [CHAP. 8 a cycleCwhich encloses eitherv 2 orv 4. Consider now the subgraphKgenerated by the vertices paintedc 3 ...
CHAP. 8] GRAPH THEORY 187 8.24. Draw the graphGcorresponding to each adjacency matrix: (a) A= ⎡ ⎢ ⎢⎢ ⎢ ⎣ 01010 10011 00011 11101 ...
188 GRAPH THEORY [CHAP. 8 (b) Here adj(D)=[ 5 (A), 1 (B), 8 (E)]. Specifically, PTR[ 4 (D)]=7 and ADJ[ 7 ]= 5 (A)tells us that a ...
CHAP. 8] GRAPH THEORY 189 Fig. 8-56 (b) During the DFS algorithm, the first vertexNin STACK is processed and the neighbors ofN(w ...
190 GRAPH THEORY [CHAP. 8 (b) The adjacency structure ofGappears in Problem 8.30. The following shows the sequence of waiting li ...
CHAP. 8] GRAPH THEORY 191 SupplementaryProblems GRAPH TERMINOLOGY 8.34. Consider the graphGin Fig. 8-58. Find: (a) degree of eac ...
192 GRAPH THEORY [CHAP. 8 Fig. 8-59 SPECIAL GRAPHS 8.48. Draw two 3-regular graphs with: (a) eight vertices; (b) nine vertices. ...
CHAP. 8] GRAPH THEORY 193 8.52. Then-cycle, denoted byCn, is the graph which consists of only a single cycle of lengthn. Figure ...
194 GRAPH THEORY [CHAP. 8 Fig. 8-63 Fig. 8-64 8.64. Find the minimum number of colors needed to paint the regions of each map in ...
CHAP. 8] GRAPH THEORY 195 8.68. Draw the multigraphGcorresponding to each of the following adjacency matrices: (a)A= ⎡ ⎢ ⎢ ⎣ 020 ...
196 GRAPH THEORY [CHAP. 8 TRAVELING–SALESMAN PROBLEM 8.73.Apply the nearest-neighbor algorithm to the complete weighted graphGin ...
CHAP. 8] GRAPH THEORY 197 8.45. (a)ABCDEA; (b)ABCDEF A; (c) none, sinceBorDmust be visited twice in any closed path including al ...
198 GRAPH THEORY [CHAP. 8 8.55. 10 8.56. 15 8.57. 1 + 1 + 1 + 1 + 1 + 2 + 2 + 3 =12. 8.59. m=1. 8.60. Only (a) is nonplanar, and ...
CHAP. 8] GRAPH THEORY 199 Fig. 8-73 8.71. (a) Each vertex is adjacent to the other four vertices. (b) G=[A:B, D, F;B:A, C, E;C:B ...
200 GRAPH THEORY [CHAP. 8 8.78. (a) [QUEUE:C,JB,LDAJ,MLDA,KMLD,KML,KM,K], CBJ ADLMK (b) [QUEUE:K,LDA,JMBLD,JMBL,CJMB,CJM,CJ,C], ...
CHAPTER 9 Directed Graphs 9.1Introduction Directed graphsare graphs in which the edges are one-way. Such graphs are frequently m ...
202 DIRECTED GRAPHS [CHAP. 9 Apictureof a directed graphGis a representation ofGin the plane. That is, each vertexuofGis represe ...
CHAP. 9] DIRECTED GRAPHS 203 Degrees SupposeGis a directed graph. Theoutdegreeof a vertexvofG, written outdeg(v), is the number ...
204 DIRECTED GRAPHS [CHAP. 9 Connectivity There are three types of connectivity in a directed graphG: (i) Gisstrongly connectedo ...
«
6
7
8
9
10
11
12
13
14
15
»
Free download pdf