{"id":8452,"date":"2023-09-29T15:01:30","date_gmt":"2023-09-29T15:01:30","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&p=8452"},"modified":"2024-10-18T20:58:13","modified_gmt":"2024-10-18T20:58:13","slug":"graph-theory-get-stronger","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/graph-theory-get-stronger\/","title":{"raw":"Graph Theory: Get Stronger","rendered":"Graph Theory: Get Stronger"},"content":{"raw":"

Graph Basics<\/h2>\r\n

For the following exercises, use the given figure below (Figure 1).<\/p>\r\n\r\n[caption id=\"attachment_13196\" align=\"alignnone\" width=\"1792\"]\"Five Figure 1[\/caption]\r\n\r\n

    \r\n\t
  1. Determine the number of vertices in Graph\u00a0S<\/i>.<\/li>\r\n\t
  2. Identify the graph with the fewest edges.<\/li>\r\n\t
  3. Name the vertices in Graph\u00a0U<\/i>.<\/li>\r\n\t
  4. Identify any pairs of vertices in Graph\u00a0S<\/i>\u00a0that are not adjacent.<\/li>\r\n\t
  5. Which graphs only has vertices of degree 2?<\/li>\r\n\t
  6. Identify the graph in which the sum of the degrees of the vertices is 16.<\/li>\r\n<\/ol>\r\n

    Graph Structures<\/h2>\r\n

    For the following exercises, use the given figure below (Figure 2).<\/p>\r\n\r\n[caption id=\"attachment_13197\" align=\"alignnone\" width=\"1694\"]\"Four Figure 2[\/caption]\r\n\r\n

      \r\n\t
    1. Explain why Graph\u00a0B<\/i>\u00a0is not a subgraph of Graph\u00a0C<\/i>.<\/li>\r\n\t
    2. How many edges are in a complete graph with 12 vertices?<\/li>\r\n<\/ol>\r\n

      Navigating Graphs<\/h2>\r\n

      For the following exercises, use Graph\u00a0A<\/i> in the given figure below (Figure 3). Consider each sequence of vertices. Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.<\/p>\r\n\r\n[caption id=\"attachment_13198\" align=\"aligncenter\" width=\"741\"]\"Two Figure 3[\/caption]\r\n\r\n

        \r\n\t
      1. e<\/i>\u00a0\u2192\u00a0d<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192\u00a0e<\/i>\u00a0\u2192\u00a0f<\/i><\/li>\r\n\t
      2. e<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192\u00a0d<\/i>\u00a0\u2192\u00a0e<\/i>\u00a0\u2192\u00a0f<\/i>\u00a0\u2192\u00a0c<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192\u00a0d<\/i><\/li>\r\n\t
      3. e<\/i>\u00a0\u2192\u00a0f<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192\u00a0d<\/i><\/li>\r\n<\/ol>\r\n

        For the following exercises, use Graph\u00a0K <\/i>(Figure 3) . Identify each sequence of vertices as a closed walk, circuit (closed trail), and\/or directed cycle (closed path). Indicate all that apply.<\/p>\r\n

          \r\n\t
        1. n<\/i>\u00a0\u2192\u00a0o<\/i>\u00a0\u2192\u00a0q<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0p<\/i>\u00a0\u2192\u00a0m<\/i>\u00a0\u2192\u00a0n<\/i><\/li>\r\n\t
        2. m<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0o<\/i>\u00a0\u2192\u00a0q<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0p<\/i>\u00a0\u2192\u00a0o<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0m<\/i><\/li>\r\n\t
        3. p<\/i>\u00a0\u2192\u00a0o<\/i>\u00a0\u2192\u00a0q<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0m<\/i>\u00a0\u2192\u00a0p<\/i><\/li>\r\n<\/ol>\r\n

          Euler Circuits<\/h2>\r\n

          For the following exercises, use the graphs and multigraphs shown below (Figure 4). Identify any graphs and\/or multigraphs with the given characteristics. If there are none, state so.<\/p>\r\n\r\n[caption id=\"attachment_13199\" align=\"alignnone\" width=\"1800\"]\"Five Figure 4[\/caption]\r\n\r\n

            \r\n\t
          1. connected<\/li>\r\n\t
          2. disconnected<\/li>\r\n\t
          3. Eulerian<\/li>\r\n<\/ol>\r\n

            Euler Trails<\/h2>\r\n

            For the following exercises, use the graphs and multigraphs in Figure 4.<\/p>\r\n

              \r\n\t
            1. Determine whether the sequence of edges represents an Euler circuit in Multigraph 15: K<\/i>\u00a0\u2192\u00a0L<\/i>\u00a0\u2192\u00a0N<\/i>\u00a0\u2192\u00a0M<\/i>\u00a0\u2192\u00a0O<\/i>\u00a0\u2192\u00a0S<\/i>\u00a0\u2192\u00a0T<\/i>\u00a0\u2192\u00a0Q<\/i>\u00a0\u2192\u00a0U<\/i>\u00a0\u2192\u00a0P<\/i>\u00a0\u2192\u00a0R<\/i><\/li>\r\n\t
            2. Find an Euler circuit beginning and ending at vertex g<\/i>\u00a0in Graph 12 if one exists. Otherwise, explain how you know such an Euler circuit does not exist.<\/li>\r\n\t
            3. Give an example of a pair of edges that could be duplicated to eulerize Multigraph 14.<\/li>\r\n<\/ol>\r\n

              For the following exercises, use the graphs and multigraphs in Figure 4. Identify any graphs and\/or multigraphs with the given characteristics. If there are none, state so.<\/p>\r\n

                \r\n\t
              1. Exactly two vertices of odd degree<\/li>\r\n\t
              2. Has an Euler trail<\/li>\r\n<\/ol>\r\n

                Hamilton Circuits<\/h2>\r\n

                For the following exercises, refer to the graph in the given in figure 5.<\/p>\r\n\r\n[caption id=\"attachment_13200\" align=\"aligncenter\" width=\"328\"]\"A Figure 5[\/caption]\r\n\r\n

                  \r\n\t
                1. A student has been asked to use Fleury\u2019s algorithm to construct an Euler trail in the given graph. The student decides to begin the trail at vertex\u00a0d<\/i>. Is this a good choice, why or why not?<\/li>\r\n\t
                2. A student who is using Fleury\u2019s algorithm to construct an Euler trail has decided to begin with\u00a0f<\/i>\u00a0\u2192\u00a0d<\/i>\u00a0\u2192\u00a0a<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192 \u2026. If the student is off to a good start, help the student by completing the Euler trail. If the student has made an error, explain the error.<\/li>\r\n\t
                3. Use Fleury\u2019s algorithm to construct an Euler trail for the given graph beginning at the vertex of your choice.<\/li>\r\n<\/ol>\r\n

                  For the following exercises, use the graphs from figures 6 and 7 to determine whether the sequence of vertices in the given graph is a Hamilton cycle, an Euler circuit, both, or neither.<\/p>\r\n\r\n[caption id=\"attachment_13201\" align=\"aligncenter\" width=\"741\"]\"Two Figure 6[\/caption] [caption id=\"attachment_13202\" align=\"aligncenter\" width=\"340\"]\"Graph Figure 7[\/caption]\r\n\r\n

                    \r\n\t
                  1. Graph F. a \u2192 b \u2192 e \u2192 c \u2192 b \u2192 d \u2192 c \u2192 a<\/em><\/li>\r\n\t
                  2. Graph K. m \u2192 n \u2192 q \u2192 o \u2192 p \u2192 m<\/em><\/li>\r\n\t
                  3. Graph A. b \u2192 d \u2192 e \u2192 f \u2192 c \u2192 b \u2192 e<\/em><\/li>\r\n<\/ol>\r\n

                    For the following exercises, evaluate the factorial expression for the given value of [latex]n[\/latex].<\/p>\r\n

                      \r\n\t
                    1. [latex](n\u22121)!,n=12[\/latex]<\/li>\r\n\t
                    2. [latex](n\u22121)!,n=14[\/latex]<\/li>\r\n\t
                    3. Calculate the number of distinct Hamilton cycles in a complete graph with [latex]13[\/latex] vertices.<\/li>\r\n<\/ol>\r\n

                      For the following exercises, use figure 8 to find the weight of each Hamilton cycle.<\/p>\r\n\r\n[caption id=\"attachment_13203\" align=\"aligncenter\" width=\"406\"]\"Graph Figure 8[\/caption]\r\n\r\n

                        \r\n\t
                      1. q<\/i>\u00a0\u2192\u00a0t<\/i>\u00a0\u2192\u00a0w<\/i>\u00a0\u2192\u00a0x<\/i>\u00a0\u2192\u00a0u<\/i>\u00a0\u2192\u00a0y<\/i>\u00a0\u2192\u00a0v<\/i>\u00a0\u2192\u00a0s<\/i>\u00a0\u2192\u00a0r<\/i>\u00a0\u2192\u00a0q<\/i><\/li>\r\n\t
                      2. w<\/i>\u00a0\u2192\u00a0x<\/i>\u00a0\u2192\u00a0y<\/i>\u00a0\u2192\u00a0u<\/i>\u00a0\u2192\u00a0v<\/i>\u00a0\u2192\u00a0s<\/i>\u00a0\u2192\u00a0r<\/i>\u00a0\u2192\u00a0q<\/i>\u00a0\u2192\u00a0t<\/i>\u00a0\u2192\u00a0w<\/i><\/li>\r\n<\/ol>\r\n

                        Hamilton Paths<\/h2>\r\n

                        For the following exercises, use figure 9 to determine whether the sequence of vertices in the given graph is a Hamilton path, an Euler trail, both, or neither.<\/p>\r\n\r\n[caption id=\"attachment_13198\" align=\"aligncenter\" width=\"741\"]\"Two Figure 9[\/caption]\r\n\r\n

                          \r\n\t
                        1. Graph A. e \u2192 b \u2192 c \u2192 f \u2192 e \u2192 b \u2192 e<\/em><\/li>\r\n\t
                        2. Graph A. b \u2192 c \u2192 f \u2192 e \u2192 d \u2192 b \u2192 e<\/em><\/li>\r\n\t
                        3. Graph K. n \u2192 q \u2192 o \u2192 p \u2192 m<\/em><\/li>\r\n\t
                        4. Graph K. o \u2192 q \u2192 m \u2192 n \u2192 p<\/em><\/li>\r\n<\/ol>\r\n

                          Traveling Sales Person Problem<\/h2>\r\n

                          For the following exercises, determine whether the algorithm described is a greedy algorithm or a brute force algorithm.<\/p>\r\n

                            \r\n\t
                          1. A lumber distributor is loading pallets onto trucks with the intention of using the fewest trucks possible to send a shipment. The distributor loads the pallets with the greatest length that will fit on the truck first and continues loading until no more pallets will fit. Then the next truck is loaded using the same approach.<\/li>\r\n\t
                          2. A traveler wants to visit five cities by airplane. The traveler lists all the possible orders in which the cities can be visited then calculates the best airfare for each itinerary and selects the least expensive option.<\/li>\r\n<\/ol>\r\n

                            For the following exercises, list all the distinct Hamilton cycles beginning at the given vertex in the given graph (figure 10). Indicate which pairs of Hamilton cycles are reverses of each other.<\/p>\r\n\r\n[caption id=\"attachment_13204\" align=\"aligncenter\" width=\"1219\"]\"Two Figure 10[\/caption]\r\n\r\n

                              \r\n\t
                            1. Graph 17, vertex\u00a0a<\/i><\/li>\r\n\t
                            2. Graph 18, vertex\u00a0m<\/i><\/li>\r\n<\/ol>\r\n

                              For the following exercises, find a Hamilton cycle of least weight for the given graph in Figure 10, beginning at the given vertex, and using the brute force method. What is the weight of the cycle?<\/p>\r\n

                                \r\n\t
                              1. Graph 18; vertex\u00a0m<\/i><\/li>\r\n\t
                              2. Graph 17; vertex\u00a0a<\/i><\/li>\r\n<\/ol>\r\n

                                Spanning Trees<\/h2>\r\n

                                For the following exercises, draw a graph with the given characteristics.<\/p>\r\n

                                  \r\n\t
                                1. A tree with eight vertices, exactly two of degree three.<\/li>\r\n\t
                                2. A connected graph with eight vertices, exactly two of degree 3, which is not a tree.<\/li>\r\n<\/ol>\r\n

                                  For the following exercises, use figure 11 to draw three possible spanning trees that fit the given description.<\/p>\r\n\r\n[caption id=\"attachment_13198\" align=\"aligncenter\" width=\"741\"]\"Two Figure 11[\/caption]\r\n\r\n

                                    \r\n\t
                                  1. Three spanning trees of Graph\u00a0A<\/i>, which include both edges\u00a0be<\/i>\u00a0and\u00a0de<\/i>.<\/li>\r\n\t
                                  2. Three spanning trees of Graph\u00a0K<\/i>, which include edges\u00a0mn<\/i>\u00a0and\u00a0oq<\/i>, but do not include\u00a0no<\/i>.<\/li>\r\n<\/ol>\r\n

                                    For the following exercises, use Kruskal\u2019s Algorithm to find a minimum spanning tree of the given graph (figure 12). Graph it and calculate its weight.<\/p>\r\n\r\n[caption id=\"attachment_13204\" align=\"aligncenter\" width=\"1219\"]\"Two Figure 12[\/caption]\r\n\r\n

                                      \r\n\t
                                    1. Graph 17<\/em><\/li>\r\n\t
                                    2. Graph 18<\/em><\/li>\r\n<\/ol>","rendered":"

                                      Graph Basics<\/h2>\n

                                      For the following exercises, use the given figure below (Figure 1).<\/p>\n

                                      \"Five
                                      Figure 1<\/figcaption><\/figure>\n
                                        \n
                                      1. Determine the number of vertices in Graph\u00a0S<\/i>.<\/li>\n
                                      2. Identify the graph with the fewest edges.<\/li>\n
                                      3. Name the vertices in Graph\u00a0U<\/i>.<\/li>\n
                                      4. Identify any pairs of vertices in Graph\u00a0S<\/i>\u00a0that are not adjacent.<\/li>\n
                                      5. Which graphs only has vertices of degree 2?<\/li>\n
                                      6. Identify the graph in which the sum of the degrees of the vertices is 16.<\/li>\n<\/ol>\n

                                        Graph Structures<\/h2>\n

                                        For the following exercises, use the given figure below (Figure 2).<\/p>\n

                                        \"Four
                                        Figure 2<\/figcaption><\/figure>\n
                                          \n
                                        1. Explain why Graph\u00a0B<\/i>\u00a0is not a subgraph of Graph\u00a0C<\/i>.<\/li>\n
                                        2. How many edges are in a complete graph with 12 vertices?<\/li>\n<\/ol>\n

                                          Navigating Graphs<\/h2>\n

                                          For the following exercises, use Graph\u00a0A<\/i> in the given figure below (Figure 3). Consider each sequence of vertices. Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.<\/p>\n

                                          \"Two
                                          Figure 3<\/figcaption><\/figure>\n
                                            \n
                                          1. e<\/i>\u00a0\u2192\u00a0d<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192\u00a0e<\/i>\u00a0\u2192\u00a0f<\/i><\/li>\n
                                          2. e<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192\u00a0d<\/i>\u00a0\u2192\u00a0e<\/i>\u00a0\u2192\u00a0f<\/i>\u00a0\u2192\u00a0c<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192\u00a0d<\/i><\/li>\n
                                          3. e<\/i>\u00a0\u2192\u00a0f<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192\u00a0d<\/i><\/li>\n<\/ol>\n

                                            For the following exercises, use Graph\u00a0K <\/i>(Figure 3) . Identify each sequence of vertices as a closed walk, circuit (closed trail), and\/or directed cycle (closed path). Indicate all that apply.<\/p>\n

                                              \n
                                            1. n<\/i>\u00a0\u2192\u00a0o<\/i>\u00a0\u2192\u00a0q<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0p<\/i>\u00a0\u2192\u00a0m<\/i>\u00a0\u2192\u00a0n<\/i><\/li>\n
                                            2. m<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0o<\/i>\u00a0\u2192\u00a0q<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0p<\/i>\u00a0\u2192\u00a0o<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0m<\/i><\/li>\n
                                            3. p<\/i>\u00a0\u2192\u00a0o<\/i>\u00a0\u2192\u00a0q<\/i>\u00a0\u2192\u00a0n<\/i>\u00a0\u2192\u00a0m<\/i>\u00a0\u2192\u00a0p<\/i><\/li>\n<\/ol>\n

                                              Euler Circuits<\/h2>\n

                                              For the following exercises, use the graphs and multigraphs shown below (Figure 4). Identify any graphs and\/or multigraphs with the given characteristics. If there are none, state so.<\/p>\n

                                              \"Five
                                              Figure 4<\/figcaption><\/figure>\n
                                                \n
                                              1. connected<\/li>\n
                                              2. disconnected<\/li>\n
                                              3. Eulerian<\/li>\n<\/ol>\n

                                                Euler Trails<\/h2>\n

                                                For the following exercises, use the graphs and multigraphs in Figure 4.<\/p>\n

                                                  \n
                                                1. Determine whether the sequence of edges represents an Euler circuit in Multigraph 15: K<\/i>\u00a0\u2192\u00a0L<\/i>\u00a0\u2192\u00a0N<\/i>\u00a0\u2192\u00a0M<\/i>\u00a0\u2192\u00a0O<\/i>\u00a0\u2192\u00a0S<\/i>\u00a0\u2192\u00a0T<\/i>\u00a0\u2192\u00a0Q<\/i>\u00a0\u2192\u00a0U<\/i>\u00a0\u2192\u00a0P<\/i>\u00a0\u2192\u00a0R<\/i><\/li>\n
                                                2. Find an Euler circuit beginning and ending at vertex g<\/i>\u00a0in Graph 12 if one exists. Otherwise, explain how you know such an Euler circuit does not exist.<\/li>\n
                                                3. Give an example of a pair of edges that could be duplicated to eulerize Multigraph 14.<\/li>\n<\/ol>\n

                                                  For the following exercises, use the graphs and multigraphs in Figure 4. Identify any graphs and\/or multigraphs with the given characteristics. If there are none, state so.<\/p>\n

                                                    \n
                                                  1. Exactly two vertices of odd degree<\/li>\n
                                                  2. Has an Euler trail<\/li>\n<\/ol>\n

                                                    Hamilton Circuits<\/h2>\n

                                                    For the following exercises, refer to the graph in the given in figure 5.<\/p>\n

                                                    \"A
                                                    Figure 5<\/figcaption><\/figure>\n
                                                      \n
                                                    1. A student has been asked to use Fleury\u2019s algorithm to construct an Euler trail in the given graph. The student decides to begin the trail at vertex\u00a0d<\/i>. Is this a good choice, why or why not?<\/li>\n
                                                    2. A student who is using Fleury\u2019s algorithm to construct an Euler trail has decided to begin with\u00a0f<\/i>\u00a0\u2192\u00a0d<\/i>\u00a0\u2192\u00a0a<\/i>\u00a0\u2192\u00a0b<\/i>\u00a0\u2192 \u2026. If the student is off to a good start, help the student by completing the Euler trail. If the student has made an error, explain the error.<\/li>\n
                                                    3. Use Fleury\u2019s algorithm to construct an Euler trail for the given graph beginning at the vertex of your choice.<\/li>\n<\/ol>\n

                                                      For the following exercises, use the graphs from figures 6 and 7 to determine whether the sequence of vertices in the given graph is a Hamilton cycle, an Euler circuit, both, or neither.<\/p>\n

                                                      \"Two
                                                      Figure 6<\/figcaption><\/figure>\n
                                                      \"Graph
                                                      Figure 7<\/figcaption><\/figure>\n
                                                        \n
                                                      1. Graph F. a \u2192 b \u2192 e \u2192 c \u2192 b \u2192 d \u2192 c \u2192 a<\/em><\/li>\n
                                                      2. Graph K. m \u2192 n \u2192 q \u2192 o \u2192 p \u2192 m<\/em><\/li>\n
                                                      3. Graph A. b \u2192 d \u2192 e \u2192 f \u2192 c \u2192 b \u2192 e<\/em><\/li>\n<\/ol>\n

                                                        For the following exercises, evaluate the factorial expression for the given value of [latex]n[\/latex].<\/p>\n

                                                          \n
                                                        1. [latex](n\u22121)!,n=12[\/latex]<\/li>\n
                                                        2. [latex](n\u22121)!,n=14[\/latex]<\/li>\n
                                                        3. Calculate the number of distinct Hamilton cycles in a complete graph with [latex]13[\/latex] vertices.<\/li>\n<\/ol>\n

                                                          For the following exercises, use figure 8 to find the weight of each Hamilton cycle.<\/p>\n

                                                          \"Graph
                                                          Figure 8<\/figcaption><\/figure>\n
                                                            \n
                                                          1. q<\/i>\u00a0\u2192\u00a0t<\/i>\u00a0\u2192\u00a0w<\/i>\u00a0\u2192\u00a0x<\/i>\u00a0\u2192\u00a0u<\/i>\u00a0\u2192\u00a0y<\/i>\u00a0\u2192\u00a0v<\/i>\u00a0\u2192\u00a0s<\/i>\u00a0\u2192\u00a0r<\/i>\u00a0\u2192\u00a0q<\/i><\/li>\n
                                                          2. w<\/i>\u00a0\u2192\u00a0x<\/i>\u00a0\u2192\u00a0y<\/i>\u00a0\u2192\u00a0u<\/i>\u00a0\u2192\u00a0v<\/i>\u00a0\u2192\u00a0s<\/i>\u00a0\u2192\u00a0r<\/i>\u00a0\u2192\u00a0q<\/i>\u00a0\u2192\u00a0t<\/i>\u00a0\u2192\u00a0w<\/i><\/li>\n<\/ol>\n

                                                            Hamilton Paths<\/h2>\n

                                                            For the following exercises, use figure 9 to determine whether the sequence of vertices in the given graph is a Hamilton path, an Euler trail, both, or neither.<\/p>\n

                                                            \"Two
                                                            Figure 9<\/figcaption><\/figure>\n
                                                              \n
                                                            1. Graph A. e \u2192 b \u2192 c \u2192 f \u2192 e \u2192 b \u2192 e<\/em><\/li>\n
                                                            2. Graph A. b \u2192 c \u2192 f \u2192 e \u2192 d \u2192 b \u2192 e<\/em><\/li>\n
                                                            3. Graph K. n \u2192 q \u2192 o \u2192 p \u2192 m<\/em><\/li>\n
                                                            4. Graph K. o \u2192 q \u2192 m \u2192 n \u2192 p<\/em><\/li>\n<\/ol>\n

                                                              Traveling Sales Person Problem<\/h2>\n

                                                              For the following exercises, determine whether the algorithm described is a greedy algorithm or a brute force algorithm.<\/p>\n

                                                                \n
                                                              1. A lumber distributor is loading pallets onto trucks with the intention of using the fewest trucks possible to send a shipment. The distributor loads the pallets with the greatest length that will fit on the truck first and continues loading until no more pallets will fit. Then the next truck is loaded using the same approach.<\/li>\n
                                                              2. A traveler wants to visit five cities by airplane. The traveler lists all the possible orders in which the cities can be visited then calculates the best airfare for each itinerary and selects the least expensive option.<\/li>\n<\/ol>\n

                                                                For the following exercises, list all the distinct Hamilton cycles beginning at the given vertex in the given graph (figure 10). Indicate which pairs of Hamilton cycles are reverses of each other.<\/p>\n

                                                                \"Two
                                                                Figure 10<\/figcaption><\/figure>\n
                                                                  \n
                                                                1. Graph 17, vertex\u00a0a<\/i><\/li>\n
                                                                2. Graph 18, vertex\u00a0m<\/i><\/li>\n<\/ol>\n

                                                                  For the following exercises, find a Hamilton cycle of least weight for the given graph in Figure 10, beginning at the given vertex, and using the brute force method. What is the weight of the cycle?<\/p>\n

                                                                    \n
                                                                  1. Graph 18; vertex\u00a0m<\/i><\/li>\n
                                                                  2. Graph 17; vertex\u00a0a<\/i><\/li>\n<\/ol>\n

                                                                    Spanning Trees<\/h2>\n

                                                                    For the following exercises, draw a graph with the given characteristics.<\/p>\n

                                                                      \n
                                                                    1. A tree with eight vertices, exactly two of degree three.<\/li>\n
                                                                    2. A connected graph with eight vertices, exactly two of degree 3, which is not a tree.<\/li>\n<\/ol>\n

                                                                      For the following exercises, use figure 11 to draw three possible spanning trees that fit the given description.<\/p>\n

                                                                      \"Two
                                                                      Figure 11<\/figcaption><\/figure>\n
                                                                        \n
                                                                      1. Three spanning trees of Graph\u00a0A<\/i>, which include both edges\u00a0be<\/i>\u00a0and\u00a0de<\/i>.<\/li>\n
                                                                      2. Three spanning trees of Graph\u00a0K<\/i>, which include edges\u00a0mn<\/i>\u00a0and\u00a0oq<\/i>, but do not include\u00a0no<\/i>.<\/li>\n<\/ol>\n

                                                                        For the following exercises, use Kruskal\u2019s Algorithm to find a minimum spanning tree of the given graph (figure 12). Graph it and calculate its weight.<\/p>\n

                                                                        \"Two
                                                                        Figure 12<\/figcaption><\/figure>\n
                                                                          \n
                                                                        1. Graph 17<\/em><\/li>\n
                                                                        2. Graph 18<\/em><\/li>\n<\/ol>\n","protected":false},"author":15,"menu_order":17,"template":"","meta":{"_candela_citation":"[]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":75,"module-header":"practice","content_attributions":[],"internal_book_links":[],"video_content":null,"cc_video_embed_content":{"cc_scripts":"","media_targets":[]},"try_it_collection":null,"_links":{"self":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8452"}],"collection":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/users\/15"}],"version-history":[{"count":9,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8452\/revisions"}],"predecessor-version":[{"id":13230,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8452\/revisions\/13230"}],"part":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/parts\/75"}],"metadata":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8452\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=8452"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=8452"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=8452"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=8452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}