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

• stopień grafu,

• stopień wierzchołkawierzchołekwierzchołka grafu,

• spójność grafugraf spójnyspó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ędzikrawędź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 (by przypomnieć sobie, dlaczego przywołujemy mosty królewieckie w kontekście teorii grafów, przejdź do e‑materiału Zagadnienie mostów królewieckichPwWUgv9LEZagadnienie mostów królewieckich):

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ścieżkaś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:

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

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:

• n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna

• macierzSasiedztwa – macierz sąsiedztwa grafu; tablica 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 C++:

const int n = 6;

int macierzSasiedztwa[n][n] = {
	{ 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 }
};

Tworzymy również stałą n, która będzie przechowywać liczbę wierzchołków grafu.

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.

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    
}

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

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    int stopnie[n] = {0};
    
}

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

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    int stopnie[n] = {0};    
    for (int i = 0; i < n; ++i) {
    }        
}

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

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    int stopnie[n] = {0};    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
        
        }            
    }        
}

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 tablicy stopnie.

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    int stopnie[n] = {0};    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
            
            }                
        }            
    }        
}

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 tablicy stopnie.

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    int stopnie[n] = {0};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
                if (i == j) {
                    stopnie[i]++;
                }                         
            }                
        }            
    }        
}

Dodajemy niezbędną bibliotekę, przestrzeń nazw, a także wywołanie funkcji.

#include <iostream>
using namespace std;

const int n = 6;

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n]) {
    int stopnie[n] = {0};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
                if (i == j) {
                    stopnie[i]++;
                }    
            }
        }
    }

    cout << "Stopnie (graf nieskierowany): " << endl;
    for (int i = 0; i < n; ++i) {
        cout << "indeks wierzcholka: " << i << " stopien: " << stopnie[i] << endl;
    }
}

int main() {
    int macierzSasiedztwa[n][n] = {
        { 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 }
    };

    stopnieWGrafieNieskierowanym(macierzSasiedztwa);

    return 0;
}

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:

• n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna

• macierzSasiedztwa – macierz sąsiedztwa grafu; tablica 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 C++:

const int n = 6;

int macierzSasiedztwa[n][n] = {
	{ 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 }
};

Ponownie tworzymy stałą n odpowiedzialną za przechowywanie liczby wierzchołków grafu.

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.

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n]) {
    
}

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

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n]) {
    int stopnie[n] = {0};
    
}

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

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n]) {
    int stopnie[n] = {0};
    for (int i = 0; i < n; ++i) {
    }        
}

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.

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n]) {
    int stopnie[n] = {0};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
        
        }            
    }        
}

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 tablicy 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.

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n]) {
    int stopnie[n] = {0};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
                stopnie[j]++;
            }
        }
    }
}

Dodajemy niezbędną bibliotekę, przestrzeń nazw, a także wywołanie funkcji.

#include <iostream>
using namespace std;

const int n = 6;

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n]) {
    int stopnie[n] = {0};

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
                stopnie[j]++;
            }
        }
    }

    cout << "Stopnie (graf skierowany): " << endl;
    for (int i = 0; i < n; ++i) {
        cout << "indeks wierzcholka: " << i << " stopien: " << stopnie[i] << endl;
    }
    cout << endl;
}

int main() {
    int macierzSasiedztwa[n][n] = {
        { 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 }
    };

    stopnieWGrafieSkierowanym(macierzSasiedztwa);

    return 0;
}

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

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n]) {
    int stopnieWejsciowe[n] = {0};
    int stopnieWyjsciowe[n] = {0};

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnieWyjsciowe[i]++;
                stopnieWejsciowe[j]++;
            }
        }
    }

    cout << "Stopnie wejsciowe (skierowany): " << endl;
    for (int i = 0; i < n; ++i) {
        cout << "indeks wierzcholka: " << i << " stopien: " << stopnieWejsciowe[i] << endl;
    }
    cout << endl;

    cout << "Stopnie wyjsciowe (skierowany): " << endl;
    for (int i = 0; i < n; ++i) {
        cout << "indeks wierzcholka: " << i << " stopien: " << stopnieWyjsciowe[i] << endl;
    }
    cout << endl;
}

#include <iostream>
using namespace std;

const int n = 6;

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n]) {
    int stopnieWejsciowe[n] = {0};
    int stopnieWyjsciowe[n] = {0};

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnieWyjsciowe[i]++;
                stopnieWejsciowe[j]++;
            }
        }
    }

    cout << "Stopnie wejsciowe (graf skierowany): " << endl;
    for (int i = 0; i < n; ++i) {
        cout << "indeks wierzcholka: " << i << " stopien: " << stopnieWejsciowe[i] << endl;
    }
    cout << endl;

    cout << "Stopnie wyjsciowe (graf skierowany): " << endl;
    for (int i = 0; i < n; ++i) {
        cout << "indeks wierzcholka: " << i << " stopien: " << stopnieWyjsciowe[i] << endl;
    }
    cout << endl;
}

int main() {
    int macierzSasiedztwa[n][n] = {
        { 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 }
    };

    stopnieWGrafieSkierowanym(macierzSasiedztwa);

    return 0;
}

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:

