Saturday, 2 January 2016

Hamilton circuits and Hamilton paths

Hamilton path: a path that passes through every vertex in a graph exactly once.
Hamilton circuit: a circuit that passes through every vertex in a graph exactly once (except for the vertex that is both the start and end, which is visited twice).
Theorem 1: A complete graph Kn has a Hamilton circuit for n≥3.
Theorem 2: If G is a connected simple graph with n vertices, where n≥3, then G has a Hamilton circuit, if the degree of each vertex is at least n/2.

Using the theorem, we can observe that there are 5 vertices, so n≥3;
Furthermore, each vertex has at least deg(2): therefore, a Hamilton circuit may exist.  One such circuit is: a, c, d, e, b, a

0 comments:

Post a Comment

UGC NET Computer Science

Computer GK App