By w pełni zrozumieć zagadnienia poruszane w tym rozdziale, musimy znać kilka podstawowych pojęć:

• stopień grafu,

• stopień wierzchołka grafu,

• spójność grafu.

Zaczniemy od stopnia grafu – jest on równy maksymalnemu stopniowi wierzchołka w tym grafie.

Stopniem wierzchołka grafu nieskierowanego nazywamy liczbę krawędzi z nim incydentnych.

Stopniem wierzchołka grafu skierowanego nazywamy sumę dwóch liczb – liczby krawędzi do niego wchodzących (stopień wejściowy) oraz liczby krawędzi z niego wychodzących (stopień wyjściowy).

O grafie mówimy, że jest spójny, jeśli dla każdych dwóch jego wierzchołków istnieje ścieżka, która je ze sobą łączy.

Graf nieskierowany jest spójny, jeśli dla każdej pary wierzchołków istnieje ścieżka, która je łączy. Jeśli takiej ścieżki nie ma, wówczas taki graf określamy niespójnym.

O grafie skierowanym możemy powiedzieć, że jest grafem spójnym, jeśli po tym, jak wszystkie jego krawędzie skierowane zostaną zastąpione krawędziami nieskierowanymi, graf ten będzie grafem nieskierowanym spójnym,

Przykład 1

Zapoznaj się z przykładem grafu nieskierowanego, który nie jest spójny (składa się z trzech spójnych składowych).

R1F2Y4l34n02y

Niespójny graf o trzech spójnych składowych.
1: O połączeniach: A, C.
B, C.
A, C.
2: O połączeniach: F, E.
E, D.
F, D.
3: O połączeniach: G, H.

Spójny podgraf takiego grafu, który nie jest zawarty w żadnym większym spójnym podgrafie, nazywamy składową grafu. Możemy zauważyć, że każdy graf niespójny jest sumą pewnych spójnych grafów.

Przyjrzyjmy się grafom z Przykładu 1. Dane są trzy grafy spójne nieskierowane. Ich suma daje graf nieskierowany niespójny.

W kontekście spójności grafów definiujemy również pojęcie mostu, czyli krawędzi, której usunięcie sprawi, że graf zwiększy liczbę spójnych składowych o jeden.

R1VzXDO2cWEv9

Ilustracja przedstawia graf o połączeniach:
C, A.
A, B.
C, B.
Krawędź mostu: B, E.
F, E.
F, D.
E, D.
F, G.
D, H.
H, G.
Drugi graf jest taki sam lecz nie posiada krawędzi mostu.

Pojęcie mostu jest podstawą działania niektórych algorytmów grafowych, takich jak na przykład algorytm Fleury'ego służący do znajdowania w grafie ścieżki lub cyklu Eulera.

Przykład 2

Zaprezentowany graf to graf spójny, którego wierzchołki mają następujące stopnie:

• stopień wierzchołka 0: 3

• stopień wierzchołka 1: 2

• stopień wierzchołka 2: 4

• stopień wierzchołka 3: 2

• stopień wierzchołka 4: 3

• stopień wierzchołka 5: 2

Tym samym stopień grafu wynosi 4 (ponieważ tyle wynosi maksymalny stopień wierzchołka grafu).

RlfB6l1pznJKy

Ilustracja przedstawia cztery punkty oznaczone dużymi literami a, b, c, d. resztę odcinków oznaczono małymi literami, prostą bd oznaczono jako f, prostą cd oznaczono g, prostą ad oznaczono e. dwie krzywe ab oznaczono jako a i b, dwie krzywe ac oznaczono c i d, każda z dwóch krzywych jest skierowana w stronę prostej e a druga w przeciwną stronę.

Już wiesz

Spójrzmy, jak wygląda graf przedstawiający mosty i lądy w Królewcu z czasów Eulera .

Rhc8uOvNVtNsd

