0000036

TWIERDZENIE 4.4

Podzbiór 0 wierzchołków grafu jest Jfdroa wtedy 1 tylko wtedy, gdy 3 Jeet Jednocześnie makeyaolnya zbiorę* wownętrznie atobllnya 1 minimalny* zbiorą* zorrnęt rznie etebilnyn.

Dowód t

Należy dowiaóć dwie- implikacje: prosty 1 odwrotny. Implikacjo odwrotna jest prawdziwa z definicji Jydra. Wyatorczy zeta* dowiaóć, la Jeżeli 0 Jeet jydraa, to 0 Jest jednocześnie meksyaalnym zbiorem wownętrznle etabllnya 1 ainlaalnya zblorea zewnętrznie etabllnya.

Załóżay, że laplikacja jest fałszywo, to znaczy istnieje Jydro 3 i Jednocześnie 3 ni* Jest aaksyaelnya zbiór** wewnętrzni* stabilny* (a) lub ainlaalnya zblorea zownętrznle etobllnya (b).

Rozweżay przypadek (a)s Niech wierzchołek * f3. Wtedy z definicji Jydra otrzymujemy, że    / f8 . Doleli zetem doły-

czyay x do zbioru 3. to 3 u(x) ni* Jest zbiorę* wewnętrzni* stabilnym. Zatem 3 auoi być maksymalnym zbiorem wewnętrznie etabllnya.

Rozważmy przypadek (b)i Podgraf tworzony przez 3 nie za -wlera ani jednej gałęzi. Bioryc zatem dowolny wierzchołek y€3 i tworzyć zbiór V • 3\{y} otrzymamy, że V ni* Jeet zbiorem zewnętrznie etabllnya, ponieważ N^ ^ V • JJ . Zatem 3 musi być minimalnym zbiorem zewnętrznie stabilny*. Sprzecz -ność uzyskana w obu przypadkach (a) 1 (b) dowodzi prawdziwości implikacji prostej 1 kończy dowód twierdzenia.

W n i o s * kj Wyznaczajyc wszystkie maksymalne zbiory wewnętrzni* etabiln* i wozyetkle miniaeln* zbiory zewnętrznie stabilno oraz porównujyc J* możemy wyznaczyć wszystkie Jydra grafu.

TWIERDZENIE 4.5

Każdy digrof symetryczny bez pętli ma Jydro 1 każdy maksymalny zbiór wewnętrzni* stabilny takiego grafu jost jędrem.

Dowód można znaleźć w [4].

Każdy digrof przochodni buz pętli no jędro i kożdy minimalny zbiór zownętrznie atobllny takiego grafu Joot Jedrem.

Oowód można znolożć w [4].

TWIERDZENIE 4.7

Kożdy digraf, nie zawiorejęcy dróg cyklicznych, ma pojodynczo Jodro.

(Pojęcio drogi cyklicznej Jeet podono w rozdziale 5).

Dowód twierdzenia można znaleźć w [4].

Problemotyko Jęder ma duże znaczenie przy analizio i roz-więzywaniu okończonych gier wiolochodowych. Modelem takiej gry może być digrof. Znalezienie Jodra takiego dlgrafu Jeet równoważno rozwięzenlu toklej gry.

ł

7i