Euler: edges matter.html (4267B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-0.5295528173446655"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:30:09 +0000"/><meta name="latitude" content="52.33449063255681"/><meta name="longitude" content="4.866731888842327"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 22:17:20 +0000"/><title>Euler: edges matter</title></head><body><div>mnemonic: <span style="text-decoration: underline;">E</span>uler starts with <span style="text-decoration: underline;">E</span>, so <span style="text-decoration: underline;">e</span>dges matter.</div><div><br/></div><div>Euler tour</div><ul><li><div>traverses <span style="text-decoration: underline;">each</span> edge exactly once, start=end</div></li><li><div>A connected graph has Euler tour iff all vertices have even degrees</div></li><li><div>Fleury’s algorithm for Euler tour:</div></li><ol><li><div>Trail P consists of single vertex u</div></li><li><div>While E(P) ≠ E(G) do:</div></li><ol><li><div>Let v be last vertex added to P</div></li><li><div>choose an edge <v,w> in (G-E(P)).</div></li><ul><li><div><v,w> is only allowed to be a cut edge if there is no other option.</div></li></ul><li><div>add it to P</div></li></ol></ol><li><div>Hierholzer’s algorithm for Euler tour</div></li><ul><li><div>First, find a closed trail from some vertex</div></li><li><div>for each vertex <span style="font-style: italic;">u</span> that has adjacent edges that are not part of the trail, find a closed trail on that vertex (starting and ending in <span style="font-style: italic;">u</span>), then add the trail to the tour</div></li><li><div><a href="https://www.youtube.com/watch?v=3k5_oooad8U">surreal video explaining this</a></div></li></ul></ul><div><br/></div><div>Euler trail</div><ul><li><div>traverses <span style="text-decoration: underline;">each</span> edge exactly once, but is open</div></li><li><div>connected graph G has Euler trail iff it has exactly 2 vertices of odd degree</div></li></ul><div><br/></div><div>Chinese postman problem (also, Bridges of Konigsberg)</div><ul><li><div>problem:</div></li><ul><li><div>in weighted graph, each edge has real-valued weight</div></li><li><div>all edges are passed <span style="text-decoration: underline;">at least</span> once, total travelled dist is minimal</div></li><li><div>find closed walk of minimal length</div></li></ul><li><div>Solution:</div></li><ul><li><div>let G be connected, weighted graph</div></li><li><div>Let v<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">1</span>, …, v<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">2k</span> be odd degree vertices in G</div></li><li><div>Algorithm:</div></li><ol><li><div>For each pair of distinct odd-degree vertices v<span style="vertical-align: sub;">i</span> and v<span style="vertical-align: sub;">j</span>, find minimum-weight path P<span style="vertical-align: sub;">ij</span></div></li><li><div>Construct weighted complete graph on 2k vertices in which vertex v<span style="vertical-align: sub;">i</span> and v<span style="vertical-align: sub;">j</span> are joined by an edge having weight w(P<span style="vertical-align: sub;">ij</span>)</div></li><li><div>Find set E of k edges {e<span style="vertical-align: sub;">1</span>, …, e<span style="vertical-align: sub;">k</span>} such that:</div></li><ul><li><div>the sum of their weights is minimal</div></li><li><div>no two edges are incident on same vertex</div></li></ul><li><div>For each edge e ∈ E, with e=<v<span style="vertical-align: sub;">i</span>, v<span style="vertical-align: sub;">j</span>>, duplicate edges of P<span style="vertical-align: sub;">i,j</span> in graph G</div></li><li><div>Find Euler tour in resulting graph</div></li></ol></ul></ul><div><br/></div></body></html>