Cykl Hamiltona: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
drobne redakcyjne |
m Dodanie szablonu, oraz rozbudowa artykułu. |
||
Linia 1:
{{Teoria grafów}}
'''Cykl Hamiltona''' to taki [[Cykl (teoria grafów)|cykl]] w [[graf (matematyka)|grafie]], w którym każdy [[wierzchołek|wierzchołek grafu]] odwiedzany jest tylko jeden raz (oprócz pierwszego wierzchołka). Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu [[problem komiwojażera|problemu komiwojażera]]. Grafy zawierające cykl Hamiltona nazywamy [[graf hamiltonowski|hamiltonowskimi]]<ref>{{Cytuj książkę | nazwisko = Diestel | imię = Reinhard | tytuł = Graph Theory | url=http://diestel-graph-theory.com/index.html | miejsce = Nowy Jork | rok = 2000 | strony = 213| isbn= 0-387-95014-1}}</ref>.▼
'''Cykl Hamiltona''' to taki [[Cykl (teoria grafów)|cykl]] w [[graf (matematyka)|grafie]], w którym każdy [[wierzchołek|wierzchołek grafu]] odwiedzany jest dokładnie raz (oprócz pierwszego wierzchołka). Analogicznie, ścieżka Hamiltona to taka ścieżka w której każdy wierzchołek odwiedzony jest dokładnie raz. Nazwa cyklu i ścieżki pochodzi od irlandzkiego matematyka [[William Rowan Hamilton| Hamiltona]].
▲
== Zobacz też ==
|