- A GRAPH is a relational structure made up of vertices and edges. The edges of a graph express the relationships among the vertices.
- An edge that connects a vertex to itself is a LOOP.
- Two vertices are ADJACENT if there is an edge joining them. (If a vertex has a loop, the vertex is adjacent to itself.)
- The DEGREE of a vertex is the total number of edges at that vertex. (A loop adds 2 to the degree of a vertex.)
- A vertex with degree 0 is an ISOLATED vertex.
- A PATH in a graph is a route among vertices along the graph’s edges such that no edge is used more than once. (Paths are specified by listing adjacent vertices from the beginning of the path to the end of the path.)
- A path that starts and ends at the same vertex is called a CIRCUIT.
- A graph is CONNECTED if any two of its vertices can be joined by a path. A graph that is not connected is DISCONNECTED. The resulting ‘pieces’ of a disconnected graph are called COMPONENTS of the graph.
- If erasing an edge of a connected graph would cause the graph to be disconnected, that edge is called a BRIDGE.
- A path that contains every edge of a connected graph exactly once is called an EULER PATH.
- An Euler path that starts and ends at the same vertex is called an EULER CIRCUIT.
Keep in mind:
- An Euler Circuit IS a type of Euler Path but an Euler Path is not necessarily an Euler Circuit.
- The sum of the degrees of all the vertices of a graph is twice the number of edges.
- The number of vertices of odd degree must be even.
- Summary of what the number of odd vertices in a CONNECTED
graph tells you about the existence of Euler paths and Euler circuits. (Remember: If there
is a circuit, there is a path--since a circuit IS a type of path!)
# of ODD Vertices
Implication (for a connected graph)
0
There is at least
one Euler Circuit.1
THIS IS IMPOSSIBLE!
(Try it yourself.)2
There is no Euler Circuit but at least 1 Euler Path.
more than 2
There are no Euler Circuits or Euler Paths.
Is there an easy way to find an Euler circuit?
(Remember, only connected graphs with no vertices of odd
degree have Euler circuits.)
In most cases, Euler circuits can be found easily by just using a couple of commonsense
guidelines:
- Always leave one edge available to get back to the starting vertex as the last step.
- Don't use an edge to go to a vertex unless there is another edge available to leave that vertex (except for the last step).
However, there is an algorithm which, if followed, is guaranteed to produce an Euler circuit in a connected graph with no vertices of odd degree:
Fleury’s algorithm (for a connected graph with no vertices of odd degree):
- Pick any vertex as a starting point.
- Marking your path as you move from vertex to vertex, travel along any edges you wish except, DO NOT travel along an edge that is a bridge for the graph formed by the EDGES THAT HAVE YET TO BE TRAVELED-- unless you have to.
- Continue until you return to your starting point.
THE PATH PRODUCED BY FLEURY’S ALGORITHM IS ALWAYS AN EULER CIRCUIT.
Modification of Fleury’s Algorithm to find Euler
Paths when no Euler Circuits exist
(for connected graphs with exactly 2 odd vertices).
Fleury’s Algorithm can be modified slightly to find
Euler Paths when no Euler Circuits exist.
Remember this only happens for a connected graph with exactly 2 vertices of odd degree.
Use Fleury’s Algorithm just as stated above EXCEPT always start at one of the odd vertices.
THE PATH PRODUCED BY THIS MODIFICATION OF FLEURY’S ALGORITHM IS ALWAYS AN EULER PATH.
Eulerizing a graph
The process of adding duplicate edges to a graph so that the resulting graph has no
vertices of odd dgree (and thus does have an Euler circuit.
Notes about Eulerization of a graph
- The duplicate edges added to the Eulerized graph can be thought of as actual new edges but in many contexts, the new edges of the Eulerized graph just represent a retracing of the same edge in the original graph.
- Eulerization involves only involves adding edges which duplicate existing edges. You cannot add "new" edges; that is, edges which do not duplicate edges already in the graph.
- Always Eulerize a graph using the fewest edges possible.
- The duplicate edges added to a graph during the process of Eulerization are often called DEADHEAD EDGES.
Semi-Eulerizing a graph
The process of adding duplicate edges to a graph so that the resulting graph
has exactly 2 vertices of odd degree (and thus does have an Euler Path but not an Euler
Circuit).
(The only difference between SEMI-EULERIZATION and EULERIZATION is that the former (semi) results in an Euler Path--with different starting and ending points--while the latter results in an Euler Circuit--with the same starting and ending point.)
Line Drawings
A LINE DRAWING is the name often given to a graph in which the vertices are not shown (the
edges just connect directly) and the edges are all line segments.
For all practical purposes, you can just think of a line drawing as a graph whose vertices are so small that you can't see them.
A line drawing has a UNICURSAL TRACING if it can be traced without lifting the pencil or retracing any line.
A unicursal tracing is CLOSED if the tracing
starts and ends at the same point.
A line drawing has a closed unicursal tracing if and only if it has no points of
intersection of odd degree.
A unicursal tracing is OPEN if the tracing
starts and ends at different points.
A line drawing has an open unicursal tracing if and only if it has exactly two
points of intersection of odd degree.