0000027 2

Podgrof (podhlporgraf) zerowy oraz pusty graf częóclowy (hlporgrof częściowy) odgrywoje rolę elemontów zerowych w strukturach algebraicznych stosowanych w teorii grafów i hiporgrafów. Wielu autorów nie wprowadza grafu zerowego, zakłodojec X / f). lecz wtedy wiele twlerdzoó traci ewę ogólnoóć. Rezygnacja z grafu zerowego w wielu pozycjoch litoratury wynika z trudnoócl interpretacji fizycznej taklogo grafu.

3.2. Dozo grafu i hlpergrafu

Dozę grafu G ■ <X. U, P> nazywany kożdy taki podgraf G* - <x', Uj P*> . Ze katda gołe* uCU Joet lncydontno z przynajaniej Jodnya wierzchołkiem xex' tego podgrafu. Ano -logicznie zdoflniowona jeet bazo hlpergrafu.

Dozę minimalne C‘• <x', u', P'> grafu G ■

» <X, U, P> Jcot koZda toko bożo, żo kozdy podzbiór właóciwy zbioru X¹ okrodło podgrof nie będgcy boże grafu G.

Ola danego grafu G nozc lotnleć wiele róZnych boz minimalnych o róZnych llodcloch wierzchołków.

Oazę nojmnioj liczne joot koZda toko. bazo. któro zowiero nojeniojo2e llodć wierzchołków w porównoniu ze wozyetklmi bazami danego grafu. Graf moZe mieć . . .o róZnych boz najmniej licznych. KoZda baza najmniej liczna joot oczywid-cie boże minimalne.

Oazo minimalna i najmniej liczno hlpergrafu joot zdefiniowana w sposób analogiczny. Oazę najmniej liczne grafu pustego jeet grof zerowy G° • <JJ. fl. P) .

Liczbę bozowe grofu (hiporgrofu) <f(C) na -• zywaay llodć wierzchołków nojmniej licznej bazy grafu G (hipor-grafu). ZauwaZmy, Ze do koZdoj boży musze wchodzić wierzchołki lncydontno z pętlami {hlperpętloml).

3.2.1. Metoda wyznaczania wszystkich boz mlnleolnych

Woźmy pod uwagę grof (hipergrof) okrodlony trójkę <X,U,P> oroz jego binarne mocierz lncydencjl A^b • [°ij]_n»« * ⁿ " 1*1•

» • I U |.

Oznoczymy przoz Y rodzinę wszystkich podzbiorów Y c x. KaZdy podzbiór Y«Y okroćlo odpowiedni podgraf (podhlpergraf). Niektóre z nich sę bazami. KaZdy podzbiór Y moZna jednoznocznle okreólló binarny*, n-wymtarowym woktorom charakterystycznym

_    , Y    Y    y .

^ \ X^ « • « X_§ f    | X_n )

1    gdy x e Y

O    gdy k,(Y

Oznoczymy    zbiór wszystkich wektorów    Oczywiściet

lx⁽ⁿ⁾l - 2ⁿ ,

X⁽ⁿ⁾ -xi^n,^x[ⁿ⁾.

X<ⁿ⁾ - zbiór woktorów określojęcych boży,

X^ⁿ) - zbiór wektorów ni* określajęcych boz.

Niech okładowe wektora x będę zmlonnyml boolowsklei.

Określimy funkcję    boolowskę f(    X^ⁿ^)    takę,    Ze

|    l    dl.

f(xlⁿ>) . |

1    o    di.

Określenie f(    x(ⁿ))    jest    równoważne    określaniu wszystkich baz

grafu (hlpergrafu), a określenie wszystkich wektorów minimal -nych funkcji f(x^ⁿ))_# o ile f(x^ⁿ^) Jest funkcję aonotonicznę (patrz dodatek O.l), jeet równowoZne określeniu wszystkich baz minimalnych.

Ola ułatwienia wyjaśnienia Istoty matematycznej sposobu określenia funkcji f(x'ⁿ^) ograniczymy się na chwilę wyłęcznle do grafów. KoZda gałęź grafu u^ Jost lncydentns z dwoma (nio -

53