Ilustracja przedstawia cztery punkty oznaczone dużymi literami a, b, c, d. resztę odcinków oznaczono małymi literami, prostą bd oznaczono jako f, prostą cd oznaczono g, prostą ad oznaczono e. dwie krzywe ab oznaczono jako a i b, dwie krzywe ac oznaczono c i d, każda z dwóch krzywych jest skierowana w stronę prostej e a druga w przeciwną stronę.

W teorii grafów taka ścieżka zamknięta nazywana jest cyklem Eulera. O ścieżce mówimy, że jest zamknięta, jeśli wierzchołek początkowy jest tożsamy z jej wierzchołkiem końcowym.

Warunki istnienia cyklu Eulera w grafie określa następujące twierdzenie:

Spójny graf zawiera cykl Eulera wtedy i tylko wtedy, gdy każdy wierzchołek jest parzystego stopnia.

Warunkiem koniecznym istnienia cyklu Eulera jest spójność grafu. Gdyby graf nie był spójny, nie istniałaby możliwość odwiedzenia wszystkich jego wierzchołków w jednym cyklu.

Digrafy

Digraf (inaczej graf skierowany) to taki graf, w którym krawędzie mają ustalony kierunek z jednego wierzchołka do drugiego. Na rysunku zwykle jest to oznaczane strzałką w jednym z końców krawędzi. Formalnie powiemy, że grafem skierowanym (digrafem) $D$ nazywamy graf składający się z niepustego i skończonego zbioru wierzchołków $V(D)$ oraz skończonej rodziny krawędzi $A(D)$, czyli z uporządkowanych par elementów zbioru $V(D)$.

Dla zaprezentowanego grafu zbiór wierzchołków to $V = {A, B, C, D, E}$. Rodzina krawędzi to następujące pary: $AB, AD, CB, DA, DE, DC, EC$.

RUidT1OAFZJY1

Ilustracja przedstawia graf skierowany.
D, E.
D, C.
E, C.
C, B.
A, B.
A, D.
D, A.

Jeśli $A$ i $B$ są wierzchołkami, to krawędź skierowana $A→B$ jest parą uporządkowaną i oznacza krawędź poprowadzoną z wierzchołka $A$ do wierzchołka $B$. Jeśli w pewnym grafie istnieją krawędzie skierowane $A→B$ i $B→A$, to nie są one krawędziami wielokrotnymi, ponieważ tutaj uwzględniamy kolejność wierzchołków.

Poruszanie się po krawędziach wychodzących

Stopniem wyjściowym wierzchołka $A$ digrafu nazywamy liczbę krawędzi skierowanych, wychodzących z wierzchołka $A$. Stopień wyjściowy wierzchołka $A$ oznaczamy symbolem:

$\text{outdeg}(A)$

Analogicznie, stopniem wejściowym wierzchołka $B$ w digrafie będzie liczba krawędzi skierowanych, poprowadzonych do wierzchołka $B$. Liczbę taką oznaczamy symbolem:

$\text{indeg}(B)$

W digrafach możemy przechodzić przez krawędzie tylko w kierunku zgodnym z kolejnością wierzchołków krawędzi. Na przykład krawędź skierowaną $A→B$ można przejść tylko od $A$ do $B$, natomiast odwrotne przejście jest niemożliwe.

Dla zaprezentowanego wyżej grafu stopień wejściowy wierzchołka $A$ to 1 (do wierzchołka $A$ skierowana jest tylko jedna krawędź), natomiast stopień wyjściowy wierzchołka $A$ to 2 (z wierzchołka wychodzą dwie krawędzie).

Spójność digrafów

Ponieważ w digrafach przechodzimy po danej krawędzi w ściśle określonym kierunku, może dojść do sytuacji, że z pewnego wierzchołka nie dostaniemy się do drugiego.

Rmw4TH9TChPk3

Ilustracja przedstawia graf skierowany o połączeniach:
C, B.
A, C.
B, A.
B, E.
E, G.
G, D.
D, F.
F, E.
G, F.
D, H.
Okręgami z przerywanej linii zaznaczono węzły gdzie każdy jest dostępny z każdego wierzchołka.

