0000047 2

Rozdział 6

CHROMATYKA GRAF&W

6.1. Pokrycia alnlaalne zbioru podzbloranl

wetaleay pod uwagę zbiór ekończony X oraz pewien zbiór podzbiorów (x_k) ; k • l.K, tego zbioru, epełnlajęcy warunek

6 x_k . x . A x„ t ₉

Mówimy, Za pewien (r—ty) podzbiór {x_f }; J • l7o_r , zbioru

{X_k} tworzy pokrycie zbioril X wtedy 1 tylko wtedy,

gdy U X ■ X. Pokrycia nazywamy alnlaalnye wte-i-ł

dy 1 tylko wtedy, gdy Żaden podzbiór właściwy zbiorów pokrywa* jocych nie tworzy pokrycia, Wśród pokryć alniaalnych iatnleje przynajmniej jedno pokryclo zawierające najanlejazę Ilość podzbiorów X_k. Oeat to pokrycie najmniej liczne.

Problem pokryć alnlaalnych polega na wyznaczaniu pokrycia najanlej licznego, na przykład przez wyznaczenie wezyatklch pokryć alnlaalnych i wybór wśród nich pokrycia najanlej licznego.

6.1.1. Algoryta wyznaczania pokryć alnlaalnych

Zaplazamy zbiory X_k za pomoc« macierzy binarnej 8^a [^blk]n.K • »^dI1' " ■ '^Xl ' ^K •|(^Xk!l

1    gdy x_i 6 X_k

’lk *

O    w przeciwnym wypadku

Macierz B jeet określona nad pierścieniem algebry Boole'a. w ten epoeób jedynki w poszczególnych kolumnach macierzy okreile-jy poszczególne podzbiory X_k<

Dowolny (r-ty) podzbiór |x_p ); j • £75 _p można zapisać

jednoznacznie za pomocy K wymiarowego, binarnego wektora ohe -

rakteryetycznego vJ^K) «<v    ,...,v    S, przy uetale -

nlu. Ze

....    1    k ^rx'

gdy

O w przeciwnym wypadku

wprowadzlay wektor    zmiennych booloweklch przyporzydkowe*

nych poszczególnym podzbloroe X_fe.

^    ■ (Vj,m

Zależnie od wartości zmiennych v_k wektor    bydzie lub nie

będzie określał pokrycia zbioru X,

Oznaczymy V(K)

zbiór wektorów określalycych pokrycia, a zbiór pozoetałych wektorów* V[^K*U\f[^K) > y(^K) ;

|V<^K>I - 2*.

warunkiem wyatarczajycya na to, aby y^^K) określał pokrycie, ,jeet

n i b v . 1    (6.1)

warunek ten określa funkcjy boolowaky    , taky za

1 dla O dla

^ev|^K>

(8.2)

y(^K) e y£^K>

Funkcja ta jeet aonotoniczny funkcjy boolowaky (.patrz 0.1), a jej wektory minjaalne okraślajy minimalna pokrycia, Ola zna*

93