Graf hamiltonowski: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m robot dodaje: sk:Hamiltonovská kružnica |
→Warunki wystarczające: dr.red. |
||
Linia 40:
== Warunki wystarczające ==
Istnieją jednak twierdzenia pozwalające na podstawie cech grafu, dostępnych w czasie liniowym, stwierdzić jednoznacznie,
Twierdzenia te są matematycznym obrazem dość naturalnej obserwacji dotyczącej własności grafów - jest logiczne, że im więcej jest krawędzi w grafie, tym "większe są szanse" na znalezienie wśród nich drogi Hamiltona. W skrócie (i nieformalnie), poniższe twierdzenia mówią, że graf jest hamiltonowski, jeżeli tylko ma on odpowiednio dużo krawędzi w stosunku do ilości wierzchołków.
| |||