Graph: Hamiltonian & Coloring: Nitin Upadhyay March 17, 2006
Graph: Hamiltonian & Coloring: Nitin Upadhyay March 17, 2006
Graph: Hamiltonian & Coloring: Nitin Upadhyay March 17, 2006
Coloring
Nitin Upadhyay
March 17, 2006
Hamiltonian Graphs
Hamiltonian Cycle
Solution
Hamiltonian Path
Rules for Constructing
Hamiltonian paths and Cycles
If G has n vertices, then a Hamiltonian path must
contain exactly n-1 edges, and a Hamiltonian cycle
must contain exactly n edges.
If a vertex v in G has degree k, then a Hamiltonian
path must contain at least one edge incident on v
and at most two edges incident on v.
Once a vertex is selected in the path then all other
unused edges associated with the vertex must be
deleted as only two edges incident on v can be
included in a Hamiltonian cycle.
Scheduling Problem
Suppose state legislature has a list of 21 standing
committees.
Each committee is supposed to meet one hour each
week.
The constraint is that no legislator should be
schedule to be in two different committee meetings
at the same time.
The problem is to obtain a weekly schedule such
that it comprise of minimum hours of time for
meeting with no legislators share two meeting.
Solution