Mówimy, że podgraf skierowany jest silnie spójną składową, jeśli każdy wierzchołek jest osiągalny z każdego innego wierzchołka składowej - czyli z każdego wierzchołka możemy poprowadzić ścieżkę do dowolnego wierzchołka.

Dla zaprezentowanego grafu możemy wyróżnić trzy podgrafy, które są silnie spójnymi składowymi. Otoczono je przerywanymi liniami.

Badanie stopnia wierzchołka grafu

Graf nieskierowany

Specyfikacja problemu:

Dane:

• macierz_sasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych

Wynik:

• wypisane stopnie poszczególnych wierzchołków

Dany jest następujący graf spójny nieskierowany bez wag:

R1OA3UoJEctUA

Ilustracja przedstawia pięciokąt wypukły. Jego wierzchołki są oznaczone kolejno cyframi 4, 0, 1, 2, 5. Wierzchołek 4 oraz 1 jest połączony przekątną, tak samo jak wierzchołek 2 i 0. Z wierzchołka 4 oraz 2 wychodzą proste, które spotykają się w punkcie oznaczonym 3, który znajduje się wewnątrz figury. Wszystkie wierzchołki i punkty są oznaczone niebieskimi kółkami.

Jego macierz sąsiedztwa:

R1eJLJbnGIkP5

Ilustracja przedstawia tabelkę sześć na sześć kratek. Jej kolumny i rzędy są oznaczone cyframi od 0 do 5. W pierwszym rzędzie wpisano 0, 1, 1, 0, 1, 0, w drugim rzędzie 1, 0, 1, 0, 1, 0, w trzecim rzędzie, 1, 1, 0, 1, 0, 1, w czwartym rzędzie 0, 0, 1, 0, 1, 0, w piątym rzędzie 1, 1, 0, 1, 0, 1, w szóstym rzędzie 0, 0, 1, 0, 1, 0.

Implementacja zaprezentowanej macierzy sąsiedztwa w języku Python:

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [1, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 0]
]

Zapiszmy funkcję odpowiedzialną za określenie stopni poszczególnych wierzchołków.

Zaczniemy od zapisania nagłówka funkcji. Funkcja przyjmuje jeden argument – macierz sąsiedztwa grafu.

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa):

W kolejnym kroku tworzymy zmienną n przechowującą długość listy macierz_sasiedztwa (liczbę wierzchołków) oraz listę stopnie o długości równej liczbie wierzchołków grafu. Listę wypełniamy zerami. Będzie ona przechowywać stopnie kolejnych wierzchołków.

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)
    stopnie = [0] * n

Zapisujemy pętlę for, która będzie iterować przez wszystkie wierzchołki (wiersze).

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)
    stopnie = [0] * n
    for i in range(n):

Zapisujemy zagnieżdżoną pętlę for, która będzie iterowała przez pozostałe wierzchołki grafu (kolumny w danym wierszu).

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)
    stopnie = [0] * n
    for i in range(n):
        for j in range(n):

W pętli zapisujemy instrukcję warunkową, za pomocą której sprawdzimy, czy wierzchołki o danych indeksach są połączone krawędzią. Jeśli tak, zwiększamy stopień i-tego wierzchołka, czyli inkrementujemy wartość i-tego elementu listy stopnie.

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)
    stopnie = [0] * n
    for i in range(n):
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1

Dodajemy kolejną instrukcję warunkową, która obsłuży przypadek, w którym krawędź jest pętlą – wtedy liczymy ją podwójnie – ponownie inkrementujemy i-ty element listy stopnie.

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)
    stopnie = [0] * n
    for i in range(n):
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1
                if i == j:
                    stopnie[i] += 1

Kompletny kod programu:

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)
    stopnie = [0] * n
    for i in range(n):
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1
                if i == j:
                    stopnie[i] += 1

    print("Stopnie (graf nieskierowany):")
    for i in range(n):
        print("indeks wierzcholka:", i, "stopien:", stopnie[i])

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [1, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 0]
]

stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa)

Wynik działania programu:

Stopnie (nieskierowany): 
indeks wierzcholka: 0 stopien: 3
indeks wierzcholka: 1 stopien: 3
indeks wierzcholka: 2 stopien: 4
indeks wierzcholka: 3 stopien: 2
indeks wierzcholka: 4 stopien: 4
indeks wierzcholka: 5 stopien: 2

Graf skierowany

Specyfikacja problemu:

Dane:

• macierz_sasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych

Wynik:

• wypisane stopnie poszczególnych wierzchołków (sumy stopni wierzchołków wejściowych i wyjściowych)

Dany jest następujący graf spójny skierowany bez wag:

R51LJ4e2RonN5

Ilustracja przedstawia pięciokąt wypukły. Jego wierzchołki są oznaczone kolejno cyframi 4, 0, 1, 2, 5. Wierzchołek 4 oraz 1 jest połączony strzałką, tak samo jak wierzchołek 2 i 0. Z 2 wychodzi strzałka, która prowadzi do punktu oznaczonego 3, który znajduje się wewnątrz figury. Od punktu 3 do punktu 4 również prowadzi strzałka. Wszystkie wierzchołki i punkty są oznaczone niebieskimi kółkami. Od punktu 0 do punktu 4 prowadzi strzałka oznaczona e2, od punktu 0 do punktu 1 prowadzi strzałka oznaczona e0, od punktu 0 do punktu 2 prowadzi strzałka oznaczona e2. Od punktu 1 do punktu 2 prowadzi strzałka oznaczona e3, od punktu 1 do punktu 4 prowadzi strzałka oznaczona e4. Od punktu 2 do punktu 3 prowadzi strzałka oznaczona e5, od punktu 2 do punktu 5 prowadzi strzałka oznaczona e6. Od punktu 3 do punktu 4 prowadzi strzałka oznaczona e7, punkty 4 i 5 łączy strzałka grotami na obu jej końcach oznaczona e8 i e9.

Macierz sąsiedztwa grafu:

R12LrCWhJbLTN

Ilustracja przedstawia tabelkę sześć na sześć kratek. Jej kolumny i rzędy są oznaczone cyframi od 0 do 5. W pierwszym rzędzie wpisano 0, 1, 1, 0, 1, 0, w drugim rzędzie 1, 0, 1, 0, 1, 0, w trzecim rzędzie, 1, 1, 0, 1, 0, 1, w czwartym rzędzie 0, 0, 1, 0, 1, 0, w piątym rzędzie 1, 1, 0, 1, 0, 1, w szóstym rzędzie 0, 0, 1, 0, 1, 0.

Implementacja zaprezentowanej macierzy sąsiedztwa w języku Python:

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0]
]

Zapiszmy funkcję odpowiedzialną za określenie stopni poszczególnych wierzchołków. W przypadku tej implementacji nie będziemy rozróżniać stopni wejściowych oraz wyjściowych. Stopień wierzchołka będzie równy sumie stopni wejściowych i wyjściowych wierzchołka.

W przypadku prezentowanego programu będziemy obliczać sumę stopni wejściowych oraz wyjściowych dla każdego wierzchołka.

Zaczniemy od zapisania nagłówka funkcji. Funkcja przyjmuje jeden argument – macierz sąsiedztwa.

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa):

Zmiennej n przypisujemy wartość równą liczbie wierzchołków.

W kolejnym kroku tworzymy listę stopnie o długości równej n. Listę wypełniamy zerami. Będzie ona przechowywać stopnie kolejnych wierzchołków.

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)    
    stopnie = [0] * n

Zapisujemy pętlę for, która będzie iterować przez wszystkie wierzchołki (wiersze).

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)    
    stopnie = [0] * n
    for i in range(n):

