Współczynnik osiągalności modułów wykresów. Digrafy i relacje binarne. Współczynnik osiągalności wierzchołków dwugrafu. Macierz osiągalności. Związek między osiągalnością a relacjami sąsiedztwa Drzewa nieskierowane i ukierunkowane

G(V,X) z pętlami, ale bez wielokrotnych łuków definiuje binarną relację X na zbiorze V. Kompletny wykres odpowiada uniwersalnej relacji. Wykres nieskierowany odpowiada relacji symetrycznej. Uzupełnienie wykresu odpowiada uzupełnieniu relacji. Zmiana kierunku łuków odpowiada odwrotnej relacji.

Digrafy i relacje binarne to ta sama klasa obiektów opisywanych różnymi środkami. Relacje binarne, funkcje to podstawowe narzędzia do budowy zdecydowanej większości modeli matematycznych, które służą do rozwiązywania praktycznych problemów, a wykresy można wizualizować w formie diagramu. To wyjaśnia powszechne stosowanie diagramów różnych typów w kodowaniu i projektowaniu.

Wierzchołek b dwugrafu (wykresu) G nazywa się osiągalny z U wtedy i tylko wtedy, gdy U=V lub istnieje ścieżka (trasa) łącząca U z V (U jest wierzchołkiem początkowym, V jest wierzchołkiem końcowym). Zatem na zbiorze wierzchołków dwugrafu (grafu) definiuje się nie tylko relację sąsiedztwa A, ale także relację osiągalności T.

Macierz osiągalności T digraf (wykres) G nazywa się T 2 n×n, którego elementy znajdują się z warunku: 1, jeśli jest osiągalny z ; 0, jeśli nie jest osiągalny z .

Definicja macierzy osiągalności dwugrafu jako macierzy zwrotnego i przechodniego domknięcia relacji sąsiedztwa.

Wprowadzona relacja osiągalności na wierzchołkach grafu G(V,X): wierzchołek w jest osiągalny z wierzchołka v, jeśli v = w lub istnieje ścieżka od v do w w G. Innymi słowy, osiągalność jest zwrotnym i przechodnim zamknięciem relacji sąsiedztwa.

Znajdź macierz sąsiedztwa, domknięcie przechodnie i zwrotne.

Łączność na wykresach. Słaba, jednokierunkowa i silna łączność w digrafach. Macierz łączności i silnej łączności. Składniki łączności. Definicja macierzy silnej łączności w oparciu o macierz osiągalności.

G(V,X) nazywa się połączony jeśli którykolwiek z jego wierzchołków jest osiągalny z dowolnego innego wierzchołka.

Dwuznak G(V,X) nazywa się połączenie w jedną stronę, jeśli dla dowolnych dwóch wierzchołków co najmniej jeden jest osiągalny z drugiego.

Dwuznak G(V,X) nazywa się silnie powiązany jeśli którykolwiek z jego wierzchołków jest osiągalny z dowolnego innego.

Dwuznak G(V,X) nazywa się luźno połączony, jeżeli jest połączony odpowiadający mu niedigraf, uzyskany w wyniku usunięcia orientacji łuków.

Digraf, który nie jest słabo połączony, nazywa się niespójny.

Silny składnik wiązania wykresu G(V,X) nazywamy maksymalnym, zgodnie z liczbą wystąpień wierzchołków, silnie powiązanym podgrafem tego wykresu. Spójny składnik dwugrafu definiuje się podobnie.

Macierz silnej łączności (łączność) wykresu (grafu) G(V,Х) nazywamy S n×n, którego elementy znajdują się z warunku: 1, jeśli jest osiągalny z i osiągalny z ; 0 jeśli nieosiągalny z i nieosiągalny z .

(digraf) silnie spójny lub spójny, wystarczy określić obecność 0 w macierzy jeśli

0 nie występuje, to wykres (digraf) jest połączony (silnie połączony), w przeciwnym razie nie.

Silnie powiązaną macierz można skonstruować z macierzy osiągalności za pomocą wzoru

Rozważane są kwestie osiągalności dla digrafów oraz metody znajdowania macierzy osiągalności i przeciwosiągalności. Rozważana jest metoda macierzowa do znajdowania liczby ścieżek pomiędzy dowolnymi wierzchołkami grafu, a także do znajdowania zbioru wierzchołków zawartych w ścieżce pomiędzy parą wierzchołków. Cel wykładu: Przedstawienie idei osiągalności i kontrosiągalności oraz sposobu ich znajdowania

Osiągalność i kontrdostępność

Zadania, w których koncepcja jest używana osiągalność, całkiem sporo.

Oto jeden z nich. Wykres może być modelem jakiejś organizacji, w której ludzie są reprezentowani przez wierzchołki, a łuki interpretują kanały komunikacji. Rozważając taki model, można zapytać, czy informacje od jednej osoby i można przekazać innej osobie j , czyli czy istnieje ścieżka biegnąca od wierzchołków i do wierzchołków j . Jeśli taka ścieżka istnieje, to mówimy, że wierzchołki j osiągalny od wierzchołków i . Można zainteresować się osiągalnością wierzchołków j z wierzchołków i tylko na ścieżkach, których długość nie przekracza określonej wartości lub których długość jest mniejsza od największej liczby wierzchołków na wykresie itp. problemu.

Osiągalność na grafie opisuje macierz osiągalności R=, i, j=1, 2, ... n, gdzie n jest liczbą wierzchołków grafu, a każdy element definiuje się następująco:

r ij =1, jeśli wierzchołki j są osiągalne z x i ,

r ij =0, w przeciwnym razie.

Zbiór wierzchołków R(x i) grafu G, osiągalnych z danego wierzchołka x i , składa się z elementów x i, dla których (i, j)-ty element macierzy osiągalności jest równy 1. Oczywiście wszystkie przekątne elementy w macierzy R są równe 1, ponieważ każdy wierzchołek jest osiągalny od siebie ścieżką o długości 0. Ponieważ bezpośrednie odwzorowanie pierwszego rzędu Г +1 (x i) jest zbiorem takich wierzchołków x j, które są osiągalne z x i przy użyciu ścieżki o długości 1, to zbiór Г + (Г +1 (x i)) = Г +2 (x i) składa się z wierzchołków osiągalnych z x i przy użyciu ścieżek o długości 2. Podobnie, r + p (x i) jest zbiorem wierzchołków które są osiągalne od x i przy użyciu ścieżek o długości p.

Ponieważ każdy wierzchołek grafu, który jest osiągalny z x i, musi być osiągalny przy użyciu ścieżki (lub ścieżek) o długości 0 lub 1, 2, ... lub p, zbiór wierzchołków osiągalnych dla wierzchołka x i można przedstawić jako

