Z Wikipedii, wolnej encyklopedii
Twierdzenie o liczbie krawędzi pozwala stwierdzić, czy graf jest hamiltonowski.
Jeśli graf prosty o wierzchołkach ma co najmniej
krawędzi, to jest hamiltonowski.
Dla dowolnego grafu prostego załóżmy, że zachodzi
i weźmy wierzchołki i takie, że:
Niech będzie grafem z którego usunięto wierzchołki i oraz kończące się w nich krawędzie. Ponieważ:
więc usunęliśmy krawędzi i dwa wierzchołki. jest podgrafem grafu a więc:
z czego wynika, że:
a więc spełnia założenia twierdzenia Orego.
Najważniejsze pojęcia |
|
---|
Wybrane klasy grafów |
|
---|
Algorytmy grafowe |
|
---|
problemy grafowe |
|
---|
Inne zagadnienia |
|
---|