Discrete Math: Spanning Trees and MST

Use the Depth First Search algorithm to find the spanning tree of a graph starting from an arbitrary vertex and traversing through the vertices by following alphabetical order, then backtracking when no more edges are available.

Using a depth-first search algorithm, create a spanning tree for a given graph starting from a specified root vertex.

Find a spanning tree for a graph with eight vertices, nine edges, and two circuits by removing two edges to break the circuits.

Find all the spanning trees for a graph with seven vertices, seven edges, and one circuit, by removing one edge to break the circuit.

Find three different spanning trees for a graph with five vertices, seven edges, and multiple overlapping circuits by removing three edges.

A company requires reliable internet and phone connectivity between their five offices. They decide to lease dedicated lines from the phone company. The phone company will charge for each link made. The cost in thousands of dollars per year are shown below in the graph. Find a spanning tree for this graph that ensures connectivity between all offices without forming any circuits.

Run Prim's algorithm on the given graph to construct a minimum spanning tree (MST).

Run Kruskal's algorithm on a connected graph with weighted edges to find the minimum spanning tree.