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

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.

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

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.