• n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna

• macierzSasiedztwa – macierz sąsiedztwa grafu; tablica 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 C++:

const int n = 6;

int macierzSasiedztwa[n][n] = {
	{ 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 }
};

Tworzymy również stałą n, która będzie przechowywać liczbę wierzchołków grafu.

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

Zmodyfikowana funkcja:

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    for (int i = 0; i < n; ++i) {
        stopnie[i] = 0;
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
                if (i == j) {
                    stopnie[i]++;
                }    
            }
        }
    }
}

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 tablicę przechowującą stopnie kolejnych wierzchołków.

Nagłówek funkcji:

int znajdzMaksymalnyStopien(int stopnie[n]) {

}

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

int znajdzMaksymalnyStopien(int stopnie[n]) {
    int maksymalnyStopien = stopnie[0];
    
}

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

int znajdzMaksymalnyStopien(int stopnie[n]) {
    int maksymalnyStopien = stopnie[0];
    for (int i = 1; i < n; ++i) {
        
    }
}

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 tablicy stopnie funkcja zwraca wartość zmiennej maksymalnyStopien, czyli stopień grafu.

int znajdzMaksymalnyStopien(int stopnie[n]) {
    int maksymalnyStopien = stopnie[0];
    for (int i = 1; i < n; ++i) {
        if (stopnie[i] > maksymalnyStopien) {
            maksymalnyStopien = stopnie[i];
        }
    }
    return maksymalnyStopien;
}

Dodajemy niezbędną bibliotekę, przestrzeń nazw, a także wywołania funkcji oraz wypisywanie odpowiedniego komunikatu.

Kompletny kod programu:

#include <iostream>
using namespace std;

const int n = 6;

void stopnieWGrafieNieskierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    for (int i = 0; i < n; ++i) {
        stopnie[i] = 0;
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
                if (i == j) {
                    stopnie[i]++;
                }    
            }
        }
    }
}

int znajdzMaksymalnyStopien(int stopnie[n]) {
    int maksymalnyStopien = stopnie[0];
    for (int i = 1; i < n; ++i) {
        if (stopnie[i] > maksymalnyStopien) {
            maksymalnyStopien = stopnie[i];
        }
    }
    return maksymalnyStopien;
}

int main() {
    int macierzSasiedztwa[n][n] = {
        { 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 }
    };

    int stopnie[n];
    stopnieWGrafieNieskierowanym(macierzSasiedztwa, stopnie);
    int maksymalnyStopien = znajdzMaksymalnyStopien(stopnie);
    cout << "Stopien grafu nieskierowanego: " << maksymalnyStopien << endl;

    return 0;
}

Wynik działania programu:

Stopien grafu nieskierowanego: 4

Graf skierowany

Specyfikacja problemu:

Dane:

• n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna

• macierzSasiedztwa – macierz sąsiedztwa grafu; tablica 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 C++:

const int n = 6;

int macierzSasiedztwa[n][n] = {
	{ 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 tym przypadku również tworzymy stałą n, która będzie przechowywać liczbę wierzchołków grafu.

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

Funkcja:

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    for (int i = 0; i < n; ++i) {
        stopnie[i] = 0;
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
            }
            if (macierzSasiedztwa[j][i] != 0) {
                stopnie[i]++;
            }
        }
    }
}

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

int znajdzMaksymalnyStopien(int stopnie[n]) {
    int maksymalnyStopien = stopnie[0];
    for (int i = 1; i < n; ++i) {
        if (stopnie[i] > maksymalnyStopien) {
            maksymalnyStopien = stopnie[i];
        }
    }
    return maksymalnyStopien;
}

Dodajemy niezbędną bibliotekę, przestrzeń nazw, a także wywołanie funkcji.

Kompletny kod programu:

#include <iostream>
using namespace std;

const int n = 6;

void stopnieWGrafieSkierowanym(int macierzSasiedztwa[n][n], int stopnie[n]) {
    for (int i = 0; i < n; ++i) {
        stopnie[i] = 0;
        for (int j = 0; j < n; ++j) {
            if (macierzSasiedztwa[i][j] != 0) {
                stopnie[i]++;
            }
            if (macierzSasiedztwa[j][i] != 0) {
                stopnie[i]++;
            }
        }
    }
}

int znajdzMaksymalnyStopien(int stopnie[n]) {
    int maksymalnyStopien = stopnie[0];
    for (int i = 1; i < n; ++i) {
        if (stopnie[i] > maksymalnyStopien) {
            maksymalnyStopien = stopnie[i];
        }
    }
    return maksymalnyStopien;
}

int main() {
    int macierzSasiedztwa[n][n] = {
        { 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 }
    };

    int stopnie[n];
    stopnieWGrafieSkierowanym(macierzSasiedztwa, stopnie);
    int maksymalnyStopien = znajdzMaksymalnyStopien(stopnie);
    cout << "Stopien grafu skierowanego: " << maksymalnyStopien << endl;
    
    return 0;

}

Wynik działania programu:

Stopien grafu skierowanego: 5

Słownik