{"id":64,"date":"2025-01-02T23:05:07","date_gmt":"2025-01-02T23:05:07","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/chapter\/graph-theory-get-stronger-answer-key\/"},"modified":"2025-01-02T23:05:07","modified_gmt":"2025-01-02T23:05:07","slug":"graph-theory-get-stronger-answer-key","status":"publish","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/chapter\/graph-theory-get-stronger-answer-key\/","title":{"raw":"Graph Theory: Get Stronger Answer Key","rendered":"Graph Theory: Get Stronger Answer Key"},"content":{"raw":"\n

Graph Basics<\/h2>\n
    \n\t
  1.  Graph S<\/em> has [latex]5[\/latex] vertices labeled a, b, c, d<\/em>, and e<\/em>.<\/li>\n\t
  2.  <\/li>\n\t
  3.  The vertices are labeled a, b, c, d, e<\/em>, and the additional vertex f<\/em>.<\/li>\n\t
  4.  <\/li>\n\t
  5. Graph T<\/em><\/li>\n\t
  6.  <\/li>\n<\/ol>\n

    Graph Structures<\/h2>\n

     <\/p>\n\n[caption id=\"attachment_13197\" align=\"alignnone\" width=\"1694\"]\"Four Figure 2[\/caption]\n\n

      \n\t
    1. Graph B<\/em> has an edge between vertices v<\/em> and r<\/em> that does not exist in Graph C<\/em>. For B to be a subgraph of C, all of B's edges would have to be present in C with exactly the same connections between vertices. Since the edge is missing in Graph C<\/em>, we can conclusively say that Graph B<\/em> is not a subgraph of Graph C<\/em>.<\/li>\n\t
    2.  <\/li>\n<\/ol>\n

      Navigating Graphs<\/h2>\n
        \n\t
      1. The sequence e \u2013 d \u2013 b \u2013 e \u2013 f<\/em> is both a walk and a trail. It is not a path due to the repeated vertex e<\/em>.<\/li>\n\t
      2.  <\/li>\n\t
      3. This is not a valid walk, trail, or path. There's no direct edge from f<\/em> to b<\/em>, the sequence e \u2013 f \u2013 b \u2013 d<\/em> cannot occur without passing through another vertex or edge. <\/li>\n\t
      4.  <\/li>\n\t
      5.  The sequence m \u2013 n \u2013 o \u2013 q \u2013 n \u2013 p \u2013 o \u2013 n \u2013 m<\/em> is a closed walk because it starts and ends at the same vertex (m<\/em>) and traverses through edges more than once. It is not a circuit (closed trail) because it uses some edges more than once. It is also not a cycle (closed path) because it revisits vertices.<\/li>\n\t
      6.  <\/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\n[caption id=\"attachment_13199\" align=\"alignnone\" width=\"1800\"]\"Five Figure 4[\/caption]\n\n

          \n\t
        1.  Graphs 11<\/em>, 12<\/em>, and 13<\/em> are all connected.<\/li>\n\t
        2.  <\/li>\n\t
        3. Graph 12<\/em><\/li>\n<\/ol>\n

          Euler Trails<\/h2>\n
            \n\t
          1.  <\/li>\n\t
          2. Find an Euler circuit beginning and ending at vertex g<\/i> in Graph 12 if one exists. Otherwise, explain how you know such an Euler circuit does not exist.<\/li>\n\t
          3.  <\/li>\n\t
          4. Multigraph 14<\/em><\/li>\n\t
          5.  <\/li>\n<\/ol>\n

            Hamilton Circuits<\/h2>\n
              \n\t
            1. Yes, beginning the Euler trail at vertex d<\/em> is a good choice, as Fleury's algorithm requires that for a graph with an Eulerian trail (a trail that visits every edge exactly once), the trail must start (and end) at one of the vertices with an odd degree. The path d\u2192a\u2192b\u2192e\u2192d\u2192f\u2192c\u2192g\u2192f, <\/em>starts and ends with the vertices that have an odd degree, and does not repeat an edge.<\/li>\n\t
            2.  <\/li>\n\t
            3. One option is: d\u2192a\u2192b\u2192e\u2192d\u2192f\u2192c\u2192g\u2192f<\/em><\/li>\n\t
            4.  <\/li>\n\t
            5. The sequence m \u2192 n \u2192 q \u2192 o \u2192 p \u2192 m<\/em> is a Hamiltonian cycle but not an Eulerian circuit in Graph K<\/em>.<\/li>\n\t
            6.  <\/li>\n\t
            7. [latex]39,916,800[\/latex]<\/li>\n\t
            8.  <\/li>\n\t
            9. [latex]239,500,800[\/latex]<\/li>\n\t
            10.  <\/li>\n\t
            11. [latex]70[\/latex]<\/li>\n<\/ol>\n

              Hamilton Paths<\/h2>\n
                \n\t
              1.  <\/li>\n\t
              2. Euler trail<\/li>\n\t
              3.  <\/li>\n\t
              4. Neither<\/li>\n<\/ol>\n

                Traveling Sales Person Problem<\/h2>\n
                  \n\t
                1.  <\/li>\n\t
                2. The approach described is a brute force algorithm. In a brute force algorithm, all possible solutions are generated and evaluated to find the best solution. In this case, the traveler lists all possible orders in which the cities can be visited, calculates the cost for each possible itinerary, and then selects the one with the least expensive airfare.<\/li>\n\t
                3.  <\/li>\n\t
                4. The distinct Hamiltonian cycles beginning at vertex 'm' in Graph 18, not counting reversals as distinct, are:\n\n
                    \n\t
                  • m \u2192 n \u2192 o \u2192 p \u2192 q \u2192 m<\/em><\/li>\n\t
                  • m \u2192 n \u2192 o \u2192 q \u2192 p \u2192 m<\/em><\/li>\n\t
                  • m \u2192 n \u2192 p \u2192 o \u2192 q \u2192 m<\/em><\/li>\n\t
                  • m \u2192 n \u2192 p \u2192 q \u2192 o \u2192 m<\/em><\/li>\n\t
                  • m \u2192 n \u2192 q \u2192 o \u2192 p \u2192 m<\/em><\/li>\n\t
                  • m \u2192 n \u2192 q \u2192 p \u2192 o \u2192 m<\/em><\/li>\n\t
                  • m \u2192 o \u2192 n \u2192 p \u2192 q \u2192 m<\/em><\/li>\n\t
                  • m \u2192 o \u2192 n \u2192 q \u2192 p \u2192 m<\/em><\/li>\n\t
                  • m \u2192 o \u2192 p \u2192 n \u2192 q \u2192 m<\/em><\/li>\n\t
                  • m \u2192 o \u2192 p \u2192 q \u2192 n \u2192 m<\/em><\/li>\n\t
                  • m \u2192 o \u2192 q \u2192 n \u2192 p \u2192 m<\/em><\/li>\n\t
                  • m \u2192 o \u2192 q \u2192 p \u2192 n \u2192 m<\/em><\/li>\n\t
                  • Note: each cycle can be reversed<\/li>\n<\/ul>\n<\/li>\n\t
                  •  <\/li>\n\t
                  • Cycles a\u2192c\u2192b\u2192d\u2192a <\/em>and a\u2192d\u2192b\u2192c\u2192a <\/em>have the lowest weight of [latex]18[\/latex].<\/li>\n<\/ol>\n

                    Spanning Trees<\/h2>\n

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

                      \n\t
                    1.  <\/li>\n\t
                    2. Answers may very<\/li>\n\t
                    3.  <\/li>\n\t
                    4. Answers may very<\/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\n[caption id=\"attachment_13204\" align=\"aligncenter\" width=\"1219\"]\"Two Figure 12[\/caption]\n\n

                        \n\t
                      1.  <\/li>\n\t
                      2.  <\/li>\n<\/ol>\n","rendered":"

                        Graph Basics<\/h2>\n
                          \n
                        1.  Graph S<\/em> has [latex]5[\/latex] vertices labeled a, b, c, d<\/em>, and e<\/em>.<\/li>\n
                        2.  <\/li>\n
                        3.  The vertices are labeled a, b, c, d, e<\/em>, and the additional vertex f<\/em>.<\/li>\n
                        4.  <\/li>\n
                        5. Graph T<\/em><\/li>\n
                        6.  <\/li>\n<\/ol>\n

                          Graph Structures<\/h2>\n

                           <\/p>\n

                          \"Four
                          Figure 2<\/figcaption><\/figure>\n
                            \n
                          1. Graph B<\/em> has an edge between vertices v<\/em> and r<\/em> that does not exist in Graph C<\/em>. For B to be a subgraph of C, all of B’s edges would have to be present in C with exactly the same connections between vertices. Since the edge is missing in Graph C<\/em>, we can conclusively say that Graph B<\/em> is not a subgraph of Graph C<\/em>.<\/li>\n
                          2.  <\/li>\n<\/ol>\n

                            Navigating Graphs<\/h2>\n
                              \n
                            1. The sequence e \u2013 d \u2013 b \u2013 e \u2013 f<\/em> is both a walk and a trail. It is not a path due to the repeated vertex e<\/em>.<\/li>\n
                            2.  <\/li>\n
                            3. This is not a valid walk, trail, or path. There’s no direct edge from f<\/em> to b<\/em>, the sequence e \u2013 f \u2013 b \u2013 d<\/em> cannot occur without passing through another vertex or edge. <\/li>\n
                            4.  <\/li>\n
                            5.  The sequence m \u2013 n \u2013 o \u2013 q \u2013 n \u2013 p \u2013 o \u2013 n \u2013 m<\/em> is a closed walk because it starts and ends at the same vertex (m<\/em>) and traverses through edges more than once. It is not a circuit (closed trail) because it uses some edges more than once. It is also not a cycle (closed path) because it revisits vertices.<\/li>\n
                            6.  <\/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.  Graphs 11<\/em>, 12<\/em>, and 13<\/em> are all connected.<\/li>\n
                              2.  <\/li>\n
                              3. Graph 12<\/em><\/li>\n<\/ol>\n

                                Euler Trails<\/h2>\n
                                  \n
                                1.  <\/li>\n
                                2. Find an Euler circuit beginning and ending at vertex g<\/i> in Graph 12 if one exists. Otherwise, explain how you know such an Euler circuit does not exist.<\/li>\n
                                3.  <\/li>\n
                                4. Multigraph 14<\/em><\/li>\n
                                5.  <\/li>\n<\/ol>\n

                                  Hamilton Circuits<\/h2>\n
                                    \n
                                  1. Yes, beginning the Euler trail at vertex d<\/em> is a good choice, as Fleury’s algorithm requires that for a graph with an Eulerian trail (a trail that visits every edge exactly once), the trail must start (and end) at one of the vertices with an odd degree. The path d\u2192a\u2192b\u2192e\u2192d\u2192f\u2192c\u2192g\u2192f, <\/em>starts and ends with the vertices that have an odd degree, and does not repeat an edge.<\/li>\n
                                  2.  <\/li>\n
                                  3. One option is: d\u2192a\u2192b\u2192e\u2192d\u2192f\u2192c\u2192g\u2192f<\/em><\/li>\n
                                  4.  <\/li>\n
                                  5. The sequence m \u2192 n \u2192 q \u2192 o \u2192 p \u2192 m<\/em> is a Hamiltonian cycle but not an Eulerian circuit in Graph K<\/em>.<\/li>\n
                                  6.  <\/li>\n
                                  7. [latex]39,916,800[\/latex]<\/li>\n
                                  8.  <\/li>\n
                                  9. [latex]239,500,800[\/latex]<\/li>\n
                                  10.  <\/li>\n
                                  11. [latex]70[\/latex]<\/li>\n<\/ol>\n

                                    Hamilton Paths<\/h2>\n
                                      \n
                                    1.  <\/li>\n
                                    2. Euler trail<\/li>\n
                                    3.  <\/li>\n
                                    4. Neither<\/li>\n<\/ol>\n

                                      Traveling Sales Person Problem<\/h2>\n
                                        \n
                                      1.  <\/li>\n
                                      2. The approach described is a brute force algorithm. In a brute force algorithm, all possible solutions are generated and evaluated to find the best solution. In this case, the traveler lists all possible orders in which the cities can be visited, calculates the cost for each possible itinerary, and then selects the one with the least expensive airfare.<\/li>\n
                                      3.  <\/li>\n
                                      4. The distinct Hamiltonian cycles beginning at vertex ‘m’ in Graph 18, not counting reversals as distinct, are:\n
                                          \n
                                        • m \u2192 n \u2192 o \u2192 p \u2192 q \u2192 m<\/em><\/li>\n
                                        • m \u2192 n \u2192 o \u2192 q \u2192 p \u2192 m<\/em><\/li>\n
                                        • m \u2192 n \u2192 p \u2192 o \u2192 q \u2192 m<\/em><\/li>\n
                                        • m \u2192 n \u2192 p \u2192 q \u2192 o \u2192 m<\/em><\/li>\n
                                        • m \u2192 n \u2192 q \u2192 o \u2192 p \u2192 m<\/em><\/li>\n
                                        • m \u2192 n \u2192 q \u2192 p \u2192 o \u2192 m<\/em><\/li>\n
                                        • m \u2192 o \u2192 n \u2192 p \u2192 q \u2192 m<\/em><\/li>\n
                                        • m \u2192 o \u2192 n \u2192 q \u2192 p \u2192 m<\/em><\/li>\n
                                        • m \u2192 o \u2192 p \u2192 n \u2192 q \u2192 m<\/em><\/li>\n
                                        • m \u2192 o \u2192 p \u2192 q \u2192 n \u2192 m<\/em><\/li>\n
                                        • m \u2192 o \u2192 q \u2192 n \u2192 p \u2192 m<\/em><\/li>\n
                                        • m \u2192 o \u2192 q \u2192 p \u2192 n \u2192 m<\/em><\/li>\n
                                        • Note: each cycle can be reversed<\/li>\n<\/ul>\n<\/li>\n
                                        •  <\/li>\n
                                        • Cycles a\u2192c\u2192b\u2192d\u2192a <\/em>and a\u2192d\u2192b\u2192c\u2192a <\/em>have the lowest weight of [latex]18[\/latex].<\/li>\n<\/ol>\n

                                          Spanning Trees<\/h2>\n

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

                                            \n
                                          1.  <\/li>\n
                                          2. Answers may very<\/li>\n
                                          3.  <\/li>\n
                                          4. Answers may very<\/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.  <\/li>\n
                                            2.  <\/li>\n<\/ol>\n","protected":false},"author":6,"menu_order":21,"template":"","meta":{"_candela_citation":"[]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":3,"module-header":"","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\/qrpracticepages\/wp-json\/pressbooks\/v2\/chapters\/64"}],"collection":[{"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/wp\/v2\/users\/6"}],"version-history":[{"count":0,"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/pressbooks\/v2\/chapters\/64\/revisions"}],"part":[{"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/pressbooks\/v2\/chapters\/64\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/wp\/v2\/media?parent=64"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/pressbooks\/v2\/chapter-type?post=64"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/wp\/v2\/contributor?post=64"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/qrpracticepages\/wp-json\/wp\/v2\/license?post=64"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}