KI - Reprezentacje grafów

Zastanów się nad sposobem reprezentacji multigrafu za pomocą macierzy sąsiedztwa. Czy jest to możliwe? Jeśli tak, to co będą zawierały komórki macierzy. Napisz odpowiedni program. Uważaj na pętle, które powinny być zaliczane jako jedna krawędź.

Normalna macierz sąsiedztwa jest macierzą logiczną. tzn. jej komórki spełniają proste kryterium:

Prosta zmiana definicji pozwoli nam umieszczać w macierzy informację o ścieżkach wielokrotnych:

Modyfikacja programu jest kosmetyczna. Polega na zastąpieniu instrukcji przypisania na instrukcję zwiększania o 1:

A[v1][v2] = A[v2][v1] = 1;
zamieniamy na:
A[v1][v2]++;
if(v1 != v2) A[v2][v1]++;

W drugim przykładzie instrukcja if jest potrzebna po to, aby pętle nie zliczać dwukrotnie. W pętli oba wierzchołki posiadają te same numery.

Zadanie 2

Jak sprawdzić na podstawie macierzy sąsiedztwa, czy graf jest grafem skierowanym lub nieskierowanym.

W grafie nieskierowanym w macierzy sąsiedztwa wprowadzamy po dwie krawędzie: od v_i do v_j oraz na odwrót, od v_j do v_i. Robimy tak dlatego, iż każdą krawędź grafu nieskierowanego można przejść w obu kierunkach. Skoro tak, to macierz sąsiedztwa grafu skierowanego jest zawsze macierzą symetryczną względem głównej przekątnej.

Symetria ta oznacza, iż dla każdego elementu a_i,j macierzy zachodzi równość

Zwróć uwagę, że i-ty wiersz macierzy symetrycznej jest równy i-tej kolumnie tej macierzy. Elementy leżące na przekątnej nas nie interesują (kierunek przejścia pętli nie jest istotny, ponieważ zawsze idziemy od wierzchołka v_i do v_i). Również nie musimy sprawdzać całej macierzy. Wystarczy porównać ze sobą połówki ponad i poniżej przekątnej. W połówce górnej bierzemy do porównania elementy i-tych wierszy, w połówce dolnej bierzemy do porównania elementy i-tych kolumn. Elementy w wierszu lub w kolumnie porównujemy poczynając od (i+1)-szego, a kończąc na n-tym. Ostatniego wiersza i ostatniej kolumny nie musimy sprawdzać, gdyż pozostaje w nich jedynie element przekątny.

Z rozważań tych powstaje następujący fragment kodu (wklejamy go w odpowiednim miejscu do programu głównego) :

Code::Blocks

// Test na graf nieskierowany

  bool isNoDigraph = true; // zmienna decyzyjna

// Przeglądamy macierz sąsiedztwa, porównując ze sobą elementy wierszy i kolumn

  for(i = 0; isNoDigraph && (i < n - 1); i++)
    for(j = i + 1; isNoDigraph && (j < n); j++)
      isNoDigraph = (A[i][j] == A[j][i]); // test na symetrię macierzy

// Wyświetlamy wyniki

  if(isNoDigraph) cout << "GRAF NIESKIEROWANY" << endl;
  else            cout << "GRAF SKIEROWANY" << endl;

Zadanie 3

Napisz program, który w grafie skierowanym zlicza krawędzie tworzące pętle oraz krawędzie, które można przejść w obu kierunkach.

Aby zliczyć pętle wystarczy zsumować elementy głównej przekątnej macierzy sąsiedztwa. Krawędzie obukierunkowe zliczamy w jednej z połówek macierzy rozdzielonych główną przekątną. Wykorzystujemy tutaj pętlę z zadania nr 2, która przechodzi przez wszystkie elementy takiej połówki. Jeśli z wierzchołka v_i prowadzi do wierzchołka v_j a_i,j krawędzi, a w kierunku odwrotnym z v_j do v_i prowadzi a_j,i krawędzi, to liczba krawędzi w obu kierunkach jest mniejszą z tych dwóch liczb a_i,j i a_j,i. Zatem przechodząc przez kolejne elementy połówki macierzy sąsiedztwa, będziemy sumować zawsze mniejszy z elementów a_i,j i a_j,i. Odpowiedni fragment programu jest następujący:

