0000046 2

TWIERDZENIE 5.16

DeZell w grafie zwykłym, spójnym C rzędu rz(C)>3

•pełniony je#t warunek

A •(*) ♦ s(y)> rz(G)

<*,y>

to w grafie tya istnieją cykl Haalltona.

Dowód:

wybierzmy w grafie C dowolny najdłuższy łańcuch prosty «£{x.y). którego długość oznaczymy przez 1. Oczywiście Urz(C)>l czyli rz(G)?l*l. Dednocześnla 1>2. ponieważ rz(G)>3, a graf C jest spójny.

Otrzyaujemy zatem

• (*) ♦ s(y) > lal ;    1 > 2

czyli warunek dostateczny na istnienie w C cyklu Haalltona (patrz twierdzenia 5.IG).

TWIERDZENIE 5.19 (Dirac)

DeZell dla koldego wierzchołka x zwykłego grafu opój-

nego C. rzędu rz(C)*3, spełniony jest warunek

•(»> > | ^r*(c) .

to w grafie G Istnieje cykl Haalltona.

Dowód i

Dla dowolnych dwóch wierzchołków x,y tego grafu otrzyau -jemy •(x) ♦ s(y)> rz(G). Na mocy twierdzenia 5.18 w takie grafie Istnieje cykl Hamiltona.

Przykład 5.5

Graf przedstawiony na rys.5.^ opełnia założenia twierdzenia 5.16. Mianowicie, łańcuch prosty najdłuższy ,£(1.4) ■

- {i. o. 2, d, 3. o, 6. f, 5, g, 4 } , o długości 1*5. aa własność •(1) ♦ s(4) ■ 6 * 1 « i . 6 ; 1>2.

Dinorno macierz przyległoócl wiorzchołków togo grafu aa postać

	1 2 3 4 5 6
1	OlOOll
2	10 110 0
3	0 10 10 1
4	0 110 10
5	10 0 10 1
6	10 10 10

1

2

d

3

Ryt. 5.1*

Zauważmy, źo w łańcuchu -£(1,4) istnieją pora kolejnych wierzchołków <3,G> taka, że rj ₆ » 1 j rjj ₃ - i. Zatea w grafie G ietnlojo cykl Hamiltona, który powetajo z łańcucha «£(1.4) w tpooób omówiony w dowodzio twierdzenia 5.16. Cykl ton jest no-ttępujocy {l. o, 2. d, 3, h, 4, g, 5, f. 6. b. l) (potrz ry-ounek 5.$).

91