Define spanning tree and minimum spanning tree. Mention the conditions for two graphs for being isomorphic with an example.

Question

Suresh Chand · Accepted Answer

Let G be a simple graph. A spanning tree of G is a subgroup of G that is a tree containing all vertex of G. Spanning tree has n vertices and n-1 edges as compared to graph G. A minimum spanning tree is a subgraph of a weighted graph G that includes all vertices of graph G and has minimum weight than all other Spanning trees of the same graph. Two graphs are said to be isomorphic if they are perhaps the same graphs just drawn differently with different names. i.e. they have identical behaviour for anu graph theoretic property. Some conditions for two graphs to be isomorphic are:- Both graphics should have same number of vertices i.e. |v1| = |v2| No. of edges of both graphs soluld be Equal i.e. |E1| = |E2| Both graphs should have same sequences and vertices of both graphics should have same degrees. Both have same no. of vertices Both have same no. of edges Degree G1 deg(a) = 3 deg(b) = 2 deg(c) = 3 deg(d) = 3 deg(e) = 1 G2 deg(v2) = 3 deg(v4) = 2 deg(v5) = 3 deg(v3) = 3 deg(v1) = 1 Hence, they are isomorphic.

Define spanning tree and minimum spanning tree. Mention the conditions for two graphs for being isomorphic with an example.

Leave your Answer:

Hits Counter

Question

Define spanning tree and minimum spanning tree. Mention the conditions for two graphs for being isomorphic with an example.

Leave your Answer: