A circuit
- every edge of
appears only once in the circuit - only graphs with one component can contain such a circuit
A connected graph
An Eulerian trail is an open trail
Königsberg Bridge Problem
The city of Königsberg, located in Prussia was separated by a river in 4 land areas, to travel between these areas 7 bridges were built, some citizens wondered whether it was possible to go for a walk in Königsberg and pass over each bridge exactly once
In graph theory terms the problem can be stated as follows
Does the multigraph
of order and size contain an Eulerian circuit or an Eulerian trail?
Suppose that such a journey is possible then it must begin at some land area and end at some land area (possibly the same one), certainly each land area must appear in the trail, note that at least two vertices of
Each of the
Going back to the Königsberg bridge problem we can see that it’s impossible to find a trail because all the vertices have an odd degree
- The length of the eulerian circuit/trail of a graph
is equal to where is the size of
For undirected graphs
- A graph
is an Eulerian graph if and only if every vertex of has even degree - A graph
contains an Eulerian trail if and only if exactly 2 vertices of have odd degree, also each trail of begins at one of these vertices and ends at the other
For directed graphs
- A graph
is an Eulerian graph if and only if every vertex of has the same incoming degree and outgoing degree values and it’s strongly connected - A graph
contains an Eulerian trail if and only if for each vertex the difference between its incoming degrees and outgoing degrees is 0 except for 2 vertices whose difference is (start) and (end), if those edges are connected by an edge then the graph is strongly connected
Hierholzer’s algorithm
Let
- identify a circuit
in , mark the edges of - if
contains all the edges of then stop - otherwise let
be a node on that is incident with an unmarked edge - build a circuit
starting at node and using edge , mark the edges of - join the circuit
to by inserting the edges of into at position , move to step 2
Implementation notes
In the implementation a source vertex
// each edge is saved by id, helper to avoid the traversal
// of an edge many times
vector<bool> edge_used;
// the number of edges used in the adjacency list of the vertex `i`
vector<int> edge_pointer;
// the eulerian trail
vector<int> trail;
// the adjacency list representation of `g`, each element `g_{i,j}` is
// a tuple (to, id) which denotes an edge `(i, to)` with id `id`
vector<vector<pair<int, int> > > g;
void dfs(int v) {
for (; edge_pointer[v] < g[v].size(); edge_pointer[v] += 1) {
pair<int, int> &edge = g[v][edge_pointer[v]];
if (edge_used[edge.second]) {
// if the edge was already used analyze the next one
continue;
}
// mark the edge
edge_used[edge.second] = true;
dfs(edge.first);
}
trail.push_back(v);
}
/**
* Computes an euler trail if possible in an undirected graph `G`
* whose `edges` are given as an input
*
* NOTE: The trail if it exists is saved on the global `trail`
*
* @param {int} n The order of the graph
* @param {vector<pair<int, int> >} A collection of tuples
* denoting the indexes of the vertices the edge `i` is incident to
* @return {bool} True if the graph has an euler trail
*/
bool euler_trail_undirected(int n, vector<pair<int, int> > &edges) {
int m = edges.size();
g.assign(n, vector<pair<int, int> > ());
edge_pointer.assign(n, 0);
edge_used.assign(m, 0);
vector<int> deg(n, 0);
// build the adjacency list of the graph
for (int i = 0; i < m; i += 1) {
int u = edges[i].first;
int v = edges[i].second;
g[u].push_back({ v, i });
g[v].push_back({ u, i });
deg[u] += 1;
deg[v] += 1;
}
// find an odd vertex
int start = 0;
int odd_degree_count = 0;
for (int i = 0; i < n; i += 1) {
if (deg[i] % 2 != 0) {
++odd_degree_count;
start = i;
}
}
if (odd_degree_count == 2 || odd_degree_count == 0) {
dfs(start);
return trail.size() == m + 1;
}
return false;
}
/**
* Computes an euler trail if possible in an directed graph `G`
* whose `edges` are given as an input
*
* NOTE: The trail if it exists is saved on the global `trail`
*
* @param {int} n The order of the graph
* @param {vector<pair<int, int> >} A collection of tuples
* denoting the indexes of the vertices the edge `i` is incident to
* @return {bool} True if the graph has an euler trail
*/
bool euler_trail_directed(int n, vector<pair<int, int> > &edges) {
int m = edges.size();
g.assign(n, vector<pair<int, int> > ());
edge_pointer.assign(n, 0);
edge_used.assign(m, 0);
vector<int> in_deg(n, 0), out_deg(n, 0);
// build the adjacency list of the graph
for (int i = 0; i < m; i += 1) {
int u = edges[i].first;
int v = edges[i].second;
g[u].push_back({ v, i });
out_deg[u] += 1;
in_deg[v] += 1;
}
// find an odd vertex
int start = 0;
int odd_degree_count = 0;
for (int i = 0; i < n; i += 1) {
if (in_deg[i] - out_deg[i] != 0) {
++odd_degree_count;
if (out_deg[i] > in_deg[i]) {
start = i;
}
}
}
if (odd_degree_count == 2 || odd_degree_count == 0) {
dfs(start);
return trail.size() == m + 1;
}
return false;
}