ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Euler graph

•Download as PPTX, PDF•
•
A
AAQIB PARREY

The document discusses graphs and Eulerian circuits and paths. It defines what a graph is composed of and defines an Eulerian circuit and path. It states that a graph must be connected and have all vertices visited once for an Eulerian circuit, or have two odd vertices for an Eulerian path. Fleury's algorithm is described for finding an Euler circuit or path by traversing edges without crossing bridges twice. The algorithm works by choosing the next edge such that bridges are only crossed if necessary. Examples are given to demonstrate the algorithm. Applications mentioned include the Chinese postman problem and communicating networks.

1 of 22
Downloaded 82 times
EULER GRAPH PRESENTED : AAQIB ASHRAF PARREY
Graphs consist of  points called vertices  lines called edges 1. Edges connect two vertices. 2. Edges only intersect at vertices. 3. Edges joining a vertex to itself are called loops. The following picture is a graph. A B C D E
EULER GRAPH • A graph is called Eulerian if it has an Eulerian Cycle and called Semi-Eulerian if it has an Eulerian Path. An Eulerian cycle (path) is a sub_graph Ge = (V;Ee) of G = (V;E) which passes exactly once through each edge of G. G must thus be connected and all vertices V are visited (perhaps more than once). We then says that G is Eulerian
Euler Circuit and Euler path • When a graph has no vertices of odd degree, then it has at least one Euler circuit. • When a graph has exactly two vertices of odd degree, then it has at least one Euler path. • When a graph has more than two vertices of odd degree, then – There is no Euler circuit or Euler path – There is no possible way that we can travel along all the edges of the graph without having to cross some of them more than once.
Euler circuit & Euler path • How we will find a route that covers all the edges of the graph while revisiting the least possible number of edges (deadhead travel)? • In real-world problems, The cost is proportional to the amount of travel. • Total cost of a route = cost of traveling original edges in the graph + cost of deadhead travel
The bridges of Konigsberg problem Seven bridges of Konigsberg problem, was first solved by Euler in the eighteenth century. The problem was rather simple. The town of Konigsberg consists of two islands and seven bridges. Is it possible, by beginning anywhere and ending anywhere, to walk through the town by crossing all seven bridges but not crossing any bridge twice?
Eulerizing a graph • Modifying a graph by adding extra edges in such a way that the odd vertices become even vertices. • The process of changing a graph by adding additional edges so that odd vertices are eliminated is called Eulerizing the graph. • Note: The edges that we add must be duplicates of edges that already exist. The idea is to cover the edges of the original graph in the best possible way without creating any new.
Eulerizing Graphs First step is to identify the odd vertices. Second step is to add duplicate copies of edges to create all even vertices OPTIMAL ROUTE: duplicate the fewest number of edges NOT an optimal route illegal route
Semi- eularization of the graph • We are not required to start and end at the same vertex. • We duplicate as many edges as needed to eliminate all odd vertices except for two, which we allow to remain odd. • We then use one of the odd vertices as the starting point and we will end up to the other odd vertex.
Semi-Eulerizing Graphs First step is to identify the odd vertices. Second step is leave out 2 odd vertices and add duplicate copies of edges to create even vertices OPTIMAL ROUTE: duplicate the fewest number of edges NOT an optimal route illegal route
Fleury’s Algorithm • Finds an Euler circuit in a connected graph with no odd vertices. • Finds an Euler path in a connected graph with two odd vertices. • The idea behind the algorithm: Don’t burn your bridges behind you. A B Bridge We would only want to cross that bridge if we know that all edges in A have been traveled.
Fleury’s Algorithm • Let G be an Eulerian graph. • STEP 1: Choose any vertex v of G and set current vertex equal to v and current trail equal to the empty sequence of edges. • STEP 2: Select any edge e incident with the current vertex but choosing a bridge only if there is no alternative. • STEP 3: Add e to the current trail and set the current vertex equal to the vertex at the ‘other end’ of e. [If e is a loop, the current vertex will not move.] • STEP 4: Delete e from the graph. Delete any isolated vertices. • Repeat steps 2 – 4 until all edges have been deleted from G. The final current trail is an Eulerian trail in G.
Fleury’s Theorem • Every time we traverse another edge, we erase it from copy 1 but mark (red) and level it with the appropriate number on copy 2. • Copy 1 gets smaller and cop2 gets redder. • Copy 1 helps us decide where to go next; copy 2 helps us reconstruct our trip. Copy 1 A B C D E F B C D E F Copy 2 Start at F (arbitrarily)
Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 1: Travel from F to C Could have also travel from F to D A
Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 2: Travel from C to D Could have also travel to A or to E 1 2 A
Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 3: Travel from D to A Could have also travel to B but not to F – DF is a bridge! 1 2 A 3
Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 4: Travel from A to C Could have also travel to E but not to B – AB is a bridge! 1 2 A 3 4
Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 5: Travel from C to E There is no choice! 1 2 A 3 4 5
Fleury’s Theorem Copy 1 B C D E F Copy 2 Steps 6, 7, 8, and 9: Only one way to go at each step 1 2 A 3 4 5 6 7 8 9
Fleury’s Algorithm for finding Euler circuit • First make sure that the graph is connected and all the vertices have even degree. • Pick any vertex as the stating point • When you have a choice, always choose to travel along an edge that is not a bridge of the yet-to-be- traveled part of the graph • Label the edges in the order in which we travel them • When we cannot travel any more, stop. we are done.
APPLICATIONS • Chinese postman problem • Communicating networks • Tourist guide
Thank you

