Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2011 mgr
Jerzy Wałaszek
|
Napisz program, który określa dla grafu skierowanego stopień wejściowy i wyjściowy każdego wierzchołka.
Jeśli graf jest zadany macierzą incydencji, to każdy wiersz tej macierzy reprezentuje w grafie jeden wierzchołek o numerze równym numerowi wiersza (wiersz 0 → wierzchołek 0, wiersz 1 → wierzchołek 1, itd.). Kolejne elementy wiersza związane są z kolejnymi krawędziami w grafie (kolumna 0 → krawędź 0, kolumna 1 → krawędź 1, itd.). Jeśli graf jest grafem skierowanym, to j-ty element i-tego wiersza może przyjąć tylko jedną z trzech wartości:
0 : j-ta krawędź nie zawiera i-tego wierzchołka |
1 - j-ta krawędź wychodzi z i-tego wierzchołka |
-1 - j-ta krawędź wchodzi do j-tego wierzchołka |
Stopień wejściowy to liczba krawędzi wchodzących do wierzchołka. Liczymy go obliczając ilość elementów wiersza równych -1. Podobnie stopień wyjściowy to liczba krawędzi wychodzących z wierzchołka, którą znajdziemy obliczając ilość elementów równych 1. W tym celu tworzymy dwa liczniki:
lkwy - licznik krawędzi wyjściowych
lkwe - licznik krawędzi wejściowych
Przeglądamy kolejne wiersze macierzy incydencji. Najpierw zerujemy oba liczniki, następnie przeglądamy kolejne elementy wiersza. Jeśli natrafimy na element równy 1, to zwiększamy licznik lkwy. Jeśli natrafimy na element równy -1, zwiększamy lkwe. Po przeglądnięciu całego wiersza wypisujemy numer wiersza (czyli numer wierzchołka grafu) oraz kolejno stan liczników lkwe i lkwy. Tak postępujemy z każdym wierszem macierzy.
Code::Blocks |
// Obliczanie stopni wejściowych i wyjściowych w grafie skierowanym int lkwe,lkwy; // Liczniki krawędzi wejściowych i wyjściowych // Przeglądamy kolejne wiersze macierzy incydencji cout << endl; for(i = 0; i < n; i++) { // Zerujemy liczniki krawędzi lkwe = lkwy = 0; // Przeglądamy kolejne elementy wiersza i zliczamy krawędzie for(j = 0; j < m; j++) if(A[i][j] == 1) lkwy ++; // krawędź wyjściowa else if(A[i][j] == -1) lkwe ++; // krawędź wejściowa // Wyświetlamy wyniki cout << i << " : WE = " << lkwe << " WY = " << lkwy << endl; } |
4 5 1 0 2 0 0 3 3 1 3 2 0 : WE = 2 WY = 1 1 : WE = 1 WY = 1 2 : WE = 1 WY = 1 3 : WE = 1 WY = 2 |
Napisz program, który wyznacza dla danego grafu skierowanego wszystkie wierzchołki startowe i końcowe. Wierzchołek startowy to taki, z którego tylko wychodzą krawędzie, lecz żadna nie wchodzi. Wierzchołek końcowy to taki, do którego tylko wchodzą krawędzie, lecz żadna nie wychodzi. W grafie może być wiele wierzchołków startowych i końcowych.
Wierzchołek startowy to taki, z którego tylko wychodzą krawędzie. Zatem posiada on stopień wyjściowy większy od zera, natomiast stopień wejściowy równy zero. Wierzchołek końcowy ma na odwrót - stopień wyjściowy równy zero, natomiast stopień wejściowy różny od zera. Do rozwiązania możemy wykorzystać poprzedni algorytm, który wylicza dla każdego wierzchołka grafu jego stopnie wejściowy (lkwe) oraz wyjściowy (lkwy).
Code::Blocks |
// Wyznaczanie w grafie skierowanym wierzchołków startowych i końcowych. int lkwe,lkwy; // Liczniki krawędzi wejściowych i wyjściowych // Przeglądamy kolejne wiersze macierzy incydencji cout << endl; for(i = 0; i < n; i++) { // Zerujemy liczniki krawędzi lkwe = lkwy = 0; // Przeglądamy kolejne elementy wiersza i zliczamy krawędzie for(j = 0; j < m; j++) if(A[i][j] == 1) lkwy ++; // krawędź wyjściowa else if(A[i][j] == -1) lkwe ++; // krawędź wejściowa // Sprawdzamy warunki dla wierzchołków startowego i końcowego if(lkwy && !lkwe) cout << i << " : START\n"; else if(!lkwy && lkwe) cout << i << " : KONIEC\n"; } |
8 15 1 0 2 0 3 0 0 7 1 3 4 1 1 5 2 3 3 4 4 5 2 7 4 6 7 4 2 6 6 7 2 : START 5 : KONIEC |
Napisz program wykorzystujący macierz incydencji do rozwiązania
następującego problemu grafowego: Jest pewna grupa n osób.
Poszczególne osoby w tej grupie są ponumerowane od 0 do n-1. Osoby łączy
kryterium znajomości: osoby
Jest to typowy problem grafowy. Aby go rozwiązać, musimy dokładnie zrozumieć czego mamy szukać. Osoby będą wierzchołkami grafu:
Ponumerujmy je od 0 do n-1 - na tym etapie sposób numeracji jest zupełnie dowolny:
Relację znajomości wyrazimy za pomocą krawędzi - dwie osoby na naszym grafie są połączone krawędzią, jeśli się nawzajem znają:
Na przykład osoba nr 10 zna się z osobami 2, 5 i 12 - dlatego łączą je krawędzie. W grafie tym wybierzmy jedną osobą, np osobę nr 6:
Teraz wyznaczmy wszystkich jej bezpośrednich znajomych - czyli wierzchołki, które są z nią połączone krawędziami:
W kolejnym kroku dla każdego bezpośredniego znajomego wyznaczamy jego znajomych bezpośrednich:
Osoby, które nie zostały wybrane na grafie są odpowiedzią: dla osoby nr 6 tylko osoba nr 13 nie jest znana osobie nr 6 oraz znajomym osoby nr 6. Zauważ, że na grafie od osoby nr 6 do 13 prowadzą co najmniej trzy ścieżki. Zatem problem ten sprowadza się do wyznaczenia dla każdego wierzchołka grafu wszystkich wierzchołków, których odległość jest większa od dwóch krawędzi. Dla innych osób lista nieznajomych może być inna. To właśnie nasz program ma wyznaczyć. Zasada działania będzie następująca:
Graf nieskierowany będzie reprezentowany macierzą incydencji (nie jest to najlepszy wybór dla tego typu zadania, ale chodzi tutaj o przykład dydaktyczny, a nie super efektywne rozwiązanie). Tworzymy tablicę logiczną o nazwie nieznajomi. Tablica ta będzie zawierała n elementów. Każdy element tablicy nieznajomi jest skojarzony z jednym wierzchołkiem grafu.
Przechodzimy przez kolejne wiersze macierzy incydencji - każdy wiersz reprezentuje w grafie jeden wierzchołek. Na początku do całej tablicy nieznajomi wpisujemy wartości true (zakładamy, że wszyscy ludzie są nieznajomymi). Następnie przeglądamy kolejno elementy wiersza i-tego macierzy incydencji - szukamy krawędzi, które zawierają przetwarzany i-ty wierzchołek. Krawędzie te prowadzą do jego bezpośrednich znajomych. Jeśli zatem natrafimy w wierszu i-tym na element j-ty równy 1, to w kolumnie j-tej szukamy szukamy drugiego elementu o wartości 1. Wiersz, w którym ten element będzie występował jest k-tym wierzchołkiem grafu, który łączy się krawędzią j-tą z wierzchołkiem i-tym. W tablicy nieznajomi zerujemy element k-ty. Przeglądamy k-ty wiersz macierzy incydencji szukając elementów równych 1. Dla każdego takiego elementu znajdujemy w tej samej kolumnie drugi element równy 1 - czyli wierzchołek, do którego prowadzi krawędź. Element tablicy nieznajomi o indeksie równym numerowi znalezionego wierzchołka zerujemy. Operację kontynuujemy aż do przeglądnięcia całego wiersza k-tego, po czym wracamy i dalej przeglądamy wiersz i-ty. Gdy przeglądanie się zakończy, w tablicy nieznajomi pozostaną elementy o wartości true. Należy je znaleźć i wypisać ich indeksy obok numeru wierzchołka i-tego. Będą to numery osób, które osoba i-ta wraz ze swoimi bezpośrednimi znajomymi nie znają.
Code::Blocks |
// Wyszukiwanie nieznajomych 2 stopnia // Graf nieskierowany // Macierz incydencji // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <iomanip> using namespace std; int main() { int ** A,i,j,k,l,m,n,p,w1,w2; // Odczytujemy n i m cin >> n >> m; // Dynamicznie tworzymy macierz o wymiarze n x m A = new int * [n]; // n wierszy for(i = 0; i < n; i++) A[i] = new int [m]; // m wyrazów w wierszu // Zerujemy macierz for(i = 0; i < n; i++) for(j = 0; j < m; j++) A[i][j] = 0; // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich w macierzy for(i = 0; i < m; i++) { cin >> w1 >> w2; A[w1][i] = A[w2][i] = 1; } // Znajdowanie osób nieznajomych w grafie nieskierowanym. cout << endl; // tworzymy tablicę nieznajomi bool * nieznajomi = new bool [n]; // Przechodzimy przez kolejne wierzchołki grafu for(i = 0; i < n; i++) { // Ustawiamy tablicę nieznajomi for(j = 0; j < n; j++) nieznajomi[j] = true; // Przeglądamy wiersz i-ty w poszukiwaniu krawędzi for(j = 0; j < m; j++) if(A[i][j]) // Jeśli znajdziemy element 1, to szukamy w j-tej kolumnie drugiego końca krawędzi for(k = 0; k < n; k++) if(k != i && A[k][j]) { // Znaleziony wierzchołek k-ty używamy do wyzerowania wpisu w tablicy nieznajomi nieznajomi[k] = false; // Przeszukujemy cały wiersz k-ty, poszukując krawędzi do osób znajomych for(l = 0; l < m; l++) if(A[k][l]) // Jeśli jest krawędź, szukamy jej drugiego końca w kolumnie l-tej for(p = 0; p < n; p++) if(p != k && A[p][l]) { // Zerujemy wpis w nieznajomi wg numeru wierzchołka nieznajomi[p] = false; break; // przerywamy pętlę } break; // przerywamy pętlę } // Wypisujemy wyniki z tablicy nieznajomi cout << i << " : "; for(j = 0; j < n; j++) if(nieznajomi[j]) cout << j << " "; cout << endl; } cout << endl << endl; // Zwalniamy pamięć delete [] nieznajomi; for(i = 0; i < n; i++) delete [] A[i]; delete [] A; return 0; } |
12 14 0 3 1 3 1 2 2 5 5 6 3 4 4 6 3 8 4 10 6 11 7 8 8 9 9 10 10 11 0 : 2 5 6 7 9 10 11 1 : 6 7 9 10 11 2 : 0 4 7 8 9 10 11 3 : 5 11 4 : 2 7 5 : 0 3 7 8 9 10 6 : 0 1 7 8 9 7 : 0 1 2 4 5 6 10 11 8 : 2 5 6 11 9 : 0 1 2 5 6 10 : 0 1 2 5 7 11 : 0 1 2 3 7 8 |
W ramach ćwiczeń spróbuj rozwiązać ten problem wykorzystując reprezentację grafu macierzą sąsiedztwa i listami sąsiedztwa. Oceń efektywność tych rozwiązań.
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe