UCT Algorithm Circle: Eulerian Paths and Topological Sort

UCT Algorithm Circle: Eulerian Paths and Topological Sort Henk Joubert 1 September 2011 Henk Joubert Eulerian Paths Outline Henk Joubert Eulerian Paths Seven bridges of K onigsberg Can you nd a walk around the city that crosses each bridge exactly once? Henk Joubert Eulerian Paths Seven bridges of K onigsberg Euler proved that there is no valid solution to this problem. A walk that crosses every bridge exactly once is called an Eulerian path, and one that ends at the

same place it began is an Eulerian Circuit. There is a nice short-cut that tells us if such a walk is possible! Henk Joubert Eulerian Paths Seven bridges of K onigsberg It’s clear that this is a graph problem. Notice that each vertex has odd degree, that is an odd number of edges connected to it. In fact for an Eulerian path to exist there must be exactly 0 or 2 vertices of odd degree! For an Eulerian circuit to exist there must be no vertices of odd degree. It is assumed that the graph is connected. Henk Joubert Eulerian Paths Seven bridges of K onigsberg It’s clear that this is a graph problem. Notice that each vertex has odd degree, that is an odd number of edges connected to it. In fact for an Eulerian path to exist there must be exactly 0 or 2 vertices of odd degree! For an Eulerian circuit to exist there must be no vertices of odd degree. It is assumed that the graph is connected. Henk Joubert Eulerian Paths Seven bridges of K onigsberg It’s clear that this is a graph problem. Notice that each vertex has odd degree, that is an odd number of edges connected to it. In fact for an Eulerian path to exist there must be exactly 0 or 2 vertices of odd degree! For an Eulerian circuit to exist there must be no vertices of odd degree. It is assumed that the graph is connected. Henk Joubert Eulerian Paths Great! So if we know a path exists, how do we nd one? Fleury’s algorithm is a simple solution to nding Eulerian paths in O(jEj2) time. Hierholzer’s algorithm nds an Euler cycle in O(jEj) time. Representing the graph using an adjacency list allows the basic operations to be completed in constant time. Henk Joubert Eulerian Paths Fleury’s algorithm 1 Start at a vertex of odd degree if 2 exist, otherwise an arbitrary vertex, in a connected graph 2 Follow an edge which if removed would not disconnect the graph, unless there is no choice, then delete that edge. This algorithm will remove all the edges in the order of an Eulerian path (circuit) An alternative to checking if an edge if removed would disconnect the graph (called a bridge in graph theory) is to recursively consider the number of neighbours each node has. Henk Joubert Eulerian Paths Hierholzer’s algorithm...

Website: algorithm.cs.uct.ac.za | Filesize: -
No of Page(s): 15
Download UCT Algorithm Circle: Eulerian Paths and Topological Sort.pdf