868 CHAPTER 13 Graph Theory A question that naturally arises from Example 2 is, “How many different Hamilton circuits are there in a complete graph?” Before we can give a formula that answers this question, we need to discuss factorials, which were presented in Section 11.7. We will review that material here. The symbol 5! is read “five factorial” and means to multiply 5 by each natural number less than 5. So = ⋅ ⋅ ⋅ ⋅ = 5! 5 4 3 2 1 120. Also = ⋅ ⋅ = 3! 3 2 1 6 and = ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ = 7! 7 6 5 4 3 2 1 5040. Note that 0! is defined to be 1. Example 2 Determining Hamilton Circuits Determine a Hamilton circuit for the complete graph shown in Fig. 13.39. A B C D E Figure 13.39 Solution We can determine many Hamilton circuits in this complete graph. For example, one is A B C D E A , , , , , . Another is B A D C E B , , , , , . Another is E B C , , , D A E , , . To build a Hamilton circuit from this complete graph, we can list all five vertices in any order and then return to the first vertex. 7 Now try Exercise 15 Number of Unique Hamilton Circuits in a Complete Graph The number of unique Hamilton circuits in a complete graph with n vertices is − n( 1)!, where n n n n ( 1)! ( 1)( 2)( 3) (3)(2)(1) − = − − − Example 3 Number of Hamilton Circuits How many unique Hamilton circuits are in a complete graph with the following number of vertices? a) Four b) Eight c) Ten d) Eleven Solution a) Using the formula, for the number of unique Hamilton circuits, a complete graph with four vertices has − = = ⋅ ⋅ = (4 1)! 3! 3 2 1 6 unique Hamilton circuits. b) A complete graph with eight vertices has − = = ⋅⋅⋅⋅⋅⋅= (8 1)! 7! 7 6 5 4 3 2 1 5040 unique Hamilton circuits. c) A complete graph with ten vertices has − = = ⋅⋅⋅⋅⋅⋅⋅⋅= (10 1)! 9! 987654321 362,880 unique Hamilton circuits. d) A complete graph with eleven vertices has − = = ⋅⋅⋅⋅⋅⋅⋅⋅⋅= (11 1)! 10! 10 9 8 7 6 5 4 3 2 1 3,628.800 unique Hamilton circuits. 7 Now try Exercise 21
RkJQdWJsaXNoZXIy NjM5ODQ=