List all the necessary conditions for the graph to be isomorphic with an  example. Find the maximal flow from the node SOURCE to SINK in the following network flow.

- Hamro CSIT

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

Login Now

The necessary conditions for the graph to be isomorphic are

  1. nunber of vertices must be equal
  2. number of edges must be equal
  3. number of degree of vertices must be equal
  4. Sub-graph consisting same degree must be same.
  5. Adjacent matrix must be same.

Example: In below, We will check whether below graph is isomorphic.

Isomorphic Graphs

Point 1: No. of vertices of G =No. of vertices of H = 8

Point 2: No. of edges of G = No. of edges of H = 10

Degree of verticesof G Degree of vertices of H
deg(a) = 2 deg(s) = 3
deg(b) = 3 deg(t) = 2
deg(c) = 2 deg(u) = 2
deg(d) = 3 deg(v) = 3
deg(e) = 2 deg(w) = 3
deg(f) = 3 deg(x) = 2
deg(g) = 2 deg(y) = 2
deg(h) = 3 deg(z) = 3

Point 3: Degree of vertices of G = degre of vertices of  H as there ae equal no. of verticeshabing degre 2 and 3.

Point 4:Subgraph of G is not equal to sub graph of H

So, They are not isomorphic.

Problem II:

Given graph is

- Hamro CSIT

 

Let’s find maximum flow from S to D using S-D cut method.

X \(\bar{X}\) K(X, \(\bar{X}\))
{A} {B, C, D, E, F} 5 + 15 = 20
{A, B} {C,D, E,F} 15 + 5 + 5 = 25
{A, C} {B, D, E, F} 5 + 5 + 5 = 15
{A, B, C} {D, E, F} 5 + 5 + 5 + 5 = 20
{A, B, D} {C, E, F} 15 + 5 + 15 = 35
{A,C, E} {B, D, F} 5 + 5 + 5 = 15
{A, B, C, D} {E, F} 5 + 15 = 20
{A, C, D, E} {B, F} 5 + 15 = 20
{A, B, C, E} {D, F} 5 + 5 + 5 = 15
{A, B, C, D, E} {F} 15 + 5 = 20

Here,

maximum flow= minimum cut = 15

Finally, the maximum flow is 15.

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