Define Euler circuit with suitable example. Find the maximal flow s to t from the given network flow.

- Hamro CSIT

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

Login Now

An Eular circuit is a circuit made using a path where every edge of the graph G is used exactly one and only once and the path returns to its statring vertex. A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degrees.

Example:

Eular Circuit Example | HAMROCSIT

It is an Eular circuit because statring and ending vertex are same.

(a-e-c-d-e-b-a)

 

Problem Part:

Let’s do using S-T cut method.

Given,

Maximum Flow S cut | HAMROCSIT

X Y cuts(X, Y) Capacity K(X, Y)
1 {S} {1, 2, 3, ,4, 5, t} {(S, 1), (S, 2), (S, 3)} 8 + 9 + 5 = 22
2 {S, 1} {2, 3, 4, 5, t} {(S, 2), (S, 3), (1, 4)} 9 + 5 + 6 = 20
3 {S, 1, 4} {2, 3, 5, t} {(S, 2), (S, 3), (4, t), (4, 5)} 9 + 5 + 11 + 4 = 29
4 {S, 2} {3, 4, 5, t} {(S, 1), (S, 3), (2, 3), (2, 5)} 8 + 5 + 7 + 5 = 25
5 {S, 1, 2} {3, 4, t} {(S, 3), (1, 4), (2, 5), (2, 3), (3, 4), (3, 6)} 5 + 6 + 5 + 7 = 23
6 {S, 1, 2, 3} {4, 5, t} {(1, 4), (2, 5), (3, 4), (3, 6)} 6 + 5 + 2 + 6 = 19
7 {S, 1. 2, 3, 4} {5, t} {(2, 5), (3, 5), (4, 5), (4, t)} 5 + 6 + 4  + 11 = 26
8 {S, 1, 2, 3, 4, 5} {t} {(4, t), (5, t)} 11 + 13 = 24
9 {S, 1, 2, 3, 5} {4, t} {(1, 4), (3, 4), (5, t)} 6 + 2  + 13 = 21
10 {S, 1, 3, 4} {2, 5, t} {(5, 2), (3, 5), (4, 5), (4, t)} 9 + 6 + 4 + 11 = 30

Here, Minimum cut capacity  = 19 and Maximum flow = 19

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