Chapter 6: Graphs and Trees (Part 2)

Euler Path:

}   Let G be a graph, and let a and b be two distinct vertices of G. An Euler Path from a to b is a sequence of adjacent edges and vertices that starts at a, ends at b, passes through every vertex of G at least once, and traverses every edge of G exactly once.

}   Let G be a graph, and let a and b be two distinct vertices of G. There is an Euler path if and only if G is connected, a and b have odd degree, and all other vertices of G have positive even degree.

Fleury Algorithm:

Fleury's algorithm works by simply constructing a path, starting at an arbitrary vertex (or at an odd one if there are any) and picking any of its incident edges, with a single caveat: any edge is permissible but those that leave the remaining graph disconnected. (For a connected graph, an edge whose removal affects the connectivity of the graph is called a bridge.)

Practice: http://www.cut-the-knot.org/Curriculum/Combinatorics/FleuryAlgorithm.shtml

 

Euler Circuit:

}   Let G be a graph. An Euler Circuit for G is a circuit that have every of its vertices and edges of G, a sequence of adjacent vertices and edges in G that has at least one edge, starts and ends at the same vertex, uses every vertex of G at least once, and uses every edge of G exactly once.

}   If the graph G is connected and every vertex of the graph has positive even degrees, then G is a Euler circuit. If some vertex of a graph has odd degree, then the graph does not have Euler Circuit.

Algorithm

Suppose that G is any connected graph and suppose that every vertex of G is a positive even integer. [We must find an Euler circuit for G.] Construct a circuit C by the following algorithm:

Step 1: Pick any vertex v of G at which to start.

[This step can be accomplished because the vertex set of G is nonempty by assumption.]

Step 2: Pick any sequence of adjacent vertices and edges, starting and ending at v and never repeating an edge. Call the resulting circuit C.

[This step can be performed for the following reasons: Since the degree of each vertex of G is a positive even integer, as each vertex of G is entered by traveling on one edge, either the vertex is v itself and there is no other unused edge adjacent to v, or the vertex can be exited by traveling on another previously unused edge. Since the number of edges of the graph is finite (by definition of graph), the sequence of distinct edges cannot go on forever. The sequence can eventually return to v because the degree of v is a positive even integer, and so if an edge connects v to another vertex, there must be a different edge that connects back to v.]

Step 3: Check whether C contains every edge and vertex of G. If so, C is an Euler circuit, and we are finished. If not, perform the following steps.

Step 3a: Remove all edges of C from G and also any vertices that become isolated when the edges of C are removed. Call the resulting

subgraph G’.

[Note that G’ may not be connected (as illustrated in Figure 10.2.4), but every vertex of G’ has positive, even degree (since removing the edges of C removes an even number of edges from each vertex, the difference of two even integers is even, and isolated vertices with degree 0 were removed.)]

Step 3b: Pick any vertex w common to both C and G’

[There must be at least one such vertex since G is connected.]

Step 3c: Pick any sequence of adjacent vertices and edges of G’, starting and ending at w and never repeating an edge. Call the resulting circuit C’’.

[This can be done since each vertex of G’ has positive, even degree and G’ is finite.]

Euler Circuit vs Euler Path

	Euler Circuit	Euler Path
Start/end point	Starts and ends at the same vertex	Start at vertex a but ends at vertex b
Degrees	All vertices contains even degree	At most two vertices that contain odd degree.
Pattern	Circular pattern	The pattern may disconnected between the starting and ending point

Watch here: http://www.youtube.com/watch?v=REfC1-igKHQ

Hamilton Path:

}   Given a Graph G , a Hamilton Path for G is a graph that consists of every vertices of G, starts at vertex a, ends at vertex b, following a sequence of adjacent vertices and distinct edges in which every vertex of G appears exactly one,

Hamilton Circuit:

}   Given a Graph G , a Hamilton Circuit for G is a graph that includes every vertices of G. That is, a Hamilton Circuit for G is a sequence of adjacent vertices and distinct edges in which every vertex of G appears exactly one, except for the first and the last vertex, which are the same.

If a graph G has a Hamiltonian circuit, then G has a subgraph H with the following

properties:

1. H contains every vertex of G.

2. H is connected.

3. H has the same number of edges as vertices.

4. Every vertex of H has degree 2.

Euler Circuit vs Euler Path

	Hamilton Circuit	Hamilton Path
Start/end point	Starts and ends at the same vertex	Start at vertex a but ends at vertex b
Pattern	Circular pattern	The pattern is disconnected between the starting and ending point