More Related Content

Euler graph

  • 1. EULER GRAPH PRESENTED : AAQIB ASHRAF PARREY
  • 2. Graphs consist of  points called vertices  lines called edges 1. Edges connect two vertices. 2. Edges only intersect at vertices. 3. Edges joining a vertex to itself are called loops. The following picture is a graph. A B C D E
  • 3. EULER GRAPH • A graph is called Eulerian if it has an Eulerian Cycle and called Semi-Eulerian if it has an Eulerian Path. An Eulerian cycle (path) is a sub_graph Ge = (V;Ee) of G = (V;E) which passes exactly once through each edge of G. G must thus be connected and all vertices V are visited (perhaps more than once). We then says that G is Eulerian
  • 4. Euler Circuit and Euler path • When a graph has no vertices of odd degree, then it has at least one Euler circuit. • When a graph has exactly two vertices of odd degree, then it has at least one Euler path. • When a graph has more than two vertices of odd degree, then – There is no Euler circuit or Euler path – There is no possible way that we can travel along all the edges of the graph without having to cross some of them more than once.
  • 5. Euler circuit & Euler path • How we will find a route that covers all the edges of the graph while revisiting the least possible number of edges (deadhead travel)? • In real-world problems, The cost is proportional to the amount of travel. • Total cost of a route = cost of traveling original edges in the graph + cost of deadhead travel
  • 6. The bridges of Konigsberg problem Seven bridges of Konigsberg problem, was first solved by Euler in the eighteenth century. The problem was rather simple. The town of Konigsberg consists of two islands and seven bridges. Is it possible, by beginning anywhere and ending anywhere, to walk through the town by crossing all seven bridges but not crossing any bridge twice?
  • 7. Eulerizing a graph • Modifying a graph by adding extra edges in such a way that the odd vertices become even vertices. • The process of changing a graph by adding additional edges so that odd vertices are eliminated is called Eulerizing the graph. • Note: The edges that we add must be duplicates of edges that already exist. The idea is to cover the edges of the original graph in the best possible way without creating any new.
  • 8. Eulerizing Graphs First step is to identify the odd vertices. Second step is to add duplicate copies of edges to create all even vertices OPTIMAL ROUTE: duplicate the fewest number of edges NOT an optimal route illegal route
  • 9. Semi- eularization of the graph • We are not required to start and end at the same vertex. • We duplicate as many edges as needed to eliminate all odd vertices except for two, which we allow to remain odd. • We then use one of the odd vertices as the starting point and we will end up to the other odd vertex.
  • 10. Semi-Eulerizing Graphs First step is to identify the odd vertices. Second step is leave out 2 odd vertices and add duplicate copies of edges to create even vertices OPTIMAL ROUTE: duplicate the fewest number of edges NOT an optimal route illegal route
  • 11. Fleury’s Algorithm • Finds an Euler circuit in a connected graph with no odd vertices. • Finds an Euler path in a connected graph with two odd vertices. • The idea behind the algorithm: Don’t burn your bridges behind you. A B Bridge We would only want to cross that bridge if we know that all edges in A have been traveled.
  • 12. Fleury’s Algorithm • Let G be an Eulerian graph. • STEP 1: Choose any vertex v of G and set current vertex equal to v and current trail equal to the empty sequence of edges. • STEP 2: Select any edge e incident with the current vertex but choosing a bridge only if there is no alternative. • STEP 3: Add e to the current trail and set the current vertex equal to the vertex at the ‘other end’ of e. [If e is a loop, the current vertex will not move.] • STEP 4: Delete e from the graph. Delete any isolated vertices. • Repeat steps 2 – 4 until all edges have been deleted from G. The final current trail is an Eulerian trail in G.
  • 13. Fleury’s Theorem • Every time we traverse another edge, we erase it from copy 1 but mark (red) and level it with the appropriate number on copy 2. • Copy 1 gets smaller and cop2 gets redder. • Copy 1 helps us decide where to go next; copy 2 helps us reconstruct our trip. Copy 1 A B C D E F B C D E F Copy 2 Start at F (arbitrarily)
  • 14. Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 1: Travel from F to C Could have also travel from F to D A
  • 15. Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 2: Travel from C to D Could have also travel to A or to E 1 2 A
  • 16. Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 3: Travel from D to A Could have also travel to B but not to F – DF is a bridge! 1 2 A 3
  • 17. Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 4: Travel from A to C Could have also travel to E but not to B – AB is a bridge! 1 2 A 3 4
  • 18. Fleury’s Theorem Copy 1 B C D E F A B C D E F Copy 2 Step 5: Travel from C to E There is no choice! 1 2 A 3 4 5
  • 19. Fleury’s Theorem Copy 1 B C D E F Copy 2 Steps 6, 7, 8, and 9: Only one way to go at each step 1 2 A 3 4 5 6 7 8 9
  • 20. Fleury’s Algorithm for finding Euler circuit • First make sure that the graph is connected and all the vertices have even degree. • Pick any vertex as the stating point • When you have a choice, always choose to travel along an edge that is not a bridge of the yet-to-be- traveled part of the graph • Label the edges in the order in which we travel them • When we cannot travel any more, stop. we are done.
  • 21. APPLICATIONS • Chinese postman problem • Communicating networks • Tourist guide