Question

Devise an algorithm for constructing the spanning forest of a graph based on deleting edges that form simple circuits.

Short answer

By using the algorithm, I can get that spanning forest of a graph based on deleting edges that form simple circuit.

Step-by-step solution

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G which is a tree and contains all vertices of G. A tree is an undirected graph which is connected and does not contain a single cycle n vertex has n-1 edges of a tree.

Determine a graph that has a simple circuit.

Let’s select the first vertex \({{\bf{v}}_{\bf{1}}}\). Add all vertices connected to \({{\bf{v}}_{\bf{1}}}\) by an edge to the list L and M and remove the edge from the graph. L keeps track of all vertices checked in the algorithm, while M keeps track of all vertices used in the last step of the algorithm. Then add all vertices connected by an edge to a vertex of M, if any of these vertices is listed in L then a simple cycle exists, If no such vertex listed in L is ever found, then there does not exist circuit. If a circuit is found, then use the function P to find the previous element in the circuit. If no vertex was added to the L, then choose a new vertex to add to the list and repeat the procedure for this vertex.

Algorithm.

Let G be an undirected graph having vertices\({\bf{V = \{ }}{{\bf{v}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{2}}}{\bf{,}}......{\bf{,}}{{\bf{v}}_{\bf{n}}}{\bf{\} }}\).

\(\begin{array}{c}{\bf{T = G}}\\{\bf{V = \{ }}\,{{\bf{v}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{2}}}{\bf{,}}......{\bf{,}}{{\bf{v}}_{\bf{n}}}{\bf{\} }}\\{\bf{L= \{ }}\,{{\bf{v}}_{\bf{1}}}{\bf{\} }}\\{\bf{M= \{ }}\,{{\bf{v}}_{\bf{1}}}{\bf{\} }}\end{array}\)

\(\begin{array}{c}{\bf{while}}\,{\bf{L}} \ne {\bf{M}}\\{\bf{if}}\,{\bf{M = }}\phi \,{\bf{then}}\\{\bf{for}}\,{\bf{j = 1}}\,{\bf{ton}}\\{\bf{if}}\,{{\bf{v}}_{\bf{j}}} \notin {\bf{L}}\,{\bf{then}}\end{array}\)

\(\begin{array}{c}{\bf{L = L}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{j}}}{\bf{\} }}\\{\bf{M = M}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{j}}}{\bf{\} }}\\{\bf {N = }}\phi \end{array}\)

For every vertex v in M.

\({\bf{for}}\,{\bf{j = 1}}\,{\bf{ton}}\)

If \({\bf{(}}{{\bf{v}}_{\bf{i}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\)is an edge in G then

\({\bf{if}}\,{{\bf{v}}_{\bf{j}}} \in {\bf{L}}\,{\bf{then}}\)

Remove the edge \({\bf{(}}{{\bf{v}}_{\bf{i}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\) from T.

Remove the edge \({\bf{(}}{{\bf{v}}_{\bf{i}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}{\bf{)}}\) from G.

Else

Remove the edge from the graph G.

\(\begin{array}{c}{\bf{L = L}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{j}}}{\bf{\} }}\\{\bf{N = N}} \cup {\bf{\{ }}\,{{\bf{v}}_{\bf{j}}}{\bf{\} }}\\{\bf{M = N}}\\{\bf{return}}\,{\bf{T}}\end{array}\)

Therefore, the results show that spanning forest of a graph G based on deleting edges that form simple circuit.