Question

Find the distance between each pair of spanning trees shown in Figures 3(c) and 4 of the graph Gshown in Figure 2.

Short answer

By following the steps get the distance between each pair of spanning trees.

Step-by-step solution

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G that is a tree and which contains all vertices of G.

A tree is an undirected graph that is connected and does not contain any single circuit n vertices has n-1 edges of a tree.

The distance between two spanning trees is the number of edges that are not common in the two spanning trees.

Solution for 3(c) T upper left graph of fig. 4.\({{\bf{T}}_{\bf{1}}}\).

There are three edges in both the graphs that are not included in the other graph.

T={a, b}, {c ,f}, {e, g}.

\({{\bf{T}}_{\bf{1}}}\)={a, b}, {e , f}, {e, g}.

There is total 6 edges not common in the graphs and thus the distance between the two trees is 6.

Solution for 3(c) T upper left graph of fig. 4.\({{\bf{T}}_{\bf{2}}}\).

There are three edges in both the graphs that are not included in the other graph.

T={a, b}, {f, g}.

\({{\bf{T}}_{\bf{2}}}\)={a, b}, {e ,f}.

There is total 4 edges not common in the graphs and thus the distance between the two trees is 4.

Solution for 3(c) T upper left graph of fig. 4\({{\bf{T}}_{\bf{3}}}\).

There are three edges in both the graphs that are not included in the other graph.

T={e , g}, {f, g}.

\({{\bf{T}}_{\bf{3}}}\)={c ,d}, {e ,f}.

There is total 4 edges not common in the graphs and thus the distance between the two trees is 4.

Solution for 3(c) T upper left graph of fig. 4\({{\bf{T}}_4}\).

There are three edges in both the graphs that are not included in the other graph.

T= {f, g}.

\({{\bf{T}}_4}\)= {a ,e}.

There are total 2 edges not common in the graphs and thus the distance between the two trees is 2.

Upper left graph of fig 4 \({{\bf{T}}_{\bf{1}}}\)and upper right graph of fig. 4\({{\bf{T}}_{\bf{2}}}\).

There are three edges in both the graphs that are not included in the other graph.

\({{\bf{T}}_{\bf{1}}}\)={c , g}, {f, g}.

\({{\bf{T}}_{\bf{2}}}\)={c ,f}, {e ,g}.

There are total 4 edges not common in the graphs and thus the distance between the two trees is 4.

Upper left graph of fig 4 \({{\bf{T}}_{\bf{1}}}\)and upper right graph of fig. 4\({{\bf{T}}_{\bf{3}}}\).

There are three edges in both the graphs that are not included in the other graph.

\({{\bf{T}}_{\bf{1}}}\)={a ,e}, {f, g}.

\({{\bf{T}}_{\bf{3}}}\)={a ,b}, {c ,f}.

There are total 4 edges not common in the graphs and thus the distance between the two trees is 4.

Upper left graph of fig 4 \({{\bf{T}}_{\bf{1}}}\)and upper right graph of fig. 4\({{\bf{T}}_4}\).

There are three edges in both the graphs that are not included in the other graph.

\({{\bf{T}}_{\bf{1}}}\)={c , g} ,{e , f} ,{f, g}.

\({{\bf{T}}_4}\)={a ,b}, {c ,f}, {e, g}.

There are total 6 edges not common in the graphs and thus the distance between the two trees is 6.

Upper left graph of fig 4 \({{\bf{T}}_{\bf{2}}}\)and upper right graph of fig. 4\({{\bf{T}}_{\bf{3}}}\).

There are three edges in both the graphs that are not included in the other graph.

\({{\bf{T}}_{\bf{2}}}\)={a , e} ,{e , g}.

\({{\bf{T}}_{\bf{3}}}\)={a ,b}, {c ,g}.

There are total 4 edges not common in the graphs and thus the distance between the two trees is 4.

Upper left graph of fig 4 \({{\bf{T}}_{\bf{2}}}\)and upper right graph of fig. 4\({{\bf{T}}_4}\).

There are three edges in both the graphs that are not included in the other graph.

\({{\bf{T}}_{\bf{2}}}\)={e , f}.

\({{\bf{T}}_4}\)=a ,b}.

There are total 2 edges not common in the graphs and thus the distance between the two trees is 2.

Therefore, this is the distance between each pair of spanning tree.