Discrete Mathematics: Elementary and Beyond

8.4 How to Store Trees 151 0 521 63 7 4 FIGURE 8.5. A tree reconstructed from its Pr ̈ufer code How does the first row start? Re ...

152 8. Trees Indeed, when this entry (say, thek-th entry in the first row) was recorded, the nodes before it in the first row we ...

8.5 The Number of Unlabeled Trees 153 8.5 The Number of Unlabeled Trees The number of unlabeled trees onnnodes, usually denoted ...

154 8. Trees FIGURE 8.6. Walking around a tree. Every unlabeled tree is uniquely determined by its planar code. Let us illuminat ...

8.5 The Number of Unlabeled Trees 155 as 1’s). Still, the planar code is quite an efficient way of encoding unlabeled trees: It ...

156 8. Trees 8.5.10IfCis a cycle, andeis an edge connecting two nonadjacent nodes ofC, then we calleachordofC. Prove that if eve ...

9 Finding the Optimum 9.1 Finding the Best Tree A country withntowns wants to construct a new telephone network to connect all t ...

158 9. Finding the Optimum We dispute the claim that this is easy. The number of trees to consider is enormous: We know by Cayle ...

9.1 Finding the Best Tree 159 (This problem is one of the most famous tasks in mathematical optimiza- tion: it is called theTrav ...

160 9. Finding the Optimum 11 6 4 10 9 8 (^75) 3 2 (^1) e f FIGURE 9.2. The greedy tree is optimal fwas ruled out because it wou ...

9.2 The Traveling Salesman Problem 161 9.2 The Traveling Salesman Problem............... Let us return to the question of findin ...

162 9. Finding the Optimum be anywhere nearly as simple, elegant and efficient as the “optimistic” algorithm discussed in the pr ...

9.2 The Traveling Salesman Problem 163 FIGURE 9.3. The cheapest tree connecting 15 given towns, the walk around it, and the tour ...

164 9. Finding the Optimum 9.2.5In a real-life government, optimists and pessimists win in unpredictable order. This means that ...

10 Matchings in Graphs 10.1 A Dancing Problem At the prom, 300 students took part. They did not all know each other; in fact, ev ...

166 10. Matchings in Graphs FIGURE 10.1. A bipartite graph with a perfect matching. To be precise, let’s give the definitions of ...

10.2 Another matching problem 167 A B C D F E 1 6 (^45) 3 2 A, B,...areas of tribes 1, 2,... areas of tortoises border between t ...

168 10. Matchings in Graphs species, just in case the tortoises want to pick totems too). Drawing the tribe-nodes on the left an ...

10.3 The Main Theorem 169 at leastknodes on the right connected to at least one of them. We’ll see in the next section that this ...

170 10. Matchings in Graphs k n-k FIGURE 10.4. The good graph is also good from right to left. Now our plan is to partition our ...