Graph theory Eulerian graph

Eulerian Graph,Chinese postman problem

1. PRESENTATION On Topic: Graph Theory :Eulerian Graph

2. Seven Bridges of Konigsberg The Konigsberg bridge problem:  Starting and ending at the same point, is it possible to cross all seven bridges just once and return to the starting point. This problem can be represented by a graph. Edges represent bridges and each vertex represents a region. Begun in 1735. Mentioned in Leonhard Euler's paper on “ Seven Bridges of Konigsberg ” . Problem : Walk all 7 bridges without crossing a bridge twice.

3. Eulerian Graph If there is a path joining any two vertices in a graph, that graph is said to be connected . A path that begins and ends at the same vertex without  traversing  any edge more than once is called a  circuit , or a closed path. A circuit that follows each edge exactly once while visiting every vertex is known as an  Eulerian circuit , and the graph is called an Eulerian graph . Note: An Eulerian graph is connected and, in addition, all its vertices have even degree.

4. Chinese Postman Problem discovered by Chinese Mathematician Kwan Mei- Ko . Algorithm: step 1 : If graph is Eulerian, return sum of all edge weights. Else do following steps. step 2 : We find all the vertices with odd degree . step 3 : List all possible pairings of odd vertices For n odd vertices total number of pairings possible are, (n-1) * (n-3) * (n -5)... * 1 . step 4 : For each set of pairings, find the shortest path connecting them. step 5 : Find the pairing with minimum shortest path connecting pairs. step 6 : Modify the graph by adding all the edges that have been found in step 5. step 7 : Weight of Chinese Postman Tour is sum of all edges. step 8 : Draw Euler Circuit of the modified graph. This Euler Circuit is Chinese Postman Tour.

5. Chinese Postman problem: a b e f d c 3 1 1 4 1 2 5 6 Illustration:

6. As we see that graph does not contain Eulerian circuit because is has odd degree vertices [a, b, e, f]. First we make all possible pairs of odd degree vertices:[ ae , bf], [ ab , ef ], [ af , eb ] so pairs with min sum of weight are [ ae , bf] : ae = (ac + ce = 3 ), bf = ( bd + df = 2 ) Total : 5 We add edges ac, ce , b d & df to the original graph and create a modified graph. a b e f d c 3 1 1 4 1 2 5 6

7. Solution Graph with adding new edges:ac , ce , bd & df Optimal Chinese postman route is of length : 5 + 23 = 28  Chinese Postman Route : a - b - d - f - d - b - f - e - c - a - c - e - a This route is Euler Circuit of the modified graph . a b e f d c 3 1 1 1 2 1 2 1 1 5 6 4

8. THANK YOU