0000033 2

Bazy grafu C oę tworzono przez podzbiory wlorzchołków:

{1.2.3.4} . {2.3.4} . {1.3.4} . {1.2.4} . {1,2.3} . (2.3) 1 {1.2}. Boży nlnlaolne grafu C tworzę podzbiory 1 {1.3,4} , {2.3}    1 {1.2} . Ó(C) -2.

>

Boży grafu C_d 00 tworzono przoz podzbiory wlorzchołków1

{1.2.3.4} . {2,3.4} . {1,3.4} . {1.2,4} , {1.2.3} . {3.4} ,{2.4} {1.4} . {1.3} i {4}. <f(C_d) - 1.

Bazy alnlaolno grafu G_d tworzę podzbiory:

{1.3} 1 {*}•

Podgrofy puoto grafu G (połno grafu G_d) tworzę podzbiory:

9. {1} . {2} . (3) . {4} . {1.4} i {3.4} .

Maksymalne podgrafy pusto grafu G (maksymalno połno grafu G_d) tworzę podzbiory:

{2} . {1.4} i {3.4}.

Podgrafy połno grafu G (pusta grafu G_d) tworzę podzbiory:

9. {1}. (2}. {3}. {4}.(1.2} . {1.3} . {2.3).{2.4} i {1.2,3}.

Mokayaolne podgrafy połno grafu G (moksymalno puste grofu G_d) tworzę podzbiory:

(2.4} i (1,2.3}.

*(C) - 2. oc(G_d) - 3. u>(C) - 3. u)(G_d) - 2 4.3. Zbiory zownętrznio stabilne

Wożaiemy pod uwagę graf G ■ (X,U,P> .

Podzbiór wierzchołków TCX jest zbiorem zew- • nętrznle stabilnym wtedy i tylko wtedy, gdy

A

ZCX\T

{ v_tT [<«.».»>*«}

U CU

Inaczej mówięc, dla każdego wierzchołka opoza T letniaje "przejście* przoz jednę galęż do zbioru T.

Ola hiporgrefu H ■ <X,U,P> dofinicję zbioru zewnętrznie atabilnogo Tcx można zapiaać formalnie naotępujęco

Ola każdego wierzchołka x_i określimy N^C X w naetępujęcy epo-eób

przy tym N< możemy nazwać zbiorem "naetępników" wierzchołka , uzupołnionym wierzchołkiem x_Ł.

Definicję zbioru zewnętrznie etabilnego TCX możemy w apoeób ogólny zapioać formalnie naetępujęco

(<.l )

Łatwo zauważyć, że do zbioru zewnętrznie etabilnego muezę na -leżeć wezyetkie wierzchołki gołe i izolowane.

Minimalnym zbiorem zewnętrznie atabilnym nazywamy każdy zbiór zewnętrznie etabilny, który nie zawiera podzbioru właściwego, będęcego innym zbiorem zewnętrznie atabilnym danego grafu (hipergrafu).

Najmniej licznym zbiorem zewnętrznie etabilnym jeet każdy taki zbiór zewnętrznie etabilny, który w danym grafie (hipergrafie) ma naj-mniejezę ilość wierzchołków.

65