0000051 2

Obowięzujo przy tym identyczno numeracja wierzchołków grafu C i odpowiadających im gałęzi grafu c!

Przykład 6.2

W oeejl egzaminacyjnej cztery grupy {g_Ł.82*93*94} ®®J® ^mł®^ eiedem egzaminów z czterema wykłodowcomi (wj,w₂,w₃>w₄j . Modelem cysternowym tej sytuacji Jeot grof zwykły C • <X,U,P> przedstawiony no rya.6.3, gdzie X jeot zbiorom grup i wykładowców, a krawędzie reprezentuj! egzaminy U ■ {*^e2*®3'^a4'*5‘*6^,07}*

Nel iy opracować harmonogram aeaji egzaminacyjnej w ten tpoeób, aby było Jak nojmniej ar... w których będę odbywały się egzaminy, warunkiem koniecznym Jest przy tym, aby togo samego dnia oni wykładowco, oni grupo nie olała więcej niż Jednego ogzominu. Problem oprowodzo się do zodonio optymalnego pokolorowanio gałęzi grafu G. Iloóć kolorów będzie oznaczała iloóć dni egzaminacyjnych w teoji.

Tworzęc grof sprzężony G* z grafem G przekonujomy aię że Jeot on identyczny z grafem z przykładu 6.1, dla którego wyzne-czono Już optymalne pokolorowanie wierzchołków. Potrzebo zatem trzoch dni, w których maję być egzominy, T(c" ) • 3* Piarwazego dnia będę się odbywoły egzaminy {®i*®2'^#3**6) * drugiego {e₅} i trzeciego |e₄,e₇J.

6.4. Szocowanie liczby chromatycznej

W zastosowaniach praktycznych często występuje potrzeba szybkiego oszacowanio waVtoóci liczby chromatycznej grafu.

•%>

Poniżaj podano tą niektóre, najczęściej otooowono. ooza -co won lo liczby -j-(C) t

V <->(C) <1 T(C) 4 rz(C)

Oszacowania to Jest oczywista 1 nie wymaga komsntarzo.

2/ T(C) 4 S(C) ♦ i

Uzaaadnieniem tago oszacowanie jaat naotępujtce rozumowania >

Załóżmy, ta dowolnie przyporzfdkowcno kolory wierzchołkom 1 iloóć utytych kolorów Jaat równa k.

Przypuśćmy, te k>S(G) ♦ 1, a kolory ponumerowano liczbami od 1 do k. Można wtedy zmniejszyć ilość kolorów w naatępujocy sposób: Ważmy wlerzchołok x, który ma kolor o numerze J, J>S(G) t l. Ilość wierzchołków przyległyoh do x nia prze -kracza S(G).

Przydzlolimy dla x nowy kolor o najmnlajezya numerze ze zbioru kolorów nlewykorzyotanych przez wierzchołki przyległe do x. W najgorszy* wypadku będzie to kolor o numerze równym S(G) ♦ 1, to znaczy w tym wypadku, gdy e(x) ■ S(G), a wierz -chołkl przyległe do x wykorzystuj! kolory o numerach od l do S(G). Uzyskane nowe pokolorowanie (nowy kolor wierzchołka x) jeet dobrym i pełnym pokolorowaniem wierzchołków grafu. Podobnie motamy zmlonió kolejno kolory wazyetkich tych wierzchołków, których kolory maj! numery więkeze od S(G) ♦ 1.

3/ TWIERDZENIE 6.2 (Brooks, 1941)

Detali dla grafu zwykłego S(G)>3 oraz żadna jego

składowa spójności G¹ nie Jest grafem pełnym rzędu

rz(G' ) - S(C) ♦ 1, to y(G) 4 S(G)

Dowód tego twierdzenia Jest zamieszczony w [53].

4/ Oznaczmy k₈(G) -|{a(x) i x € x}|

to ilość różnych otopnl wierzchołków w grafie).

TWIERDZENIE 6.3 (Oirac, 1964)

Detali G ■ <X,U,P> Jeot grafem zwykłym, to ,

T(G) 4 rz(C) - antier [| k_t(G)]

101