EULERIAN CYCLE
Before I started working on the project and almost up until now, I was not sure what the exact definition
of an Eulerian Cycle is. However, now I am positive that an Eulerian Cycle is an Eulerian
Trail that starts and ends on the same vertex. And an Eulerian Trail is a walk on the
edges of the graph that uses each edge exactly once. According to the theorem, a graph contains an
Eulerian Trail if and only if it contains no more than 2 vertices of odd degree, while the graph
contains an Eulerian Cycle if and only if it contains no vertices of odd degree. An intuitive
reason for this is the following: in an Eulerian Trail we need to enter and exit all the
vertices except for the beginning and ending ones, which implies that at most two of the
vertices (the beginning and the ending ones) can have an odd degree, while all others must
have an even degree; in the case of an Eulerian Cycle, since we start and end on
the same vertex, all of the vertices must have an even degree in order for us to be able to both enter
and exit each one of them.
Below is the applet I wrote for one of the bonus projects that outputs an Eulerian Cycle of the graph
the user draws, if one exists, or tells the user that the graph does not contain an Eulerian Cycle
for a certain reason.
Clearly, an Eulerian Cycle does not exist if any of the vertices has an odd degree, so that is one of
the first checks I perform. Another important check is whether the graph is connected or not, since
an Eulerian Cycle can only exist in a connected graph. Additionally, if the graph is empty,
I make sure that Java does not crash due to a NullPointerException.
The algorithm I used for finding an Eulerian Cycle, if one exists, is rather easy. Since all of the
vertices have an even degree in a graph that contains an Eulerian Cycle, any vertex can be chosen
to be the starting one. After choosing the starting vertex, I look for a cycle that starts and ends on that
vertex, and use it as the main part of my Eulerian Cycle. Then I choose one of the vertices of that
cycle to be the next starting point and try to find a cycle that starts and ends on that vertex and contains
the unvisited edges. I keep doing that until all the edges are visited. By the end of the
looping through all the vertices and edges, I find an Eulerian Cycle in the form of the collection
of vertices in a particular order.
Here is how to use the applet:
-
To draw a vertex -- double click on the applet.
-
To draw an edge -- select a starting vertex by clicking on it, and drag the mouse to the ending vertex.
-
Once the graph is drawn, click on an Output an Eulerian Cycle button.
-
The arrows on the edges, as well as the labels, show the direction of the Eulerian Cycle,
while the starting point is also marked red.
-
To continue drawing and extending the graph -- click on a Back to Drawing Graph button.
One of the assumptions I made was that a graph that contains a single vertex does not
contain an Eulerian Cycle since it does not contain any edges.
|
|
|