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

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

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,

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.

Click here to submit your answer.

HAMROCSIT.COM

## Discussion