R (x i) = ( x i ) G +1 (x i) G +2 (x i) ... G + p (x i).

Jak widać, zbiór osiągalnych wierzchołków R(x i) jest bezpośrednim przechodnim zamknięciem wierzchołka x i , tj. R(x i) = T + (x i). Dlatego, aby skonstruować macierz osiągalności, znajdujemy osiągalne zbiory R(x i) dla wszystkich wierzchołków x i X. Ustawienie r ij =1 jeśli x j R(x i) oraz r ij =0 w przeciwnym wypadku.

Ryż. 4.1. Osiągalność w grafie: a -graf; b – macierz sąsiedztwa; c – macierz osiągalności; r jest macierzą kontrosiągalności.

Dla wykresu pokazanego na ryc. 4.1,a, osiągalne zestawy znajdują się w następujący sposób:

R (x 1) = ( x 1 ) ( x 2 , x 5 ) ( x 2 , x 4 , x 5 ) ( x 2 , x 4 , x 5 ) = ( x 1 , x 2 , x 4 , x 5 ),

R (x 2) = (x 2) (x 2, x 4) (x 2, x 4, x 5) (x 2, x 4, x 5) = (x 2, x 4, x 5),

R (x 3) = ( x 3 )( x 4 )( x 5 )( x 5 ) = ( x 3 , x 4 , x 5 ),

R (x 4) = ( x 4 )( x 5 )( x 5 ) = ( x 4 , x 5 ),

R (x 5) = ( x 5 )( x 5 ) = ( x 5 ),

R (x 6) = ( x 6 )( x 3 , x 7 )( x 4 , x 6 )( x 3 , x 5 , x 7)( x 4 , x 5 , x 6) = ( x 3 , x 4, x 5, x 6, x 7),

R (x 7) = ( x 7 )( x 4 , x 6 )( x 3 , x 5 , x 7)( x 4 , x 5 , x 6) = ( x 3 , x 4 , x 5 , x 6 , x 7 ).

Macierz osiągalności ma postać pokazaną na ryc. 4.1,c. Macierz osiągalności można zbudować według macierz sąsiedztwa(Rys. 4.1b), tworząc zbiory T + (x i) dla każdego wierzchołka x i .

Macierz kontrosiągalności Q = [ q ij ],i, j =1, 2, ... n, gdzie n jest liczbą wierzchołków grafu, definiuje się następująco:

q ij =1, jeśli z wierzchołka x j można dojść do wierzchołka x i ,

q ij =0, w przeciwnym razie.

możliwe do przeciwdziałania zbiór Q (x i) jest zbiorem wierzchołków takim, że z dowolnego wierzchołka tego zbioru można dotrzeć do wierzchołka x i . Podobnie jak przy konstrukcji osiągalnego zbioru R (x i), możemy napisać wyrażenie na Q (x i):

Q (x i) = ( x i ) Г -1 (x i) Г - 2(x i) ... Г -p (x i).

Jest więc jasne, że Q (x i) jest niczym innym jak odwrotnym przechodnim zamknięciem wierzchołka x i, tj. Q (x i) = T - (x i). Z definicji wynika, że kolumna x i macierzy Q (w której q ij =1 jeśli x j Q (x i), a q ij =0 w przeciwnym razie) pokrywa się z wierszem x i macierzy R, tj. Q = R T , gdzie R T jest macierzą transponowaną do macierz osiągalności R.

Macierz kontrosiągalności pokazano na ryc. 4.1, g.

Należy zauważyć, że ponieważ wszystkie elementy macierzy R i Q są równe 1 lub 0, każdy wiersz można zapisać w postaci binarnej, oszczędzając koszty pamięci komputera. Macierze R i Q są wygodne do przetwarzania na komputerze, ponieważ z obliczeniowego punktu widzenia główne operacje to szybkie operacje logiczne.

Znajdowanie zbioru wierzchołków zawartych w ścieżce

Jeśli chcesz wiedzieć o wierzchołkach grafu zawartych w tych ścieżkach, powinieneś pamiętać o definicjach domknięć przechodnich bezpośrednich i odwrotnych. Ponieważ T + (x i) jest zbiorem wierzchołków, do których są ścieżki z wierzchołka x i , a T - (x j) jest zbiorem wierzchołków, z których są ścieżki do x j , to T + (x i) T - (x j ) jest zbiorem wierzchołków , z których każdy należy do co najmniej jednej ścieżki biegnącej od x i do x j . Te wierzchołki są nazywane podstawowymi lub integralnymi w odniesieniu do dwóch wierzchołków końcowych x i oraz x j . Wszystkie inne wierzchołki grafu nazywane są nieistotnymi lub nadmiarowymi, ponieważ ich usunięcie nie wpływa na ścieżki od x i do x j .

Ryż. 4.2. dwuznak

Tak więc dla wykresu na ryc. 4.2 znalezienie wierzchołków zawartych w ścieżce, na przykład od wierzchołka x 2 do wierzchołków 4, sprowadza się do znalezienia T + (x 2) \u003d ( x 2, x 3, x 4, x 5, x 6 ),

T - (x 4) \u003d ( x 1, x 2, x 3, x 4, x 5) i ich przecięcia T + (x 2) T - (x 4) \u003d ( x 2, x 3, x 4, x 5).

Macierzowa metoda znajdowania ścieżek w grafach

Macierz sąsiedztwa całkowicie definiuje strukturę grafu. Podnieśmy do kwadratu macierz sąsiedztwa zgodnie z zasadami matematyki. Każdy element macierzy A 2 jest określony wzorem

a (2) ik = n j=1 a ij a jk

Wyrażenie we wzorze jest równe 1 wtedy i tylko wtedy, gdy obie liczby a ij i a jk są równe 1, w przeciwnym razie jest równe 0. Ponieważ równość a ij = a jk = 1 implikuje istnienie ścieżki o długości 2 od wierzchołka x i do wierzchołków k przechodzących przez wierzchołek x j , to (i-ty,k-ty) element macierzy A 2 jest równy liczbie ścieżek o długości 2 przechodzących od x i do k .

Tabela 4.1a przedstawia macierz sąsiedztwa wykresu pokazanego na ryc. 4.2. Wynik podniesienia do kwadratu macierzy sąsiedztwa A2 przedstawiono w tabeli 4.1b.

Tak więc „1”, stojąc na przecięciu drugiego rzędu i czwartej kolumny, wskazuje na istnienie jednej ścieżki o długości 2 od wierzchołka x 2 do wierzchołków 4 . Rzeczywiście, jak widzimy w kolumna na ryc. 4.2, jest taka ścieżka: a 6 , a 5 . „2” w macierzy A 2 wskazuje na istnienie dwóch ścieżek o długości 2 od wierzchołków 3 do wierzchołków 6: a 8 , a 4 i a 10 , a 3 .

Podobnie, dla macierzy sąsiedztwa podniesionej do trzeciej potęgi A 3 (tabela 4.1c), a (3) ik jest równe liczbie ścieżek o długości 3 biegnących od x i do x k . Z czwartego rzędu macierzy A 3 widać, że istnieją ścieżki o długości 3: jedna z x 4 w 4 (a 9 , a 8 , a 5), jedna z x 4 w

x 5 (a 9, a 10, a 6) i dwie ścieżki od x 4 na 6 (a 9, a 10, a 3 i a 9, a 8, a 4). Macierz A 4 pokazuje istnienie ścieżek o długości 4 (tabela 4.1d).

Tak więc, jeśli p ik jest elementem macierzy Ap, to p ik jest równe liczbie ścieżek (niekoniecznie lub łańcuchów lub prostych lub łańcuchów) o długości p przechodzącej od x i do x k .

DOSTĘPNOŚĆ I ŁĄCZNOŚĆ NA WYKRESACH Zarys wykładu: Ścieżki łańcucha i cykle. Wykres łączności i składników łączności. Średnica, promień i środek wykresu.

Udostępnij pracę w sieciach społecznościowych

Jeśli ta praca Ci nie odpowiada, na dole strony znajduje się lista podobnych prac. Możesz także użyć przycisku wyszukiwania

Baranow Wiktor Pawłowicz Dyskretna matematyka. Sekcja 3Wykresy, sieci, kody.

Wykład 8

Wykład 8 DOSTĘPNOŚĆ I ŁĄCZNOŚĆ NA WYKRESACH

Plan wykładu:

Trasy, łańcuchy i rowery.
Wykres łączności i składników łączności.
Średnica, promień i środek wykresu.
Macierze osiągalności i kontrosiągalności.

Trasy, obwody i pętle

Trasa zorientowana(lub przez ) dwugrafu to sekwencja łuków, w której wierzchołek końcowy dowolnego łuku innego niż ostatni jest wierzchołkiem początkowym następnego. Na ryc. 1 sekwencja łuku

, (1)

, (2)

(3)

są ścieżkami.

Ryż. jeden.

zorientowany łańcuch(lub orepio ) nazywana jest ścieżką, w której każdy łuk i z nie używany więcej niż jeden raz. Na przykład ścieżki (2) i (3) są lubłańcuchami, ale ścieżka (1) nie jest, ponieważ łuk jest w niej używany dwukrotnie.

Jedyny nazywa się łańcuchem, w którym każdy wierzchołek jest używany przez co najwyżej jeden o czasy. Na przykład orchain (3) jest prosty, ale orchain (2) nie.

Trasa jest nieskierowanym bliźniakiem ścieżki, tj. sekwencją krawędzi, w której każda krawędź, z wyjątkiem pierwszej i ostatniej, jest połączona wierzchołkami końcowymi z krawędziami i. Słupek nad symbolem łuku oznacza, że jest on traktowany jako krawędź.

Tak jak zdefiniowaliśmy lub łańcuchy i łańcuchy proste, możemy zdefiniować łańcuchy i łańcuchy proste.

Ścieżka lub trasa może być również reprezentowana przez sekwencję wierzchołków. Na przykład oraz takty, ścieżka (1) może być zapisana jako: .

Ścieżka nazywa się zamknięta , jeśli początkowy wierzchołek łuku pokrywa się z koniem h Noe wierzchołek łuku. Zamknięte lub łańcuchy (łańcuchy) nazywane są orcykle (cykle ). Orcykle są również nazywane kontury . Zamknięte proste łańcuszki (łańcuchy) zwane s proste orcykle(cykle). zamknięta trasajest niezorientowany n zamknięte podwójne na Ciebie.

Wykres Łączność i Komponenty Łączności

Mówi się, że wierzchołek w dwugrafie jest osiągalny z wierzchołka, jeśli istnieje ścieżka. Jeśli ponadto jest osiągalny z, wtedy mówi się, że te wierzchołki są wzajemnie osiągalne.

Dwuznak nazywa się silnie powiązanym lub silnym , jeśli dowolne dwa wierzchołki w nim są a imo osiągalne. Przykład silnego digrafu pokazano na ryc. 2a. Ponieważ w kolumnie mi biorąc pod uwagę orcykl, który zawiera wszystkie wierzchołki, brane są dowolne dwa z nich ale osiągalne.

° ° °

° ° ° ° ° °

a B C

Ryż. 2.

Digraf nazywa siępołączenie w jedną stronę lub jednostronne jeśli w dowolnej parze jego wierzchołków przynajmniej jeden jest osiągalny z drugiego. Przykład wykresu jednokierunkowego pokazano na ryc. 2b. Ten wykres ma orcykl, który zawiera cztery wzajemnie osiągalne wierzchołki. Wierzchołek ma stopień wejścia równy zero, co oznacza, że nie ma ścieżek prowadzących do tego wierzchołka. Co więcej, każdy z pozostałych czterech wierzchołków jest z niego osiągalny.

Digraf nazywa się luźno połączony lub słaby , jeśli zawiera dowolne dwa wierzchołki z o zjednoczeni w połowie drogi . Połowa ścieżki, w przeciwieństwie do ścieżki, może mieć przeciwny kierunek. w leniwe łuki. Przykład słabego digrafu pokazano na ryc. 2 cale Jest oczywiste, że wykres nie zawiera w ty między wierzchołkami i, ale istnieje półścieżka składająca się z przeciwnych n a rządzone łuki i.

Jeśli dla jakiejś pary wierzchołków nie ma trasy łączącej je, to t a który digraf nazywa się niespójny.

Dla digrafu zdefiniowane są trzy typy połączonych elementów:silny składnik– ma k najsilniejszy podgraf,element jednostronny- maksymalna pojedyncza o ronny podpunkt isłaby składnikjest najsłabszym podpunktem.

Koncepcję silnego komponentu ilustruje ryc. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Ryż. 3

Wykres, który jest połączony jednokierunkowo zawiera sześć silnych d wykresy, z których tylko i są silne składowe n tami. W podobny sposób zilustrowano koncepcję elementu jednokierunkowego. W tej notatce mi Składnik jednokierunkowy re jest taki sam jak sam wykres. Jeśli zmienimy orientację a łuk np. do przeciwnego, to otrzymujemy słaby wykres z dwoma jednostronnymi o komponenty czołowe, z których jeden tworzą wierzchołki, a drugi ve r opony.

