Tuesday, 24 April 2012
A Hamiltonian cycle in a dodecahedron. Like all platonic solids, the dodecahedron is Hamiltonian.
Hamilton path - a simple path in a graph that passes through every vertex exactly once.
Hamilton circuit - a simple circuit in a graph that passes through every vertex exactly once and end back at the 1st vertex.
Dirac's Theorem - if graph is a simple graph with n vertices with n >=3 such that the degree of every vertex in G is at least n / 2, then G has a Hamilton circuit.
Ore's Theorem - if graph is a simple graph with n vertices with n=> 3 such that deg(u) + deg(v) >= n
for every pair of nonadjacent vertices U and V in graph, then the graph has a Hamilton circuit
(DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H.Rosen)
An Eulerian cycle, also called an Eulerian circuit, Euler circuit, Eulerian tour, or Euler tour
An Euler circuit in a graph in a simple circuit containing every edge of Graph.
An Euler Path in Graph is a simple path containing every edge of graph.
Theorem 1
A connected multigraph with at least two vertices has an Euler if and only if each of its vertices has even degree.
Theorem 2
A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.
(DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H.Rosen)
An Euler circuit in a graph in a simple circuit containing every edge of Graph.
An Euler Path in Graph is a simple path containing every edge of graph.
Theorem 1
A connected multigraph with at least two vertices has an Euler if and only if each of its vertices has even degree.
Theorem 2
A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.
(DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H.Rosen)
Subscribe to:
Posts (Atom)