22-3 Euler tour

An Euler tour of a strongly connected, directed graph \(G = (V, E)\) is a cycle that traverses each edge of \(G\) exactly once, although it may visit a vertex more than once.

a. Show that \(G\) has an Euler tour if and only if \(\text{in-degree}(v) = \text{out-degree}(v)\) for each vertex \(v \in V\).

b. Describe an \(O(E)\)-time algorithm to find an Euler tour of \(G\) if one exists. (\(\textit{Hint:}\) Merge edge-disjoint cycles.)

a. First, we'll show that it is necessary to have in degree equal out degree for each vertex. Suppose that there was some vertex v for which the two were not equal, suppose that \(\text{in-degree}(v) - \text{out-degree}(v)\). Note that we may assume that in degree is greater because otherwise we would just look at the transpose graph in which we traverse the cycle backwards. If \(v\) is the start of the cycle as it is listed, just shift the starting and ending vertex to any other one on the cycle. Then, in whatever cycle we take going though \(v\), we must pass through \(v\) some number of times, in particular, after we pass through it a times, the number of unused edges coming out of \(v\) is zero, however, there are still unused edges goin in that we need to use. This means that there is no hope of using those while still being a tour, becase we would never be able to escape \(v\) and get back to the vertex where the tour started. Now, we show that it is sufficient to have the in degree and out degree equal for every vertex. To do this, we will generalize the problem slightly so that it is more amenable to an inductive approach. That is, we will show that for every graph \(G\) that has two vertices \(v\) and \(u\) so that all the vertices have the same in and out degree except that the indegree is one greater for \(u\) and the out degree is one greater for \(v\), then there is an Euler path from \(v\) to \(u\). This clearly lines up with the original statement if we pick \(u = v\) to be any vertex in the graph. We now perform induction on the number of edges. If there is only a single edge, then taking just that edge is an Euler tour. Then, suppose that we start at \(v\) and take any edge coming out of it. Consider the graph that is obtained from removing that edge, it inductively contains an Euler tour that we can just post-pend to the edge that we took to get out of \(v\).

b. To actually get the Euler circuit, we can just arbitrarily walk any way that we want so long as we don't repeat an edge, we will necessarily end up with a valid Euler tour. This is implemented in the following algorithm, \(\text{EULER-TOUR}(G)\) which takes time \(O(|E|)\). It has this runtime because the for loop will get run for every edge, and takes a constant amount of time. Also, the process of initializing each edge's color will take time proportional to the number of edges.

1
2
3
4
5
6
7
8

EULER-TOUR(G)
    color all edges WHITE
    let (v, u) be any edge
    let L be a list containing v
    while there is some WHITE edge (v, w) coming out of v
        color (v, w) BLACK
        v = w
        append v to L

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用