Dla grafu nieskierowanego definiujemy na zbiorze jego wierzchołków bin R relacji, zakładając, że istnieje dowiązanie do łańcucha. Ta relacja jest a daje właściwości refleksyjności, symetrii i przechodniości, czyli chodzi o t noszenie ekwiwalentu. Dzieli zbiór wierzchołków na nieprzecinające się klasy: . Dwa wierzchołki z tej samej klasy są równoważne, to znaczy w grafie, który je łączy, nie ma takiego łańcucha dla wierzchołków z różnych klas. Od końca Yu Jeżeli krawędzie są ze sobą powiązane, to zbiór krawędzi grafu również zostanie podzielony na nieprzecinające się klasy: , gdzie zbiór wszystkich krawędzi, do których należą końce, jest oznaczony przez .

Wykresy są połączone i sumują się w wykres. Te wykresy nazywają sięelementy łącznościwykres. Liczba to kolejna numeryczna cecha wykresu. W przypadku połączonego wykresu, jeśli wykres jest odłączony, to.

Jeżeli dany graf nie jest połączony i dzieli się na kilka składowych, to rozwiązanie każdego pytania dotyczącego tego grafu z reguły można sprowadzić do badania poszczególnych składowych, które są ze sobą połączone. Dlatego w większości przypadków sensowne jest założenie, że dany wykres jest połączony.

Średnica, promień i środek wykresu

Dla połączonego wykresu definiujemy dystans między dwoma wierzchołkami i jako długość najkrótszego łańcucha łączącego te wierzchołki i oznaczonego przez. Długość łańcucha to liczba krawędzi, z których składa się łańcuch. Łatwo sprawdzić, czy wpisujesz n Ta odległość spełnia aksjomaty metryki:

2) ;

3) .

Określ odległość od każdego wierzchołka wykresu do najbardziej oddalonego od niego wierzchołka

który jest nazywanyekscentryczność. Oczywiście mimośród dla wszystkich wierzchołków w całym grafie jest równy jeden, a dla wierzchołków prostego cyklu - .

Maksymalna ekscentryczność nazywa sięśrednica wykres, a minimum - promień wykres. Na pełnym wykresie mamy, aw prostym cyklu - .

Wierzchołek nazywany jest centralnym if. Wykres może mieć kilka b takie wierzchołki, a na niektórych grafach wszystkie wierzchołki są centralne. W prostym łańcuchu, z nieparzystą liczbą wierzchołków, tylko jeden jest centralny, a przy parzystej liczbie wierzchołków z są dwa takie wierzchołki. W kompletnym wykresie i dla prostego cyklu wszystkie wierzchołki są centralne. Zbiór środkowych wierzchołków nazywa sięśrodek wykresu.

Przykład 1 Znajdź średnicę, promień i środek wykresu pokazanego na ryc. 4.

° °

° ° °

° °

Ryż. 4.

Aby rozwiązać ten problem, wygodnie jest wstępnie obliczyćmacierz odległości między blatami mi liczyć. W tym przypadku będzie to macierz wielkości, w której odległość od wierzchołka do wierzchołka jest na miejscu:

Dla każdego wiersza macierzy znajdujemy największy element i zapisujemy go za pomocą a wa od deski rozdzielczej. Największa z tych liczb jest równa średnicy wykresu, najmniejsza to p a dius wykresu. Środek wykresu tworzą środkowe wierzchołki i.

Koncepcje wierzchołka centralnego i środka grafu pojawiły się w związku z problematyką optymizmu. oraz niewielka lokalizacja punktów użyteczności publicznej takich jak szpitale, straż pożarna, posterunki porządku publicznego itp., gdy ważne jest zminimalizowanie oraz większa odległość od dowolnego punktu jakiejś sieci do najbliższego punktu serwisowego nija.

Macierze osiągalności i kontrosiągalności

Macierz osiągalnościdefiniuje się następująco:

Zbiór wierzchołków grafu osiągalnych z danego wierzchołka składa się z tych elementów, dla których th element macierzy wynosi 1. Zbiór ten można przedstawić jako

Macierz kontrosiągalności (odwrotna osiągalność) definiować następująco:

Podobnie jak w przypadku budowy zestawu dostępnego, można stworzyć zestaw o gest używając następującego wyrażenia:

Z definicji wynika, że -ta kolumna macierzy pokrywa się z -tym wierszem ma t , czyli gdzie jest macierz transponowana na macierz.

Przykład 2 Znajdź macierze osiągalności i kontrosiągalności dla wykresu itp. oraz pokazano na ryc. 5.

Ryż. 5.

Zdefiniujmy zbiory osiągalności dla wierzchołków grafu:

Dlatego macierze osiągalności i kontrosiągalności mają postać:

Ponieważ jest zbiorem takich wierzchołków, z których każdy należy do co najmniej jednej ścieżki prowadzącej od do, to wierzchołki tego zbioru są nazywane są niezbędne lub niezbywalne w odniesieniu do wierzchołków końcowych i. Wszystkie inne wierzchołki są nazywanenieistotny lub zbędne , ponieważ ich usunięcie nie wpływa na ścieżki z do.

Możesz także zdefiniować macierze ograniczony osiągalność i kontrosiągalność oraz mosty, jeśli wymagamy, aby długości ścieżek nie przekraczały określonej liczby. Wtedy będzie górna granica długości dopuszczalnych ścieżek.

Mówi się, że wykres jest przechodni jeśli z istnienia łuków i śladu w istnieje łuk.zamknięcie przechodniegraph to graf, gdzie jest minimalnym możliwym zbiorem łuków koniecznych do tego, aby graf był przechodni. Jest oczywiste, że macierz osiągalności grafu pokrywa się z macierzą sąsiedztwa grafu, jeśli umieścimy jednostki na głównej przekątnej w macierzy.

Wykres osiągalności

Jednym z pierwszych pytań, jakie pojawiają się w badaniu grafów, jest kwestia istnienia ścieżek pomiędzy danymi lub wszystkimi parami wierzchołków. Odpowiedzią na to pytanie jest powyższa relacja osiągalności na wierzchołkach grafu G=(V,E): wierzchołek w jest osiągalny z wierzchołka v, jeśli v = w lub istnieje ścieżka z v do w w G. Innymi słowy, relacja osiągalności jest zwrotnym i przechodnim zamknięciem relacji E. W przypadku grafów nieskierowanych relacja ta jest również symetryczna, a zatem jest relacją równoważności na zbiorze wierzchołków V. W grafie nieskierowanym klasy równoważności osiągalności to: zwane połączonymi komponentami. W przypadku grafów skierowanych osiągalność na ogół nie musi być relacją symetryczną. Wzajemna osiągalność jest symetryczna.

Definicja 9.8. Mówi się, że wierzchołki v i w grafu skierowanego G=(V,E) są wzajemnie osiągalne, jeśli G ma ścieżkę z v do w i ścieżkę z w do v.