Zapisujemy zagnieżdżoną pętlę for, która będzie iterowała przez pozostałe wierzchołki grafu (kolumny w danym wierszu) – w pętli sprawdzimy, czy istnieje krawędź między wierzchołkiem o indeksie i a j.

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)    
    stopnie = [0] * n
    for i in range(n):
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:

W pętli zapisujemy zatem instrukcję warunkową, za pomocą której sprawdzimy, czy wierzchołki o danych indeksach (i oraz j) są połączone krawędzią. Jeśli tak, zwiększamy stopnie i-tego (ponieważ ma on krawędź wychodzącą) oraz j-tego wierzchołka (ponieważ ma on krawędź wchodzącą), czyli inkrementujemy wartości i-tego oraz j‑tego elementu listy stopnie.

Stopień wierzchołka w grafie skierowanym definiujemy w tym przypadku jako sumę krawędzi wchodzących do wierzchołka i wychodzących z wierzchołka.

Zatem jeśli istnieje krawędź między wierzchołkami i oraz j, to dla wierzchołka i jest to krawędź wyjściowa, a dla wierzchołka j – wejściowa.

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)    
    stopnie = [0] * n
    for i in range(n):
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1
                stopnie[j] += 1

Kompletny kod programu:

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa)    
    stopnie = [0] * n
    for i in range(n):
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1
                stopnie[j] += 1

    print("Stopnie (graf skierowany):")
    for i in range(n):
        print("indeks wierzcholka:", i, "stopien:", stopnie[i])
    print()

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0]
]

stopnie_w_grafie_skierowanym(macierz_sasiedztwa)

Wynik działania programu:

Stopnie (graf skierowany):
indeks wierzcholka: 0 stopien: 3
indeks wierzcholka: 1 stopien: 3
indeks wierzcholka: 2 stopien: 4
indeks wierzcholka: 3 stopien: 2
indeks wierzcholka: 4 stopien: 5
indeks wierzcholka: 5 stopien: 3

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa):
    n = len(macierz_sasiedztwa) 
    stopnie_wejsciowe = [0] * n
    stopnie_wyjsciowe = [0] * n

    for i in range(n):
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie_wyjsciowe[i] += 1
                stopnie_wejsciowe[j] += 1

    print("Stopnie wejsciowe (graf skierowany):")
    for i in range(n):
        print("indeks wierzcholka:", i, "stopien:", stopnie_wejsciowe[i])
    print()

    print("Stopnie wyjsciowe (graf skierowany):")
    for i in range(n):
        print("indeks wierzcholka:", i, "stopien:", stopnie_wyjsciowe[i])
    print()

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0]
]

stopnie_w_grafie_skierowanym(macierz_sasiedztwa)

Stopnie wejsciowe (graf skierowany):
indeks wierzcholka: 0 stopien: 0
indeks wierzcholka: 1 stopien: 1
indeks wierzcholka: 2 stopien: 2
indeks wierzcholka: 3 stopien: 1
indeks wierzcholka: 4 stopien: 4
indeks wierzcholka: 5 stopien: 2

Stopnie wyjsciowe (graf skierowany): 
indeks wierzcholka: 0 stopien: 3
indeks wierzcholka: 1 stopien: 2
indeks wierzcholka: 2 stopien: 2
indeks wierzcholka: 3 stopien: 1
indeks wierzcholka: 4 stopien: 1
indeks wierzcholka: 5 stopien: 1

Badanie stopnia grafu

Graf nieskierowany

Specyfikacja problemu:

Dane:

• macierz_sasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych

Wynik:

• stopień grafu nieskierowanego

Dany jest następujący graf spójny nieskierowany bez wag:

R1OA3UoJEctUA

Ilustracja przedstawia pięciokąt wypukły. Jego wierzchołki są oznaczone kolejno cyframi 4, 0, 1, 2, 5. Wierzchołek 4 oraz 1 jest połączony przekątną, tak samo jak wierzchołek 2 i 0. Z wierzchołka 4 oraz 2 wychodzą proste, które spotykają się w punkcie oznaczonym 3, który znajduje się wewnątrz figury. Wszystkie wierzchołki i punkty są oznaczone niebieskimi kółkami.

