Data Structures and Analysis (COMP 410) David Stotts Computer Science Department UNC Chapel Hill Graph Theory and Algorithms (part 4) 7 Bridges of Konigsberg
Popular 1600s 1700s pastime can you walk through the city and cross each bridge exactly once (either direction)? Present day Kaliningra d, Russia
red bridges are no longer there Leonard Euler in 1735 Created an abstraction of this problem and laid the groundwork for graph theory (and also topology) Represented land masses as vertices
Represented bridges as connecting lines (edges) Eulers original description Eulers Graph Model We model the city with an undirected graph,
because we can walk across the bridge in either direction The problem Can a person execute a walk that crosses each bridge once and only once? You can start anywhere and end up anywhere Informal:
Put a pen on a vertex. Can you trace the diagram without picking up the pen, or redrawing an edge? Euler Path, Circuit Euler Path (EP): A path in the graph that passes through every edge once Euler Circuit (EC): An EP that begins and ends on the same vertex Degree of a vertex v: #edges involving v
The question: does G have any EP or EC ? To answer: first compute the degree of every vertex in G Euler Theorems Given connected undirected G=(V,E) Theorem 1: EC If G has any odd vertices then it has no EC. If G has all even vertices then there is at least one EC. Theorem 2: EP If G has more than 2 odd vertices, then it has no EP.
If G has exactly 2 odd vertices, then it has at least one EP, which must start at one odd vertex and end at the other. Theorem 3: General The sum of the degrees of all vertices in G is even ( exactly twice |E| ). The number of odd vertices is even. Euler Theorems #odd v implication -------------------------------------0 >=1 EC (no EP that is not EC)
1 impossible (th.3) 2 no EC, >=1 EP every EP must start on one odd and end on the other >2
no EC, no EP Examples 2 odd no EC at least 1 EP 2 3 3
4 4 3 3 4 4 3 3
4 odd no EP (so no EC) 2 4 4 they start, end here 4 4
2 4 0 odd at least 1 EC Euler Path, Circuit Memory aid: G has an EC iff #odd vertices = 0 G has an EP iff #odd vertices = 2 (EP means that is not EC)
There is an algorithm to find EC in a graph that is worst case O( |E|+|V| ) Algorithm for EP/EC Given undirected unweighted G=(V,E) 1) Start with empty tmp stack, empty EC stack If 0 odd nodes pick any as cn, the curr node else if 2 odd nodes pick one odd as cn, the curr node else no EP/EC: end 2) If cn has no neighbors: push cn to EC stack
cn = pop tmp stack Else // cn has neighbors push cn to tmp stack pick any neighbor nb of cn remove edge (cn,nb) make nb the new cn 3) Repeat step 2 until cn has no neighbors and tmp stack is empty Euler and Topology Inventing graphs allowed Euler to
begin defining what we now know as topology This is a cube (3D) stretched flattened to 2D The graph allows us to study some properties of the cube Every convex polyhedron can be projected into 2D as a connected planar graph
Euler and Topology Can a bug crawl along all edges of the cube without crossing any twice? No, tough luck for the bug ! 3 3 Sounds like EP in 3-space 3 3 3
So maybe we can do EP on the flattened graph 3 compute degree of all vertices #odd vertices = 8 3 3 no EC (needs 0 odds)
no EP (needs exactly 2 odds) Hamiltonian Path, Cycle Given undirected connected graph G=(V,E) Hamiltonian Path (HP): path in G that contains each vertex once Hamiltonian Circuit (HC): a HP with endpoints that are adjacent HC: 1, 2, 3, 4, 5, 1 1 2
HP: 1, 2, 3, 4, 5 3 5 4 HC: 2, 3, 4, 5, 1, 2 HC: 2, 3, 4, 1, 5, 2 HP: 1, 5, 2, 4, 3
HP: 2, 5, 1, 4, 3 Another Example 1 5 3 2 4
HC: none HP: 5 HP: 5 HP: 3 HP: etc. 1, 2, 3, 4, 1, 4, 3, 2, 1, 4, 5, 2,
3, 2, 5, 4, 1 Hamiltonian vs. Eulerian Memory aid: To remember which does edges, and which does vertices Euler Edge The Icosian Game Invented by Sir William Rowan Hamilton in 1857 Sold as a physical board game
Put pegs in the holes in number order to define a path that uses each peg exactly once, and ends where it starts From Icosian Game Planar graph,
a flattened dodecahedron There is a HC for this graph From Wordplay, the NYT crossword blog By Christoph Sommer - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1724516 Platonic Solids We said earlier that
any convex polyhedron will project down to a connected planar graph The 5 platonic solids produce graphs that are Hamiltonian, i.e. have an HC From http://www.korthalsaltes.com/ No Nice Theorems like Euler We saw an O(|V|+|E|) algorithm for EP/EC HP/HC is not nearly so easy for some strange
reason Dirac 1952 (sufficient condition) A simple graph G (no loops, no multi-edges) with N vertices is Hamiltonian if degree of each vertex is >= N/2. does NOT say if G is Hamiltonian, then the vertex degrees are >= N/ 2 Ore 1960 (sufficient condition) A graph G with N vertices is Hamiltonian if for every pair of non-adjacent vertices the
sum of their Existence proofs, not degrees is >=N. constructive Same for Eulers Theorems Efficiency: P vs. NP No known efficient algorithm for finding HP/HC So EP/EC is linear O(|V|+|E|) worst case But HP/HC is exponential on some data Efficient means polynomial
Bubble Sort? O(N^2) we said its horrible, but its polynomial HP/HC exponential is way worse Note: We have not proven that HP/HC is not polynomial We have not yet found a polynomial time algorithm All known algorithms are exponential time worst case Efficiency: P vs. NP Note: If we are given a path/circuit, we can easily (in polynomial time) check if it is a HP/HC for
a graph See the difference: 1) 2) 3) Y/N decision Does this G have an HC? procedure Checking, verify Given this path P in G, is it a HC? Constructive Find a HC for G Travelling Salesman Problem
https:// en.wikipedia.org/wiki/Travelling_salesman_p roblem Computes a Hamiltonian Path (or circuit) on a graph
No known efficient (polynomial time) algorithm for solving this Known algorithms are exponential (nonpolynomial) in the size of the graph (#nodes + #edges) END