Jest jasne, że relacja wzajemnej osiągalności jest zwrotna, symetryczna i przechodnia, a zatem jest równoważnością na zbiorze wierzchołków grafu. Klasy równoważności w odniesieniu do wzajemnej osiągalności nazywane są komponentami silnie powiązanymi lub podwójnie połączone komponenty wykres.

Rozważmy najpierw kwestię konstrukcji relacji osiągalności. Zdefiniujmy dla każdego grafu jego graf osiągalności (czasami nazywany także grafem przechodniego domknięcia), którego krawędzie odpowiadają ścieżkom oryginalnego grafu.

Definicja 9.9. Niech G=(V,E) będzie grafem skierowanym. Wykres osiągalności G * =(V,E *) dla G ma ten sam zestaw wierzchołków V i następujący zestaw krawędzi E * =( (u, v) | na grafie G wierzchołek v jest osiągalny z wierzchołka u).

Przykład 9.3. Rozważ wykres G z przykładu 9.2.

Ryż. 9.2. Hrabia G

Następnie możemy sprawdzić, czy wykres osiągalności G* dla G wygląda tak (nowe krawędzie pętli na każdym z wierzchołków 1-5 nie są pokazane):

Ryż. 9.3. Liczba G*

Jak można skonstruować graf G * z grafu G? Jednym ze sposobów jest określenie dla każdego wierzchołka grafu G zbioru wierzchołków osiągalnych z niego poprzez sekwencyjne dodawanie do niego wierzchołków osiągalnych z niego przez ścieżki o długości 0, 1, 2 i tak dalej.

Rozważymy inną metodę opartą na wykorzystaniu macierzy sąsiedztwa A G grafu G i operacji logicznych. Niech zbiór wierzchołków V=(v 1 , … , v n ). Wtedy macierz A G jest macierzą n × n Boole'a.

Poniżej, aby zachować podobieństwo do zwykłych operacji na macierzach, użyjemy notacji „arytmetycznej” dla operacji logicznych: alternatywę oznaczymy przez +, a spójnik przez ·.

Oznaczmy przez E n macierz jednostkową o rozmiarze n × n. Włóżmy . Niech Nasza procedura konstruowania G * będzie oparta na następującym stwierdzeniu.

Lemat 9.2. Niech będzie. Następnie

Dowód wykonajmy przez indukcję na k.

Podstawa. Dla k=0 i k=1, stwierdzenie jest z definicji prawdziwe i .

krok indukcji. Niech lemat będzie ważny dla k. Pokażmy, że obowiązuje również dla k+1. Z definicji mamy:

Załóżmy, że na wykresie G od v i do v j istnieje ścieżka o długości k+1. Rozważ najkrótszą z tych ścieżek. Jeżeli jego długość wynosi k, to zgodnie z hipotezą indukcyjną a_(ij)^((k))=1. Ponadto ajj (1) =1. Zatem a ij (k) a jj (1) =1 i a ij (k+1) =1. Jeśli długość najkrótszej drogi od v i do v j jest równa k+1, to niech v r będzie jej przedostatnim wierzchołkiem. Wtedy od v i do v r istnieje droga o długości k i zgodnie z hipotezą indukcyjną a ir (k) =1. Ponieważ (v r ,v j) E, to a_(rj)^((1))=1. Zatem a ir (k) a rj (1) =1 i a ij (k+1) =1.

I odwrotnie, jeśli a ij (k+1) =1, to dla co najmniej jednego r suma a ir (k) a rj (1) jest równa 1. Jeśli to jest r=j, wtedy a ij (k) = 1 i zgodnie z hipotezą indukcyjną, G ma ścieżkę od v i do vj o długości k. Jeśli rj, to a ir (k) =1 i a rj (1) =1. Oznacza to, że G ma ścieżkę od v i do v r o długości k i krawędź (v r ,v j) E. Łącząc je otrzymujemy ścieżkę od v i do v j o długości k+1.

Z lematów 9.1 i 9.2 otrzymujemy bezpośrednio

Konsekwencja 1. Niech G=(V,E) będzie grafem skierowanym o n wierzchołkach, a G * jego grafem osiągalności. Wtedy A_(G*) = . Dowód. Lemat 5.1 implikuje, że jeśli G ma ścieżkę z u do v u, to ma również prostą ścieżkę z u do v o długości n-1. A w lemacie 5.2 wszystkie takie ścieżki są reprezentowane w macierzy .

Zatem procedura konstruowania macierzy sąsiedztwa A G* grafu osiągalności dla G sprowadza się do podniesienia macierzy do potęgi n-1. Zróbmy kilka uwag, aby uprościć tę procedurę.

gdzie k jest najmniejszą liczbą taką, że 2 k n.

takie r jest takie, że a ir = 1 i a rj =1, to cała suma a ij (2) =1. Dlatego pozostałe warunki można zignorować.

Przykład 9.3. Rozważmy jako przykład obliczenie macierzy grafu osiągalności A G* dla grafu G przedstawionego w rys.9.2. W tym przypadku

Ponieważ G ma 6 wierzchołków, to . Obliczmy tę macierz:

i (ostatnia równość jest łatwa do sprawdzenia). Zatem,

Jak widać, ta macierz naprawdę definiuje wykres przedstawiony w rys.9.3.

Wzajemna osiągalność, silnie połączone komponenty i podstawy wykresów

Analogicznie do grafu osiągalności definiujemy graf o silnej osiągalności.

Definicja 9.10. Niech G=(V,E) będzie grafem skierowanym. Silnie osiągalny graf G * * =(V,E * *) dla G ma ten sam zestaw wierzchołków V i następujący zestaw krawędzi E * * =( (u, v) | w G, wierzchołki v i u są wzajemnie osiągalny).

Z macierzy grafu osiągalności łatwo jest skonstruować macierz silnego grafu osiągalności. Rzeczywiście, z definicji osiągalności i silnej osiągalności wynika bezpośrednio, że dla wszystkich par (i,j), 1 i,j n, wartość elementu jest równa 1 wtedy i tylko wtedy, gdy oba elementy A G* (i, j) a A G* (j, i) są równe 1, tj.

Na podstawie macierzy można wyróżnić silnie powiązane składowe grafu G w następujący sposób.

Umieśćmy w składowej K 1 wierzchołek v 1 i wszystkie wierzchołki v j takie, że A_(G_*^*)(1,j) = 1.

Niech składowe K 1 , …, K i oraz v k zostały już zbudowane - jest to wierzchołek o minimalnej liczbie, który nie został jeszcze uwzględniony w składowych. Następnie umieszczamy w składowej K_(i+1) wierzchołek v k i wszystkie takie wierzchołki v j ,

że A_(G_*^*)(k,j) = 1.

Powtarzaj krok (2), aż wszystkie wierzchołki zostaną rozdzielone między komponenty.

W naszym przykładzie dla wykresu G on rys.2 przez macierz otrzymujemy następującą macierz grafu silnej osiągalności