Macierz sąsiedztwa grafu:

R2qewExxGb7lq

Ilustracja przedstawia tabelkę sześć na sześć kratek. Jej kolumny i rzędy są oznaczone cyframi od 0 do 5. W pierwszym rzędzie wpisano 0, 1, 1, 0, 1, 0, w drugim rzędzie 1, 0, 1, 0, 1, 0, w trzecim rzędzie, 1, 1, 0, 1, 0, 1, w czwartym rzędzie 0, 0, 1, 0, 1, 0, w piątym rzędzie 1, 1, 0, 1, 0, 1, w szóstym rzędzie 0, 0, 1, 0, 1, 0.

Implementacja zaprezentowanej macierzy sąsiedztwa w języku Python:

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [1, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 0]
]

W programie wykorzystamy funkcję odpowiedzialną za określenie stopni poszczególnych wierzchołków – zmodyfikujemy ją nieco, by wykorzystać listę stopnie w dalszej części programu.

Zmodyfikowana funkcja:

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa, stopnie):
    n = len(macierz_sasiedztwa) 
    for i in range(n):
        stopnie[i] = 0
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1
                if i == j:
                    stopnie[i] += 1

Dodatkowo w programie wykorzystamy jeszcze funkcję odpowiedzialną za znalezienie największego stopnia wśród stopni wierzchołków.

Zapiszmy ją. Jako argument przekażemy do funkcji listę przechowującą stopnie kolejnych wierzchołków.

Nagłówek funkcji:

def znajdz_maksymalny_stopien(stopnie):

Zaczniemy od utworzenia zmiennej maksymalnyStopien. Przypiszemy jej pierwszy element listy stopnie (element o indeksie 0).

def znajdz_maksymalny_stopien(stopnie):
    maksymalny_stopien = stopnie[0]

Następnie zapiszemy pętlę for, która będzie iterowała przez elementy listy stopnie, zaczynając od elementu o indeksie 1.

def znajdz_maksymalny_stopien(stopnie):
    maksymalny_stopien = stopnie[0]
    for i in range(1, len(stopnie)):

W pętli zapisujemy instrukcję warunkową. Wykorzystamy ją do sprawdzenia, czy aktualnie analizowany stopień wierzchołka jest większy od wartości przechowywanej w zmiennej maksymalnyStopien. Jeśli tak, zaktualizujemy wartość tej zmiennej, przypisując jej wartość analizowanego stopnia wierzchołka.

Po przeiterowaniu przez elementy listy stopnie funkcja zwraca wartość zmiennej maksymalnyStopien, czyli stopień grafu.

def znajdz_maksymalny_stopien(stopnie):
    maksymalny_stopien = stopnie[0]
    for i in range(1, len(stopnie)):
        if stopnie[i] > maksymalny_stopien:
            maksymalny_stopien = stopnie[i]
    return maksymalny_stopien

Kompletny kod programu:

def stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa, stopnie):
    n = len(macierz_sasiedztwa) 
    for i in range(n):
        stopnie[i] = 0
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1
                if i == j:
                    stopnie[i] += 1

def znajdz_maksymalny_stopien(stopnie):
    maksymalny_stopien = stopnie[0]
    for i in range(1, len(stopnie)):
        if stopnie[i] > maksymalny_stopien:
            maksymalny_stopien = stopnie[i]
    return maksymalny_stopien

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [1, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 0]
]

n = len(macierz_sasiedztwa)
stopnie = [0] * n
stopnie_w_grafie_nieskierowanym(macierz_sasiedztwa, stopnie)
maksymalny_stopien = znajdz_maksymalny_stopien(stopnie)
print("Stopien grafu nieskierowanego:", maksymalny_stopien)

Wynik działania programu:

Stopien grafu nieskierowanego: 4

Graf skierowany

Specyfikacja problemu:

Dane:

• macierz_sasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych

Wynik:

• stopień grafu skierowanego

