0000044

N« podstawi* uzyskanych cech określamy na przykład następujący łańcuch Eulera

i_c(3.5) - {3.h.2.b.l.c.2.e.4.k.5,u.e.t.5.m.6.n.5.1.4.j, *.q.7.r.8.w.6.o.6.1.3.e.l.d.4.p_#7.e.0.t.*.v,

6.8.2, f.5} .

5.6.2.    Łańcuchowa pokrycia grafu

Łańcuchowy* pokryciem frafu ńozywomy wynik rozwiązania no-etępujęcego zadania: naloty wyznaczyć najeniejsz* ilość rozłącznych w sensie gałęzi łańcuchów, która w surio wyczerpywałyby wszystkie gałęzi* grafu.

Detali graf jest grafea Eulera, to wystorczy jeden łańcuch Eulera do pokryci* grafu.

Problea ten jest zatem Istotny dla grafu nie zawiorojęcego łańcucha Eulera.

Rozwalania ogranlczyny do grafu spójnego, ponlewot sformułowane zadanie naloty rozwlęzać nlezaletnle dla katdej składowej spójności. Poeocne będzie następujęce, oczywiste twierdzenie.

TWIERDZENIE 5.13

W dowolny* grafie ilość wierzchołków o nieparzystych rozwldlenlach Jest zawsze parzysta.

Oznaczay przez L ilość łańcuchów tworzęcych łańcuchowo pokrycie grafu, natomiast przez p ilość par wierzchołków o nieparzystych rozwldlenlach w tya grafie. Oczywista jeet naetępujęca nierówność Lł p. Detell zatem potrafimy wyznaczyć takie pokrycie, te L • p, to rozwlęZcay zadani* pokrycia łańcuchowego. Motemy tego dokonać w następujący sposób:

1° Łęczymy dowolnie w pary wierzchołki o nieparzystych rozwldlenlach za pomoc* dodatkowych krawędzi. Powstaje nadgraf, w który* istniej* cykliczny łańcuch Eulera.

2° Wyznaczamy cykliczny łańcuch Eulera w powstałym nadgrafie, a następnie usuwaay dodane krawędzie. Cykl Eulera rozpada się na p łańcuchów, tworzęcych optyaaln* pokrycie łańcu -chowe grafu.

5.7. Łańcuchy Hanlltona

Łańcucha* Hamiltona nazywa tlę łańcuch proaty wyczerpujący cały zbiór wierzchołków grafu. Cykle* Hanlltona nazywa się cykl pros-ty wycierpujycy wazy*tkle wierzchołki grafu.

TWIERDZENIE 5.14

W grafla G latnlaje łańcuch Hanlltona, o danyn dygu wierzchołków, wtedy 1 tylko wtedy, gdy w ezklelecle G_# tego grafu latnlaje łańcuch Hanlltona o ldentycz-nyn dygu wierzchołków.

Dowód tago twierdzenia wynika natychmiast z definicji ezkle latu grafu i definicji łańcucha prostego.

TWIERDZENIE 5.15

W grafie G rzędu rz(G) > 2 Istnieje łańcuch cykliczny / Hanlltona, o danyn dygu wierzchołków, wtedy 1 tylko wtedy, gdy w ezklelecle tego grafu Istnieje cykl Hamiltona o identyczny* clygu wierzchołków.

Zauważay, ta każdy łańcuch Hanlltona jaet łańcuchaa prostym najdłuższy* w dany* grafie 1 oczywiście łańcucha* prosty* ma-ksyaalnya.

TWIEROZENIE 5.16 (Ore)

Dożęli w grafie zwykły*, apójnya istnieje najdłuższy łańcuch prosty X(x_£),*₁) - { *₀,u_ł#...    o dłu

gości 1*2 taki, ża e(x₀) ♦ e(x^) > 1 ♦ 1, to graf zawiera cykl Haalltona, a i(x₀,x^) jest łańcucha* Hanlltona.

Dowód tago twierdzenia zawiera konstrukcję wyznaczający cykl Hanlltona. w dowodzie wykorzystuje oly nastypujycy lemat.

L a ■ a t

Podgraf G* grafu zwykłego, spójnego G, tworzony przez zbiór wierzchołków nakeynalnogo łańcucha prostego ^(x_Q,x^), takiego ie 1 > 2 i. e(x₀) ♦ e(x^)£ !♦!, zawiera cykl Haalltona.

07