|
|
|
|
|
|
|
|
Neben den bisher zugrundegelegten Kantenfolgen in einem Graphen sind
auch die sich nicht überkreuzenden Kantenfolgen, Kreise, von
Bedeutung.
Graph mit (links) und ohne (rechts)
Hamiltonschen Kreis.
Satz von Dirac (hinreichende Bedingung):
Besitzen in einem Graphen 
alle Ecken einem Grad größer gleich
k, 
und ist 
, so besitzt G
einen Hamiltonschen Kreis.
|
|
|
|
|
|
|
|
