{"id":2718,"date":"2023-05-12T19:24:19","date_gmt":"2023-05-12T19:24:19","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&p=2718"},"modified":"2025-08-29T20:16:14","modified_gmt":"2025-08-29T20:16:14","slug":"euler-and-hamiltonian-paths-and-circuits-learn-it-5","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/euler-and-hamiltonian-paths-and-circuits-learn-it-5\/","title":{"raw":"Euler and Hamiltonian Paths and Circuits: Learn It 5","rendered":"Euler and Hamiltonian Paths and Circuits: Learn It 5"},"content":{"raw":"

Spanning Trees<\/h2>\r\n

A company requires reliable internet and phone connectivity between their five offices (named [latex]A[\/latex], [latex]B[\/latex], [latex]C[\/latex], [latex]D[\/latex], and [latex]E[\/latex] for simplicity) in New York, so they decide to lease dedicated lines from the phone company. The phone company will charge for each link made. The costs, in thousands of dollars per year, are shown in the graph.<\/p>\r\n

\r\n[caption id=\"attachment_2722\" align=\"aligncenter\" width=\"573\"]\"graph Figure 1. A map with five vertices, [latex]A[\/latex], [latex]B[\/latex], [latex]C[\/latex], [latex]D[\/latex], and [latex]E[\/latex], representing offices with the amount charged for each link[\/caption]\r\n<\/center>\r\n

 <\/p>\r\n

In this case, we don\u2019t need to find a circuit, or even a specific path; all we need to do is make sure we can make a call from any office to any other. In other words, we need to be sure there is a path from any vertex to any other vertex. We can use a spanning tree<\/strong>.<\/p>\r\n

\r\n
\r\n

spanning tree<\/h3>\r\n

A spanning tree<\/strong> is a connected graph using all vertices in which there are no circuits.<\/p>\r\n

In other words, there is a path from any vertex to any other vertex, but no circuits.<\/p>\r\n<\/div>\r\n<\/section>\r\n

\r\n

When deciding whether a graph is a spanning tree, check the following characteristics:<\/p>\r\n

    \r\n\t
  • All vertices are included.<\/li>\r\n\t
  • No vertices are adjacent that were not adjacent in the original graph.<\/li>\r\n\t
  • The graph is connected.<\/li>\r\n\t
  • There are no cycles.<\/li>\r\n<\/ul>\r\n<\/section>\r\n

    Some examples of spanning trees are shown below. Notice there are no circuits in the trees, and it is fine to have vertices with degree higher than two.<\/p>\r\n

    \r\n[caption id=\"attachment_2723\" align=\"aligncenter\" width=\"777\"]\"Five Figure 2. Five different spanning trees[\/caption]\r\n<\/center>\r\n
    Use the figure below to determine which of graphs [latex]M1, M2, M3,[\/latex] and [latex]M4[\/latex], are spanning trees of [latex]Q[\/latex].
    \"Five<\/center>[reveal-answer q=\"997648\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997648\"]\r\n\r\n
      \r\n\t
    1. Graph [latex]M1[\/latex] is not a spanning tree of Graph [latex]Q[\/latex] because it has a cycle ([latex]c, d, f, e[\/latex]).<\/li>\r\n\t
    2. Graph [latex]M2[\/latex] is a spanning tree of Graph [latex]Q[\/latex] because it has all the original vertices, no vertices are adjacent in [latex]M2[\/latex] that weren\u2019t adjacent in Graph [latex]Q[\/latex], Graph [latex]M2[\/latex] is connected and it contains no cycles.<\/li>\r\n\t
    3. Graph [latex]M3[\/latex] is not a spanning tree of Graph [latex]Q[\/latex] because vertices [latex]a[\/latex] and [latex]f[\/latex] are adjacent in Graph [latex]M3[\/latex] but not in Graph [latex]Q[\/latex].<\/li>\r\n\t
    4. Graph [latex]M4[\/latex] is not a spanning tree of Graph [latex]Q[\/latex] because it is not connected.<\/li>\r\n<\/ol>\r\n\r\nSo, only graph [latex]M2[\/latex] is a spanning tree of Graph [latex]Q[\/latex]. [\/hidden-answer]<\/section>\r\n

      Usually, we have a starting graph to work from, like in the phone example above. In this case, we form our spanning tree by finding a subgraph<\/strong> \u2013 a new graph formed using all the vertices but only some of the edges from the original graph. No edges will be created where they didn\u2019t already exist.<\/p>\r\n

      Suppose that you wanted to find a spanning tree within a graph. One approach is to find paths within the graph. You can start at any vertex, go any direction, and create a path through the graph stopping only when you can\u2019t continue without backtracking as shown in the figure below.<\/p>\r\n

      \r\n[caption id=\"attachment_8814\" align=\"aligncenter\" width=\"300\"]\"A Figure 3. A spanning tree within a graph[\/caption]\r\n<\/center>\r\n

       <\/p>\r\n

      Once you have stopped, pick a vertex along the path you drew as a starting point for another path. Make sure to visit only vertices you have not visited before as shown in the figure below.<\/p>\r\n

      \r\n[caption id=\"attachment_8815\" align=\"aligncenter\" width=\"300\"]\"A Figure 4. Pick a vertex as a starting point for another path[\/caption]\r\n<\/center>\r\n

       <\/p>\r\n

      Repeat this process until all vertices have been visited as shown in the figure below.<\/p>\r\n

      \r\n[caption id=\"attachment_8816\" align=\"aligncenter\" width=\"300\"]\"A Figure 5. Repeat until all vertices have been visited[\/caption]\r\n<\/center>\r\n

       <\/p>\r\n

      The end result is a tree that spans the entire graph as shown in the figure below.<\/p>\r\n

      \r\n[caption id=\"attachment_8817\" align=\"aligncenter\" width=\"300\"]\"A Figure 6. The end result, a tree spanning the entire graph[\/caption]\r\n<\/center>\r\n

       <\/p>\r\n

      Notice that this subgraph is a tree because it is connected and acyclic. It also visits every vertex of the original graph, so it is a spanning tree. However, it is not the only spanning tree for this graph. By making different turns, we could create any number of distinct spanning trees.<\/p>\r\n

      \r\n

      Construct two distinct spanning trees for the graph below.<\/p>\r\n

      \"Graph<\/center>[reveal-answer q=\"997621\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997621\"] Two possible solutions are given below.
      \"Two<\/center>
      First Spanning Tree for Graph [latex]L[\/latex]<\/strong><\/span><\/center>\r\n

       <\/p>\r\n

      \"Two<\/center>
      Second Spanning Tree for Graph [latex]L[\/latex] [\/hidden-answer]<\/span><\/strong><\/center><\/section>\r\n

      Of course, any random spanning tree isn\u2019t really what we want. We want the minimum cost spanning tree (MCST)<\/strong>.<\/p>\r\n

      In many applications of spanning trees, the graphs are weighted and we want to find the spanning tree of least possible weight. For example, the graph might represent a computer network, and the weights might represent the cost involved in connecting two devices. So, finding a spanning tree with the lowest possible total weight, or minimum spanning tree, means saving money!<\/p>\r\n

      \r\n
      \r\n

      minimum cost spanning tree (MCST)<\/h3>\r\n

      The minimum cost spanning tree<\/strong> is the spanning tree with the smallest total edge weight.<\/p>\r\n<\/div>\r\n<\/section>\r\n

      A nearest neighbor style approach doesn\u2019t make as much sense here since we don\u2019t need a circuit, so instead we will take an approach similar to sorted edges.<\/p>\r\n

      \r\n
      \r\n

      Kruskal\u2019s algorithm<\/h3>\r\n
        \r\n\t
      1. Choose any edge with the minimum weight of all edges.<\/li>\r\n\t
      2. Choose another edge of minimum weight from the remaining edges. The second edge does not have to be connected to the first edge.<\/li>\r\n\t
      3. Choose another edge of minimum weight from the remaining edges, but do not select any edge that creates a cycle in the subgraph you are creating.<\/li>\r\n\t
      4. Repeat step 3 until all the vertices of the original graph are included and you have a spanning tree.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<\/section>\r\n

        Watch the following video on how to use Kruskal's Algorithm to find minimum spanning trees.<\/p>\r\n