Advanced High-School Mathematics

SECTION 2.2 Elementary Graph Theory 111 would ideally choose a route that would allow him to avoid walking the same street twice ...

112 CHAPTER 2 Discrete Mathematics Definition. The degreeof a vertexv in a graph is the number of edges on this vertex. A loop o ...

SECTION 2.2 Elementary Graph Theory 113 Theorem. (Euler’s Degree Theorem)The sum of the degrees of the vertices equals twice the ...

114 CHAPTER 2 Discrete Mathematics Exercises Sketch a graph whose adjacency matrix is A =         0 1 2 1 0 1 1 ...

SECTION 2.2 Elementary Graph Theory 115 Model this problem with a suitable graph and give a reason for your answer. Consider th ...

116 CHAPTER 2 Discrete Mathematics We consider the following family of simple graphsOn, n= 1, 2 ,..., defined as follows. Vert ...

SECTION 2.2 Elementary Graph Theory 117 Does the graph to the right have an Eulerian circuit? If so, find it. 2.2.2 Hamiltonia ...

118 CHAPTER 2 Discrete Mathematics Of more significance than just finding a Hamiltonian cycle in a simple graph is that of findi ...

SECTION 2.2 Elementary Graph Theory 119 cycles. In order to find the Hamiltonian cycle of minimal weight, we shall resort to the ...

120 CHAPTER 2 Discrete Mathematics often abbreviated TSP—and is one of fundamental importance in Man- agement Science. It is als ...

SECTION 2.2 Elementary Graph Theory 121 TSP: The nearest-neighbor algorithm As indicated above, the brute-force method will alwa ...

122 CHAPTER 2 Discrete Mathematics A B C D E A * 20 23 19 17 B * 20 25 18 C * 24 19 D * 23 E * Use the Nearest-Neighbor algo- ri ...

SECTION 2.2 Elementary Graph Theory 123 As with the Nearest-Neighbor algorithm, we do not select any edges which would premature ...

124 CHAPTER 2 Discrete Mathematics 2.2.3 Networks and spanning trees In this subsection we consider a problem similar to TSP but ...

SECTION 2.2 Elementary Graph Theory 125 spanning treeof the graph.^33 The second says that we are looking for aminimal-weight sp ...

126 CHAPTER 2 Discrete Mathematics be a path fromv tov′, where each {vi− 1 ,vi} is an edge inG. Assume thatv′is adjacent to anot ...

SECTION 2.2 Elementary Graph Theory 127 Example 1, continued. We shall return to the above exam- ple only long enough to indicat ...

128 CHAPTER 2 Discrete Mathematics Kruskal’s algorithm Kruskal’s algorithm is the same in spirit as the Cheapest-Link algorithm ...

SECTION 2.2 Elementary Graph Theory 129 Exercises Find a minimal spanning tree for the graph on the right. The table to the rig ...

130 CHAPTER 2 Discrete Mathematics tained a lower bound for the total weight of a minimal-weight Hamiltonian cycle. (b) (Upper b ...