Euler_ edges matter.md (1932B)
1 +++ 2 title = 'Euler: edges matter' 3 +++ 4 # Euler: edges matter 5 mnemonic: Euler starts with E, so edges matter. 6 7 Euler tour 8 9 - traverses each edge exactly once, start=end 10 - A connected graph has Euler tour iff all vertices have even degrees 11 - Fleury’s algorithm for Euler tour: 12 13 1. Trail P consists of single vertex u 14 2. While E(P) ≠ E(G) do: 15 1. Let v be last vertex added to P 16 2. choose an edge <v,w> in (G-E(P)). 17 18 - <v,w> is only allowed to be a cut edge if there is no other option. 19 20 3. add it to P 21 22 - Hierholzer’s algorithm for Euler tour 23 - First, find a closed trail from some vertex 24 - for each vertex *u* that has adjacent edges that are not part of the trail, find a closed trail on that vertex (starting and ending in *u*), then add the trail to the tour 25 - [surreal video explaining this](https://www.youtube.com/watch?v=3k5_oooad8U) 26 27 Euler trail 28 29 - traverses each edge exactly once, but is open 30 - connected graph G has Euler trail iff it has exactly 2 vertices of odd degree 31 32 Chinese postman problem (also, Bridges of Konigsberg) 33 34 - problem: 35 - in weighted graph, each edge has real-valued weight 36 - all edges are passed at least once, total travelled dist is minimal 37 - find closed walk of minimal length 38 - Solution: 39 - let G be connected, weighted graph 40 - Let v1, …, v2k be odd degree vertices in G 41 - Algorithm: 42 43 1. For each pair of distinct odd-degree vertices vi and vj, find minimum-weight path Pij 44 45 2. Construct weighted complete graph on 2k vertices in which vertex vi and vj are joined by an edge having weight w(Pij) 46 47 3. Find set E of k edges {e1, …, ek} such that: 48 49 - the sum of their weights is minimal 50 - no two edges are incident on same vertex 51 52 4. For each edge e ∈ E, with e=<vi, vj>, duplicate edges of Pi,j in graph G 53 54 5. Find Euler tour in resulting graph