Lecture 15 - Notes
March 3, 2016
Eulerian Cycles
definition: A Eulerian Cycle contains all the edges in the graph exactly once.
Theorem
A connected indirected graph has an Eulerian cycle if and only if the degree of each vertex is even.
Theorem
A connected (strongly connected) digraph has an Eulerian cycle if and only if the in-degree of each vertex equals its out-degree.
Algorithm
To find the Euclidean cycle in a digraph (enumerate the edges in the cycle), using a greedy process,
- Preprocess the graph and make and in-tree with root $r$, compute $\bar{G}$ (reverse all edges). Then perform BFS to get the tree $T$. This is $O(|E| + |V|)$.
if we write the adjacency list for the graph,
When we perform the algorithm, we'll get the list,
Why does it work? This works because, since, $G$ is Eulerian the algorithm ends at $r$. Imagine that $(v,w)$ is missing . Since the algorithm terminated $v \neq r$. Without loss of generality we can assume that $(v,w) \in T$. Since $C - P$ is balanced (where $P$ is the cycle found) there is an edge $(u,v)$ also not in $P$. Without loss of generality $(u,v) \in T$. Continuing in this manner we get a sequence of tree edges which eventually get back to $r$, a contradiction.
This is actually what Frank Rusky wrote on the board. He makes no sense.
Efficiency
We can get all edges in $O(|E| + |V|)$.
Hamiltonian Cycles
Finding all vertices in a Hamiltonian is an $nP$-complete problem.
Planar Graphs
definition: A graph is planar if there is a way to embedded it in the plane (drawn in two dimensions) without crossing edges. The graph embedded in the plane is a plane graph however a graph can be planar without being a plane graph. For example edges could be crossed but it has the potential to be rewritten into a plane graph.
Are Two Graphs Isomorphic?
definition: Two graphs are isomorphic if there is a bijection $\phi: V \to V^\prime$ such that for every edge in $V$,