Twierdzenie Diraca – Wikipedia, wolna encyklopedia
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.