Twierdzenie Bondy’ego-Chvátala
Wygląd
(Przekierowano z Twierdzenie Bondy'ego-Chvátala)
Twierdzenie Bondy’ego-Chvátala – twierdzenie pozwalające stwierdzić, czy graf jest hamiltonowski.
Treść twierdzenia
[edytuj | edytuj kod]Niech będzie grafem o wierzchołkach, a oznacza jego nadgraf zbudowany według reguły mówiącej, że dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków takich, że:
należy dodać krawędź Graf jest hamiltonowski wtedy, i tylko wtedy, gdy jest hamiltonowski.
Zobacz też
[edytuj | edytuj kod]Bibliografia
[edytuj | edytuj kod]- Jonathan David Gross, Jay Yellen: Handbook of Graph Theory. CRC Press, s. 801. ISBN 1-58488-090-2.