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

CHAP. 8] GRAPH THEORY 165 Fig. 8-18 Minimum Spanning Trees SupposeGis a connected weighted graph. That is, each edge ofGis assig ...

166 GRAPH THEORY [CHAP. 8 Thus the minimal spanning tree ofQwhich is obtained contains the edges BE,CE,AE,DF,BD The spanning tre ...

CHAP. 8] GRAPH THEORY 167 Maps, Regions A particular planar representation of a finite planar multigraph is called amap. We say ...

168 GRAPH THEORY [CHAP. 8 Theorem 8.9: LetGbe a connected planar graph withpvertices andqedges, wherep≥3. Thenq≥ 3 p−6. Note tha ...

CHAP. 8] GRAPH THEORY 169 for example, “paint”Grather than “color”Gwhen we are assigning colors to the vertices ofG.) The minimu ...

170 GRAPH THEORY [CHAP. 8 Theorem 8.11: The following are equivalent for a graphG: (i) Gis 2-colorable. (ii) Gis bipartite. (iii ...

CHAP. 8] GRAPH THEORY 171 Observe that any coloring of the regions of a mapMwill correspond to a coloring of the vertices of the ...

172 GRAPH THEORY [CHAP. 8 Linked Representation of a GraphG LetGbe a graph withmvertices. The representation ofGin memory by its ...

CHAP. 8] GRAPH THEORY 173 Here: (1) EDGE will be the name of the edge (if it has one). (2) ADJ points to the location of the ver ...

174 GRAPH THEORY [CHAP. 8 During the execution of our algorithms, each vertex (node)NofGwill be in one of three states, called t ...

CHAP. 8] GRAPH THEORY 175 EXAMPLE 8.4 Suppose the DFS Algorithm 8.5 in Fig. 8-31 is applied to the graph in Fig. 8-30. The verti ...

176 GRAPH THEORY [CHAP. 8 Fig. 8-33 Fig. 8-34 8.13Traveling-Salesman Problem LetGbe a complete weighted graph. (We view the vert ...

CHAP. 8] GRAPH THEORY 177 Fig. 8-35 ThusACDBAwith weight 20 is the Hamiltonian circuit of minimum weight. We solved the “traveli ...

178 GRAPH THEORY [CHAP. 8 SolvedProblems GRAPH TERMINOLOGY 8.1. Consider the graphGin Fig. 8-36(a). (a) DescribeGformally, that ...

CHAP. 8] GRAPH THEORY 179 8.3. Consider the multigraphs in Fig. 8-37. (a) Which of them are connected? If a graph is not connect ...

180 GRAPH THEORY [CHAP. 8 8.5. Consider the graphGin Fig. 8-36(b). Find the subgraphs obtained when each vertex is deleted. Does ...

CHAP. 8] GRAPH THEORY 181 8.8. Which of the graphs in Fig. 8-40 have a Hamiltonian circuit? If not, why not? Graphs(a)and(c)have ...

182 GRAPH THEORY [CHAP. 8 Fig. 8-43 except that two of the ways lead to disconnected graphs. Hence the above eight spanning tree ...

CHAP. 8] GRAPH THEORY 183 (iv) implies(i) Since adding any edgee={x, y}toGproduces a cycle, the verticesxandymust already be con ...

184 GRAPH THEORY [CHAP. 8 (a) Redrawing the positions ofBandE, we get a planar representation of the graph as in Fig. 8-47(a). ( ...