Twierdzenie Diraca
Twierdzenie Diraca – twierdzenie pozwalające stwierdzić, czy graf jest hamiltonowski, zostało sformułowane w roku 1952. Nazwa pochodzi od Gabriela Diraca.
Treść twierdzenia[edytuj | edytuj kod]
Jeśli graf nie ma pętli, ani krawędzi wielokrotnych (jest grafem prostym) i
oraz jeśli
dla każdego wierzchołka w to jest on hamiltonowski[1].
Dowód twierdzenia[edytuj | edytuj kod]
Jeśli dla każdego wierzchołka
to
dla każdego wierzchołka i niezależnie od tego, czy są połączone krawędzią, czy nie, a więc spełnia założenia twierdzenia Ore, a więc jest hamiltonowski.
Zobacz też[edytuj | edytuj kod]
- twierdzenie Bondy’ego-Chvátala
- twierdzenie Orego
- twierdzenie o liczbie krawędzi (graf hamiltonowski)
Przypisy[edytuj | edytuj kod]
- ↑ Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 214. ISBN 0-387-95014-1.