Korzystając z procedury opisanej powyżej, stwierdzamy, że wierzchołki grafu G są podzielone na 4 silnie powiązane składowe: K 1 = (v 1 , v 2 , v 3 ), \ K 2 =( v 4 ), \ K 3 = ( v 5 ), \ K 4 =( v 6 ). Na zbiorze silnie powiązanych komponentów definiujemy również relację osiągalności.

Definicja 9.11. Niech K i K" będą silnie związanymi składowymi grafu G. Składowa K osiągalny z składowych K^\prim jeśli K= K" lub istnieją dwa wierzchołki u K i v K" takie, że u jest osiągalne z v. K ściśle osiągalne od K^\prime, jeśli K K" i K jest osiągalny z K". Składnik K nazywa się minimum jeśli nie jest ściśle osiągalny z żadnego komponentu.

Ponieważ wszystkie wierzchołki w jednym komponencie są wzajemnie osiągalne, łatwo zauważyć, że relacje osiągalności i ścisłej osiągalności w komponentach nie zależą od wyboru wierzchołków u K i v K”.

Z definicji łatwo wywnioskować następującą cechę ścisłej osiągalności.

Lemat 9.3. Relacja ścisłej osiągalności jest relacją porządku częściowego, tj. jest antyrefleksyjna, antysymetryczna i przechodnia.

