Wikipedia

Cykl Hamiltona: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
Rnm (dyskusja | edycje)
3412 edycji
w edycji
Rnm (dyskusja | edycje)
3412 edycji
przenosze twierdzenia do 'graf hamiltonowski'
Linia 1:
{{WEdycji|Rnm}}
 
'''Cykl Hamiltona''' to taki [[cykl]] w [[graf (matematyka)|graf]]ie, w którym każdy [[Graf (matematyka)|wierzchołek grafu]] występuje dokładnie jeden raz. 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]].
 
Zobacz też: [[cykl Eulera]], [[graf Hamiltonowski]], [[problem komiwojażera]], [[algorytm najbliższego sąsiada]]
 
==Twierdzenie (Ore, 1960)==
 
Jeżeli w [[graf]]ie ''G'' [[rząd grafu (matematyka)|o n wierzchołkach]], <math>\! n>2</math> zachodzi następująca nierówność
<math>deg(v)+deg(w) \geq n</math>
dla każdej pary [[wierzchołki niesąsiednie (matematyka)|niesąsiednich wierzchołków]] ''u'' i ''v'', wówczas graf ''G'' jest hamiltonowski.
 
===Dowód:===
Załóżmy, że twierdzenie jest prawdziwe dla pewnej liczby ''n'' i niech ''G'' będzie kontrprzykładem takim, że wartość <math>\! |E(G)|</math> jest największa. Graf jest podgrafem grafu hamiltonowskiego <math>K_n</math>. Dodanie do ''G'' krawędzi z grafu <math>K_n</math> daje w wyniku graf, który nadal spełnia założenia nałożone na niesąsiednie wierzchołki, i który ma więcej niż <math>\! |E(G)|</math> krawędzi. Ze względu na wybór grafu ''G'' każdy tak powstały graf będzie miał cykl Hamiltona. To znaczy, że ''G'' musi mieć (przynajmniej) drogę Hamiltona, określoną przez ciąg wierzchołków, [[BSO]] <math>v_1,v_2,\cdots ,v_n</math>. Ponieważ ''G'' nie ma cyklu Hamiltona, to nie istnije krawędź łącząca <math>v_1\ i\ v_n</math>, a więc <math>deg(v_1)\ +\ deg(v_n)\ge n</math>.
 
Można zdefiniować podzbiory zbioru <math>\{2,3,\cdots ,n\}</math> takie, że:
 
 
<math>S_1\ =\ \{i:\ \{v_1,v_i\}\in E(G)\}</math> i <math>S_n\ =\{i:\{v_{i-1},v_n\}\in E(G)\}</math>
 
 
Wtedy <math>|S_1|\ = \deg(v_1)\ i\ |S_n|\ =\ deg(v_n)</math>. Ponieważ <math>|S_1|+|S_n|\ge n</math> i <math>S_1 \cup S_n</math> ma co najwyżej ''n-1'' elementów, a więc zbiór <math>S_1 \cap S_n</math> musi być niepusty. Istnieje więc liczba ''i'',dla której istnieją krawędzie <math>{v_1,v_i}\ i\ {v_{i-1},v_n}</math>. Wtedy droga
 
 
<math>v_1,\cdots ,v_{i-1},v_n,\cdots ,v_i,v_1</math>
 
 
jest cyklem Hamilotona w grafie ''G'', co przeczy jego wyborowi. CKD
 
==Twierdzenie (Dirac, 1952)==
 
Jeżeli w grafie prostym ''G'', który ma ''n'' wierzchołków i <math>n > 2</math>, [[stopień wierzchołka (matematyka)|stopień]] każdego wierzchołka ''v'' grafu ''G'' jest co najmniej <math>\frac{n}{2}</math> (<math>deg(v)\geq \frac{n}{2}</math>), to graf ''G'' jest hamiltonowski.
 
===Dowód===
 
 
[[Kategoria:Teoria grafów]]
 
Źródło: „https://pl.wikipedia.org/wiki/Cykl_Hamiltona”