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

Zadanie 1

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:

 

dla grafu skierowanego:

A[v1][v2] = 1;

zamieniamy na
A[v1][v2]++;

 

dla grafu nieskierowanego:

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 vi do vj oraz na odwrót, od vj do vi. 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.

 

  0 1 2 3 4 5
0 0 1 1 0 1 0
1 1 0 0 1 0 0
2 1 0 0 1 0 0
3 0 1 1 0 1 1
4 1 0 0 1 0 1
5 0 0 0 1 1 1

 

Symetria ta oznacza, iż dla każdego elementu ai,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 vi do vi). 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 vi prowadzi do wierzchołka vj ai,j krawędzi, a w kierunku odwrotnym z vj do vi prowadzi aj,i krawędzi, to liczba krawędzi w obu kierunkach jest mniejszą z tych dwóch liczb ai,j i aj,i. Zatem przechodząc przez kolejne elementy połówki macierzy sąsiedztwa, będziemy sumować zawsze mniejszy z elementów ai,j i aj,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

Napisz program, który wyszukuje w grafie wierzchołki izolowane.

 

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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

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