Relację tę można przedstawić jako graf skierowany, którego wierzchołkami są składowe, a krawędź (K", K) oznacza, że K jest ściśle osiągalny z K". Na Ryż. 9,4 ten wykres składników jest pokazany dla wykresu G rozważanego powyżej.

Ryż. 9.4.

W tym przypadku występuje jeden minimalny składnik K 2 .

W wielu zastosowaniach graf ukierunkowany jest siecią dystrybucji jakiegoś zasobu: produktu, produktu, informacji itp. W takich przypadkach naturalnie pojawia się problem znalezienia minimalnej liczby takich punktów (wierzchołków), z których ten zasób może być dostarczony do dowolnego punktu w sieci.

Definicja 9.12. Niech G=(V,E) będzie grafem skierowanym. Podzbiór wierzchołków W V nazywa się generatywny, jeśli z wierzchołków W można dotrzeć do dowolnego wierzchołka grafu. Podzbiór wierzchołków W V nazywany jest podstawą grafu, jeśli generuje, ale żaden z jego własnych podzbiorów nie generuje.

Poniższe twierdzenie pozwala sprawnie znaleźć wszystkie podstawy grafu.

Twierdzenie 9.1. Niech G=(V,E) będzie grafem skierowanym. Podzbiór wierzchołków W V jest bazą G wtedy i tylko wtedy, gdy zawiera jeden wierzchołek z każdej minimalnej silnie połączonej składowej G i nie zawiera żadnych innych wierzchołków.

Dowód Zauważ najpierw, że każdy wierzchołek grafu jest osiągalny z wierzchołka, który należy do jakiegoś minimalnego komponentu. Generuje się zatem zbiór wierzchołków W zawierający jeden wierzchołek z każdego minimalnego komponentu, a kiedy jakikolwiek wierzchołek zostanie z niego usunięty, przestaje nim być, ponieważ wierzchołki z odpowiadającego mu minimalnego komponentu stają się nieosiągalne. Dlatego W jest bazą.

I odwrotnie, jeśli W jest bazą, to musi zawierać co najmniej jeden wierzchołek z każdego minimalnego komponentu, w przeciwnym razie wierzchołki takiego minimalnego komponentu będą niedostępne. W nie może zawierać żadnych innych wierzchołków, ponieważ każdy z nich jest osiągalny z już zawartych wierzchołków.

Twierdzenie to implikuje następującą procedurę konstruowania jednej lub listy wszystkich podstaw grafu G.

Znajdź wszystkie silnie połączone komponenty G.

Określ na nich kolejność i wybierz komponenty, które są minimalne w stosunku do tej kolejności.

Wygeneruj jedną lub wszystkie podstawy wykresu, wybierając jeden wierzchołek z każdego minimalnego składnika.

Przykład 9.5. Definiujemy wszystkie podstawy grafu skierowanego G pokazanego w rys.9.5.

Ryż. 9.5. Hrabia G

W pierwszym etapie znajdujemy silnie powiązane komponenty G:

W drugim etapie konstruujemy ścisły wykres osiągalności tych komponentów.

Ryż. 9.6. Wykres zależności osiągalności na składnikach G

Określamy minimalne składowe: K 2 = ( b ), K 4 =( d, e, f, g) i K 7 = ( r).

Na koniec wymieniamy wszystkie cztery zasady G: B 1 = ( b, d, r), B 2 = ( b, e, r), B 3 = ( b, f, r) i B 1 = ( b, g , r).

Zadania

Problem 9.1. Udowodnij, że suma stopni wszystkich wierzchołków dowolnego grafu skierowanego jest parzysta.

Problem ten ma popularną interpretację: udowodnić, że łączna liczba uścisków dłoni wymienianych przez osoby, które przyszły na imprezę, jest zawsze parzysta.

Problem 9.2. Wymień wszystkie nieizomorficzne grafy nieskierowane, które mają co najwyżej cztery wierzchołki.

Problem 9.3. Udowodnij, że graf spójny nieskierowany pozostaje połączony po usunięciu pewnej krawędzi ↔ ta krawędź należy do pewnego cyklu.

Problem 9.4. Udowodnij, że graf spójny nieskierowany o n wierzchołkach

zawiera co najmniej n-1 krawędzi,

jeśli zawiera więcej niż n-1 krawędzi, to ma co najmniej jeden cykl.

Problem 9.5. Udowodnij, że w każdej grupie 6 osób jest trzech znajomych w parach lub trzech nieznajomych w parach.

Problem 9.6. Wykazać, że graf nieskierowany G=(V,E) jest połączony ↔ dla każdego podziału V= V 1 V 2 z niepustym V 1 i V 2 istnieje krawędź łącząca V 1 z V 2 .

Problem 9.7. Udowodnij, że jeśli w grafie nieskierowanym znajdują się dokładnie dwa wierzchołki nieparzystego stopnia, to są one połączone ścieżką.

Problem 9.8. Niech G=(V,E) będzie grafem nieskierowanym z |E|< |V|-1. Докажите, что тогда G несвязный граф.

Problem 9.9. Udowodnij, że dowolne dwie proste ścieżki o maksymalnej długości w połączonym grafie nieskierowanym mają wspólny wierzchołek.

Problem 9.10. Niech graf nieskierowany bez pętli G=(V,E) ma k połączonych składowych. Udowodnij, że wtedy

Problem 9.11. Określ, do czego służy wykres osiągalności

graf o n wierzchołkach i pustym zbiorze krawędzi;

graf o n wierzchołkach: V= (v 1 ,… , v n ), którego krawędzie tworzą cykl:

Problem 9.12. Oblicz macierz wykresu osiągalności dla wykresu

i skonstruuj odpowiedni wykres osiągalności. Znajdź wszystkie podstawy grafu G.

Problem 9.13. Zbuduj dla danego dnia Ryż. 9,7 graf skierowany G1 =(V,E) jego macierz sąsiedztwa A G1, macierz padania B G1 i listy sąsiedztwa. Oblicz macierz osiągalności A G1* i skonstruuj odpowiadający jej wykres osiągalności G 1 * .

Ryż. 9.7.

Drzewa nieskierowane i zorientowane

Drzewa to jedna z ciekawszych klas grafów wykorzystywanych do reprezentowania różnego rodzaju struktur hierarchicznych.

Definicja 10.1. Graf nieskierowany nazywany jest drzewem, jeśli jest połączony i nie zawiera cykli.

Definicja 10.2. Graf skierowany G=(V,E) nazywamy drzewem (skierowanym), jeśli

Na Ryż. 10.1 pokazano przykłady drzewa nieskierowanego G1 i drzewa ukierunkowanego G2. Zauważ, że drzewo G 2 uzyskuje się z G 1, wybierając wierzchołek c jako korzeń i orientując wszystkie krawędzie w kierunku „od korzenia”.

Ryż. 10.1. Drzewa nieskierowane i ukierunkowane

To nie przypadek. Udowodnij sobie następujące twierdzenie dotyczące związku między drzewami nieskierowanymi i skierowanymi.

Lemat 10.1. Jeżeli w jakimkolwiek drzewie nieskierowanym G=(V,E) wybieramy dowolny wierzchołek v V jako korzeń i orientujemy wszystkie krawędzie w kierunku „od korzenia”, tj. uczyń v początkiem wszystkich krawędzi, które do niego dochodzą, wierzchołki sąsiadujące z v - początkami wszystkich jeszcze nie skierowanych krawędzi, które pochodzą z v, itd., to wynikowy graf skierowany G" będzie drzewem skierowanym.

Drzewa nieskierowane i ukierunkowane mają wiele równoważnych cech.

Twierdzenie 10.1. Niech G=(V,E) będzie grafem nieskierowanym. Wtedy następujące warunki są równoważne.

G to drzewo.

Dla dowolnych dwóch wierzchołków w G istnieje unikalna ścieżka łącząca je.

G jest połączone, ale gdy jakakolwiek krawędź zostanie usunięta z E, przestaje być połączony.

G jest połączone i |E| = |V| -jeden.

G jest acykliczny i |E| = |V| -jeden.

G jest acykliczny, ale dodanie dowolnej krawędzi do E generuje cykl.

Dowód(1) (2): Gdyby jakieś dwa wierzchołki w G były połączone dwiema ścieżkami, to oczywiście w G byłby cykl. Ale to jest sprzeczne z definicją drzewa w (1).

(2) (3): Jeśli G jest połączone, ale E pozostaje połączone, gdy część krawędzi (u,v) zostanie usunięta, to istnieje ścieżka między u i v, która nie zawiera tej krawędzi. Ale wtedy G ma co najmniej dwie ścieżki łączące u i v, co jest sprzeczne z warunkiem (2).

(3) (4): Dostarczone do czytnika (patrz problem 9.4).

(4) (5): Jeśli G zawiera cykl i jest spójny, to usuwając jakąkolwiek krawędź z cyklu, spójność nie powinna być zerwana, ale krawędzie pozostają |E|= V -2, i przez Problem 9.4(a ), połączony wykres musi mieć co najmniej żebra V-1. Wynikająca z tego sprzeczność pokazuje, że w G nie ma cykli i warunek (5) jest spełniony.

(5) (6): Załóżmy, że dodanie krawędzi (u,v) do E nie spowodowało powstania cyklu. Wtedy wierzchołki u i v w G są w różnych połączonych składowych. Skoro |E|= V -1, to w jednej z tych składowych niech będzie (V 1 ,E 1), liczba krawędzi i liczba wierzchołków są takie same: |E 1 |=|V 1 |. Ale wtedy zawiera cykl (patrz Problem 9.4(b)), co przeczy faktowi, że G jest acykliczny.

(6) (1): Gdyby G nie były połączone, to byłyby dwa wierzchołki u i v z różnych połączonych komponentów. Wówczas dodanie krawędzi (u,v) do E nie prowadziłoby do pojawienia się cyklu, co zaprzecza (6). Stąd G jest połączone i jest drzewem.

W przypadku drzew skierowanych często wygodnie jest użyć poniższej definicji indukcyjnej.

Definicja 10.3. Definiujemy przez indukcję klasę grafów skierowanych zwanych drzewami. Jednocześnie dla każdego z nich definiujemy wybrany wierzchołek - korzeń.

Ryż. 10.2 ilustruje tę definicję.

Ryż. 10.2. Indukcyjna definicja drzew skierowanych

Twierdzenie 10.2. Definicje drzew skierowanych 10.2 i 10.3 są równoważne.

Dowód Niech graf G=(V,E) spełnia warunki definicji 10.2. Pokażmy przez indukcję na liczbie wierzchołków |V|, że .

Jeśli |V|=1, to jedynym wierzchołkiem v V jest korzeń drzewa według właściwości (1), tj. na tym wykresie nie ma krawędzi: E = . Następnie .

Załóżmy, że dowolny graf z n wierzchołkami, który spełnia definicję 10.2 jest zawarty w . Niech graf G=(V,E) z (n+1)-tym wierzchołkiem spełnia warunki definicji 10.2. Zgodnie z warunkiem (1) ma wierzchołek korzenia r 0 . Niech k krawędzi wyłania się z r 0 i prowadzą do wierzchołków r 1 , … , r k (k 1). Oznaczmy przez G i ,(i=1, …, k) graf, który zawiera wierzchołki V i =( v V|v \textit( osiągalne z )r i ) oraz łączące je krawędzie E i E. Łatwo to zobaczyć że Gi spełnia warunki definicji 10.2. Rzeczywiście, r i nie zawiera krawędzi, tj. ten wierzchołek jest pierwiastkiem G i . Każdy z pozostałych wierzchołków z V i ma jedną krawędź, tak jak G . Jeśli v V i , to jest osiągalny od pierwiastka r i zgodnie z definicją grafu G i . Ponieważ |V i | n, a następnie przez hipotezę indukcyjną . Wtedy graf G otrzymuje się z reguły indukcyjnej (2) definicji 10.3 z drzew G 1 , …, G k i dlatego należy do klasy .

⇐ Jeżeli jakiś graf G=(V,E) należy do klasy , to spełnienie warunków (1)-(3) z Definicji 10.2 może być łatwo ustalone przez indukcję z Definicji 10.2. Pozostawiamy to czytelnikowi jako ćwiczenie.

Istnieje bogata terminologia związana z drzewami zorientowanymi, pochodząca z dwóch źródeł: botaniki i dziedziny relacji rodzinnych.

Korzeń to jedyny wierzchołek, który nie ma krawędzi, liście to wierzchołki, które nie mają krawędzi. Ścieżka od korzenia do liścia nazywana jest gałęzią drzewa. Wysokość drzewa to maksymalna długość jego gałęzi. Głębokość wierzchołka to długość ścieżki od korzenia do tego wierzchołka. Dla wierzchołka v V, podgraf drzewa T=(V,E), który zawiera wszystkie wierzchołki osiągalne z v i łączące je krawędzie z E, tworzy poddrzewo T v drzewa T z korzeniem v (patrz Problem 10.3 ). Wysokość v jest wysokością drzewa T v . Wykres, który jest sumą kilku nie przecinających się drzew, nazywa się lasem.

Jeśli krawędź prowadzi od wierzchołka v do wierzchołka w, to v nazywa się ojciec w, i w - syn v (ostatnio w literaturze anglojęzycznej używa się bezpłciowej pary terminów: rodzic – dziecko). Z definicji drzewa wynika wprost, że każdy wierzchołek ma oprócz korzenia innego ojca. Jeśli ścieżka prowadzi od wierzchołka v do wierzchołka w, to v nazywamy przodkiem w, a w potomkiem v. Wierzchołki, które mają wspólnego ojca, nazywają się bracia lub siostry.

Wyróżniamy jeszcze jedną klasę grafów, która uogólnia drzewa skierowane - skierowane acykliczne. Poniżej zostaną użyte dwa rodzaje takich oznaczonych wykresów do reprezentowania funkcji logicznych. Wykresy te mogą mieć kilka pierwiastków - wierzchołki, które nie zawierają krawędzi, a każdy wierzchołek może mieć kilka krawędzi, a nie jedną, jak w przypadku drzew.

komputer technologia, w szczególności program ... 2009 roku Szkoła podstawowa to miejsce eksperymentalne na wprowadzenie Federalnej stan ...

MEDIA MONITORINGU Modernizacja szkolnictwa zawodowego marzec - sierpień 2011

Streszczenie

Zjednoczony stan egzaminy" na wybór: informacyjny komputertechnologia, biologia i literatura. Swoją drogą, w tym rok POSŁUGIWAĆ SIĘ... pytanie„O wynikach wdrożenia programy rozwój krajowych uczelni badawczych w 2009 -2010 lata". ...

STRATEGICZNY PROGRAM ROZWOJU Tver 2011

Program

W 2009 rok. Zmiany strukturalne widoczne w 2010 r. rokna w kierunku 2009 , ... Zawodowo – zorientowany język obcy”, „Nowoczesna edukacja technologia". W każdym program zaawansowany moduł szkoleniowy " Stan ...

Analogicznie do grafu osiągalności definiujemy graf o silnej osiągalności.

Definicja: Niech będzie grafem skierowanym. Silny wykres osiągalności
dla ma również wiele wierzchołków i następny zestaw krawędzi
w kolumnie szczyty oraz wzajemnie dostępne.

Według macierzy wykresu osiągalności
łatwe do zbudowania matrycy
wykres silnej osiągalności. Rzeczywiście, z definicji osiągalności i silnej osiągalności wynika bezpośrednio, że dla wszystkich par
,
, wartość elementu
równa się 1 wtedy i tylko wtedy, gdy oba elementy
oraz
są równe 1, tj.

Według macierzy
można wyróżnić silnie powiązane składowe grafu w następujący sposób:

Powtarzaj drugi krok, aż wszystkie wierzchołki zostaną rozdzielone między komponenty.

W naszym przykładzie dla wykresu przykład 14.1. przez macierz
otrzymujemy następującą macierz grafu silnej osiągalności

Korzystając z procedury opisanej powyżej, stwierdzamy, że wierzchołki grafu podzielone są na 4 silnie połączone elementy:
,
,
,
. Na zbiorze silnie powiązanych komponentów definiujemy również relację osiągalności.

Definicja: Zostawiać
oraz
są silnie powiązanymi składowymi grafu . Składnik
osiągalny z komponentu
, jeśli
czy są dwa takie wierzchołki
oraz
, Co osiągalny z .
ściśle osiągalne od
, jeśli
oraz
osiągalny z
. Składnik
nazywana jest minimalna, jeśli nie jest ściśle osiągalna z żadnego komponentu.

Z definicji łatwo wywnioskować następującą cechę ścisłej osiągalności.

Lemat: Relacja ścisłej osiągalności jest relacją porządku częściowego, tj. jest antyrefleksyjna, antysymetryczna i przechodnia.

Relację tę można przedstawić jako graf skierowany, którego wierzchołkami są składowe, a krawędź
oznacza, że
ściśle osiągalne od
. Wykres składowy dla przykładu 14.1 pokazano poniżej.

W tym przypadku jest jeden minimalny składnik
.

Definicja: Zostawiać
jest grafem skierowanym. Podzbiór wierzchołków
nazywa generatywny jeśli z wierzchołków
można osiągnąć dowolny wierzchołek wykresu. Podzbiór wierzchołków
nazywa się podstawą grafu, jeśli generuje, ale nie generuje żadnego odpowiedniego podzbioru.

Poniższe twierdzenie pozwala sprawnie znaleźć wszystkie podstawy grafu.

Twierdzenie: Zostawiać
jest grafem skierowanym. Podzbiór wierzchołków
jest podstawą wtedy i tylko wtedy, gdy zawiera jeden wierzchołek z każdego z minimalnych silnie połączonych komponentów i nie zawiera żadnych innych wierzchołków.

Dowód: zauważ najpierw, że każdy wierzchołek grafu jest osiągalny z wierzchołka, który należy do jakiegoś minimalnego komponentu. Dlatego zbiór wierzchołków
, zawierający jeden wierzchołek z każdego minimalnego komponentu, generuje się, a kiedy dowolny wierzchołek zostanie z niego usunięty, przestaje nim być, ponieważ wierzchołki z odpowiadającego mu minimalnego komponentu stają się nieosiągalne. Więc
jest podstawą.

I odwrotnie, jeśli
jest bazą, to musi zawierać co najmniej jeden wierzchołek z każdego minimalnego komponentu, w przeciwnym razie wierzchołki takiego minimalnego komponentu będą niedostępne. Żadnych innych szczytów
nie może zawierać, ponieważ każdy z nich jest osiągalny z już zawartych wierzchołków.