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

This answer is restricted. Please login to view the answer of this question.

Login Now

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:-

  1. Both graphics should have same number of vertices
    i.e. |v1| = |v2|
  2. No. of edges of both graphs soluld be Equal
    i.e. |E1| = |E2|
  3. Both graphs should have same sequences and vertices of both graphics should have same degrees.

Isomorphic graph | Discrete Structure | HAMROCSIT

  • 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.

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .