Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2011 mgr Jerzy Wałaszek I LO w Tarnowie

Rozwiązania zadań 6-8 - macierz incydencji

Zadanie 6

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.

    // 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;
    }

Zadanie 7

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

    // 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"; 
    }

Zadanie 8

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 i-ta i j-ta są znajomymi. Dla każdej osoby i-tej w grupie należy wyznaczyć osoby, których osoba i-ta ani jej bezpośredni znajomi nie znają osobiście.

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

// 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;
}

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    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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