Dany jest następujący graf spójny skierowany bez wag:

R51LJ4e2RonN5

Ilustracja przedstawia pięciokąt wypukły. Jego wierzchołki są oznaczone kolejno cyframi 4, 0, 1, 2, 5. Wierzchołek 4 oraz 1 jest połączony strzałką, tak samo jak wierzchołek 2 i 0. Z 2 wychodzi strzałka, która prowadzi do punktu oznaczonego 3, który znajduje się wewnątrz figury. Od punktu 3 do punktu 4 również prowadzi strzałka. Wszystkie wierzchołki i punkty są oznaczone niebieskimi kółkami. Od punktu 0 do punktu 4 prowadzi strzałka oznaczona e2, od punktu 0 do punktu 1 prowadzi strzałka oznaczona e0, od punktu 0 do punktu 2 prowadzi strzałka oznaczona e2. Od punktu 1 do punktu 2 prowadzi strzałka oznaczona e3, od punktu 1 do punktu 4 prowadzi strzałka oznaczona e4. Od punktu 2 do punktu 3 prowadzi strzałka oznaczona e5, od punktu 2 do punktu 5 prowadzi strzałka oznaczona e6. Od punktu 3 do punktu 4 prowadzi strzałka oznaczona e7, punkty 4 i 5 łączy strzałka grotami na obu jej końcach oznaczona e8 i e9.

Macierz sąsiedztwa grafu:

R12LrCWhJbLTN

Ilustracja przedstawia tabelkę sześć na sześć kratek. Jej kolumny i rzędy są oznaczone cyframi od 0 do 5. W pierwszym rzędzie wpisano 0, 1, 1, 0, 1, 0, w drugim rzędzie 1, 0, 1, 0, 1, 0, w trzecim rzędzie, 1, 1, 0, 1, 0, 1, w czwartym rzędzie 0, 0, 1, 0, 1, 0, w piątym rzędzie 1, 1, 0, 1, 0, 1, w szóstym rzędzie 0, 0, 1, 0, 1, 0.

Implementacja zaprezentowanej macierzy sąsiedztwa w języku Python:

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0]
]

W programie ponownie wykorzystamy zmodyfikowaną funkcję odpowiedzialną za określenie stopni poszczególnych wierzchołków.

Funkcja:

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa, stopnie):
    for i in range(n):
        stopnie[i] = 0
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1
            if macierz_sasiedztwa[j][i] != 0:
                stopnie[i] += 1

Funkcja odpowiedzialna za określenie największego stopnia wierzchołka jest taka sama, jak dla implementacji dla grafu nieskierowango:

def znajdz_maksymalny_stopien(stopnie):
    maksymalny_stopien = stopnie[0]
    for i in range(1, len(stopnie)):
        if stopnie[i] > maksymalny_stopien:
            maksymalny_stopien = stopnie[i]
    return maksymalny_stopien

Kompletny kod programu:

def stopnie_w_grafie_skierowanym(macierz_sasiedztwa, stopnie):
    for i in range(n):
        stopnie[i] = 0
        for j in range(n):
            if macierz_sasiedztwa[i][j] != 0:
                stopnie[i] += 1
            if macierz_sasiedztwa[j][i] != 0:
                stopnie[i] += 1


def znajdz_maksymalny_stopien(stopnie):
    maksymalny_stopien = stopnie[0]
    for i in range(1, len(stopnie)):
        if stopnie[i] > maksymalny_stopien:
            maksymalny_stopien = stopnie[i]
    return maksymalny_stopien

macierz_sasiedztwa = [
    [0, 1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0]
]

n = len(macierz_sasiedztwa)
stopnie = [0] * n
stopnie_w_grafie_skierowanym(macierz_sasiedztwa, stopnie)
maksymalny_stopien = znajdz_maksymalny_stopien(stopnie)
print("Stopien grafu skierowanego:", maksymalny_stopien)

Wynik działania programu:

Stopien grafu skierowanego: 5

Słownik