DSC00280 (8)

BAZY MINIMALNE

DEFINICJA BAZY GRAFU;

Bazą grafti G ^m <W,U,Q> nazywamy każdy taki podgraf G' ■ <W',V\Q*> tego grafU, że dowolna gałąź u&U grafti G jest incydentna z przynajmniej jednym wierzchołkiem w*W* tego pod grafu.

TWIERDZENIE:

Podgraf G' ^m<W^,,U\Q*> grafti G ^m <W,U,Q> jest bazą tego grafti <“> zbiór wierzchołków W— w‘ tworzy podgraf pusty tego grafti.

BAZA MINIMALNA- nie można usunąć ani jednego wierzchołka w ten sposób aby pozostałe wierzchołki również tworzyły bazę tego grafu.

Dopełnienie do bazy minimalnej jest maksymalnym podgrafem pustym.

ALGORYTM WYZNACZANIA BAZ MINIMALNYCH:

1.    Numerujemy wierzchołki grafu G ^m <W,U,Q> i przyporządkowujemy im zmienneboolowskie Xt,l^mgdzie n^m\W\ *1"{0,1}.

2.    Numerujemy gałęzie grafti liczbami J ^m l,2,..,m m-| U\ 1 tworzymy binarną macierz incydencji wierzchołków i gałęzi grafti

A^b[G]^m[a^kuJ

3.    Tworzymy wyrażenie boolowskie według wzoru:

f(^)-TTZ^a^

4.    Przekształcamy f(xf^) do postaci minimalnej formuły alternatywnej mfa

ŁkJ

f(xf^n>)- 277&

k

stosując właściwości algebry Boole’a.

5.    Na podstawie ntfa określamy wszystkie bazy minimalne grafti:

*    liczba baz minimalnych jest równa liczbie iloczynów występujących w sumoiloczynie ntfa

♦    każda baza minimalna jest określona przez odpowiedni iloczyn w ten sposób, że do podzbioru jej wierzchołków wchodzą te wierzchołki grafti, których zmienne boolowskie występują w odnośnym iloczynie.

Jak wyznaczyć maksymalne podgrafy puste ?