Code::Blocks

// Obliczamy liczbę pętli, sumując wyrazy na głównej przekątnej

  int loopcnt = 0;

  for(i = 0; i < n; i++) loopcnt += A[i][i];

// Obliczamy liczbę krawędzi obukierunkowych

  int edgecnt = 0;

  for(i = 0; i < n - 1; i++)
    for(j = i + 1; j < n; j++)
      edgecnt += A[i][j] < A[j][i] ? A[i][j] : A[j][i];

// Wyświetlamy wyniki

  cout << "LICZBA PETLI : " << loopcnt << endl
       << "LICZBA KRAWEDZI NIESKIEROWANYCH : " << edgecnt << endl;

Zadanie 4

Napisz program, który określa stopnie poszczególnych wierzchołków grafu - pamiętaj, że pętle są liczone za 2.

Dla grafu nieskierowanego stopnie kolejnych wierzchołków otrzymamy jako sumy wyrazów wiersza macierzy, przy czym element przekątnej sumujemy mnożąc przez 2.

Code::Blocks

// Obliczamy stopnie wierzchołków, sumując wyrazy wiersza macierzy sąsiedztwa

  int vdegree;

  for(i = 0; i < n; i++)
  {
    vdegree = 0;
    for(j = 0; j < n; j++)
      if(i == j) vdegree += 2 * A[i][j];
      else       vdegree += A[i][j];

      // wypisujemy wynik

      cout << i << " : " << vdegree << endl;
  }

Dla grafu skierowanego suma wyrazów w wierszu macierzy sąsiedztwa da nam jedynie stopnie wyjściowe (liczbę krawędzi wychodzących z wierzchołka). Stopnie wejściowe otrzymamy sumując kolumny macierzy (liczby krawędzi wchodzących do wierzchołka). Stopień wierzchołka jest sumą stopnia wejściowego i wyjściowego. Tutaj pętli nie musimy liczyć za 2, ponieważ same się odpowiednio uwzględnią - raz w stopniu wejściowym i raz w stopniu wyjściowym.

Code::Blocks

// Obliczamy stopnie wierzchołków, sumując wyrazy wiersza macierzy sąsiedztwa

  int vindeg,voutdeg;

  for(i = 0; i < n; i++)
  {
    vindeg = voutdeg = 0;
    for(j = 0; j < n; j++)
    {
      voutdeg += A[i][j];
      vindeg  += A[j][i];
    }

    // wypisujemy wynik

    cout << i << " : " << vindeg + voutdeg << endl;
  }

Zadanie 5

Wierzchołek izolowany nie jest połączony krawędzią z żadnym innym wierzchołkiem w grafie.

Dla grafu nieskierowanego wystarczy sprawdzić, czy suma wyrazów i-tego wiersza macierzy sąsiedztwa jest równa 0. Jeśli tak, to wierzchołek i-ty jest izolowany. Suma ta określa stopień wierzchołka. Stopień zerowy oznacza brak krawędzi.

Code::Blocks

// Wyszukujemy wierzchołki izolowane

  int visolated;

  for(i = 0; i < n; i++)
  {
    visolated = 0;
    for(j = 0; j < n; j++) visolated += A[i][j];

      // wypisujemy wynik

      if(!visolated) cout << i << " : IZOLOWANY" << endl;
  }

W grafie skierowanego należy wyznaczyć sumę wyrazów i-tego wiersza i i-tej kolumny. Jeśli jest ona równa zero, to i-ty wierzchołek jest izolowany.

Code::Blocks

// Wyszukujemy wierzchołki izolowane

  int visolated;

  for(i = 0; i < n; i++)
  {
    visolated = 0;
    for(j = 0; j < n; j++) visolated += A[i][j] + A[j][i];

      // wypisujemy wynik

      if(!visolated) cout << i << " : IZOLOWANY" << endl;
  }

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

Rozwiązania zadań 1-5 - macierz sąsiedztwa

Zadanie 1

Zadanie 2

Zadanie 3

Zadanie 4

Zadanie 5