Transpozycja grafu


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
  Transpozycja grafu zadanego macierzą sąsiedztwa
Transpozycja grafu zadanego listami sąsiedztwa
Transpozycja grafu zadanego macierzą incydencji

Problem

Dokonać transpozycji danego grafu skierowanego.



Transpozycja grafu skierowanego (ang. digraph transposition) polega na otrzymaniu grafu, który posiada te same wierzchołki, lecz którego krawędzie mają zwrot przeciwny.

 

Graf wyjściowy

       Graf transponowany

 

Transpozycja grafu zadanego macierzą sąsiedztwa

Aby otrzymać graf transponowany, wystarczy transponować jego macierz sąsiedztwa. Spowoduje to zamianę zwrotu wszystkich krawędzi grafu. Ponieważ macierz sąsiedztwa jest macierzą kwadratową, to można ją transponować w miejscu (gdy graf wyjściowy nie jest potrzebny), utworzyć nową macierz i przepisać do niej zawartość starej macierzy zastępując kolumny wierszami i na odwrót lub po prostu zastąpić odwołania do kolumn odwołaniami do wierszy macierzy i na odwrót (w tym przypadku nic nie musimy robić z macierzą sąsiedztwa!).

Rozwiązanie jest bardzo proste i zostało dokładnie opisane w rozdziale o transpozycji macierzy.

 

Transpozycja grafu zadanego listami sąsiedztwa

Tworzymy nową tablicę list sąsiedztwa dla grafu transponowanego. Tablicę wypełniamy pustymi listami. Następnie przeglądamy kolejne listy sąsiedztwa w grafie wyjściowym. Jeśli lista wierzchołka v jest niepusta, to zawiera numery sąsiadów u, do których prowadzą krawędzie wychodzące z v. Dla każdego takiego sąsiada u wpisujemy na listę wierzchołka u w grafie transponowanym wierzchołek v. Dzięki temu graf transponowany będzie zawierał wszystkie krawędzie grafu wyjściowego o zwrocie przeciwnym.

 

Algorytm transponowania grafu zadanego listami sąsiedztwa

Wejście
n    liczba wierzchołków w grafie, n C
A    n elementowa tablica list sąsiedztwa grafu wyjściowego
Wyjście:
AT – n elementowa tablica list sąsiedztwa grafu transponowanego
Elementy pomocnicze:
v    wierzchołek, v C
p,r    wskaźniki elementu listy
Lista kroków:
K01: Utwórz n elementową tablicę list sąsiedztwa AT  
K02: Tablicę AT wypełnij pustymi listami  
K03: Dla v = 0,1,...,n-1 wykonuj K04...K11 ; przechodzimy kolejno przez wszystkie wierzchołki grafu
K04:     pA[v] ; w p ustawiamy adres początku listy sąsiedztwa dla v
K05:     Dopóki p ≠ nil, wykonuj K06...K11 ; przechodzimy przez kolejne elementy listy
K06:         Utwórz nowy element listy  
K07:         r ← adres utworzonego elementu listy  
K08:         (rv) ← v ; w elemencie umieszczamy numer v
K09:         (rnext) ← AT[pv] ; element r dodajemy do listy AT sąsiada
K10:         AT[pv] ← r  
K11:         p ← (pnext) ; przechodzimy do następnego sąsiada na liście A
K12: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu skierowanego, tworzy listy sąsiedztwa, a następnie oblicza dla niego graf transponowany i wyświetla wynik w oknie konsoli.

 

Przykładowe dane:
       7 11
0 3
1 0
2 0 2 1
4 1 4 2 4 5
5 2 5 3 5 6
6 4

 

Lazarus
// Transpozycja grafu
// Data: 22.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program transg;

// Typy dla dynamicznej tablicy list sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// **********************
// *** Program główny ***
// **********************

var
  n,m,v,u,i : integer;            // Liczba wierzchołków i krawędzi
  A,AT      : TList;              // Tablice list sąsiedztwa grafu
  p,r       : PslistEl;

begin
  read(n,m);                      // Odczytujemy liczbę wierzchołków i krawędzi

  SetLength(A,n);                 // Tworzymy tablice dynamiczne
  SetLength(AT,n);

  // Inicjujemy tablice

  for i := 0 to n - 1 do
  begin
    A[i]  := nil;
    AT[i] := nil;
  end;

  // Odczytujemy kolejne definicje krawędzi.

  for i := 0 to m - 1 do
  begin
    read(v,u);               // Wierzchołki tworzące krawędź
    new(p);                  // Tworzymy nowy element
    p^.v := u;               // Numerujemy go jako u
    p^.next := A[v];         // i dodajemy na początek listy A[v]
    A[v] := p;
  end;

  // Wyznaczamy graf transponowany

  for v := 0 to n - 1 do     // Przeglądamy kolejne wierzchołki
  begin
    p := A[v];               // Przeglądamy sąsiadów v
    while p <> nil do
    begin
      new(r);                // Tworzymy nowy element listy
      r^.v := v;             // Zapamiętujemy w nim wierzchołek v
      r^.next := AT[p^.v];   // i dodajemy do listy sąsiada
      AT[p^.v] := r;

      p := p^.next;          // Następny sąsiad
    end;
  end;

  // Wypisujemy wyniki

  writeln;
  for v := 0 to n - 1 do
  begin
    write(v,' :');
    p := AT[v];
    while p <> nil do
    begin
      write(' ',p^.v);
      p := p^.next;
    end;
    writeln;
  end;

  // Usuwamy tablice dynamiczne

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
    p := AT[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);
  SetLength(AT,0);
end.
Code::Blocks
// Transpozycja grafu
// Data: 22.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa

struct slistEl
{
  slistEl * next;
  int v;
};

// **********************
// *** Program główny ***
// **********************

int main()
{
  int n,m;                   // Liczba wierzchołków i krawędzi
  slistEl **A, **AT;         // Tablice list sąsiedztwa
  int i,v,u;
  slistEl *p,*r;

  cin >> n >> m;             // Odczytujemy liczbę wierzchołków i krawędzi

  A  = new slistEl * [n];    // Tworzymy tablice dynamiczne
  AT = new slistEl * [n];

  // Inicjujemy tablice

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

  // Odczytujemy kolejne definicje krawędzi.

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;           // Wierzchołki tworzące krawędź
    p = new slistEl;         // Tworzymy nowy element
    p->v = u;                // Numerujemy go jako w
    p->next = A[v];          // Dodajemy go na początek listy A[v]
    A[v] = p;
  }

  // Wyznaczamy graf transponowany

  for(v = 0; v < n; v++)     // Przeglądamy kolejne wierzchołki
    for(p = A[v]; p; p = p->next) // Przeglądamy sąsiadów v
    {
      r = new slistEl;       // Tworzymy nowy element listy
      r->v = v;              // Zapamiętujemy w nim wierzchołek v
      r->next = AT[p->v];    // i dodajemy do listy sąsiada
      AT[p->v] = r;
    }

  // Wypisujemy wyniki

  cout << endl;
  for(v = 0; v < n; v++)
  {
    cout << v << " :";
    for(p = AT[v]; p; p = p->next) cout << " " << p->v;
    cout << endl;
  }

  // Usuwamy tablice dynamiczne

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
    p = AT[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  delete [] AT;

  return 0;
}
Free Basic
' Transpozycja grafu
' Data: 22.01.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' **********************
' *** Program główny ***
' **********************

Dim As Integer n,m               ' Liczba wierzchołków i krawędzi
Dim As slistEl Ptr Ptr A,AT      ' Tablice list sąsiedztwa grafu
Dim As Integer Ptr C
Dim As Integer i,v,u,cc
Dim As slistEl Ptr p,r

Open Cons For Input As #1

Input #1,n,m                     ' Odczytujemy liczbę wierzchołków i krawędzi

A  = New slistEl Ptr [n]         ' Tworzymy tablice dynamiczne
AT = New slistEl Ptr [n]

' Inicjujemy tablice

For i = 0 To n - 1
  A[i]  = 0
  AT[i] = 0
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 1 To m
  Input #1,v,u            ' Wierzchołki tworzące krawędź
  p = New slistEl         ' Tworzymy nowy element
  p->v = u                ' Numerujemy go jako w
  p->next = A[v]          ' Dodajemy go na początek listy A[v]
  A[v] = p
Next

Close #1

' Wyznaczamy graf transponowany

For v = 0 To n - 1        ' Przeglądamy kolejne wierzchołki
  p = A[v]                ' Przeglądamy sąsiadów v
  While p
  	 r = New slistEl  ' Tworzymy nowy element listy
    r->v = v              ' Zapamiętujemy w nim wierzchołek v
    r->next = AT[p->v]    ' i dodajemy do listy sąsiada
    AT[p->v] = r
    p = p->Next           ' Następny sąsiad
  Wend
Next

' Wypisujemy wyniki

Print
For v = 0 To n - 1
  Print v;" :";
  p = AT[v]
  While p
    print p->v;
    p = p->Next
  Wend
  Print
Next
  
' Usuwamy tablice dynamiczne

For i = 0 To n - 1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
  p = AT[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] A
Delete [] AT

End
Wynik
7 11
0 3
1 0
2 0 2 1
4 1 4 2 4 5
5 2 5 3 5 6
6 4

0 : 2 1
1 : 4 2
2 : 5 4
3 : 5 0
4 : 6
5 : 4
6 : 5

 

Transpozycja grafu zadanego macierzą incydencji

W macierzy incydencji zamieniamy wszystkie wartości 1 na -1 i na odwrót. Otrzymamy w ten sposób graf, w którym krawędzie posiadają odwrotne zwroty. Macierz incydencji możemy przeglądać kolumnami (kolumna reprezentuje krawędź). W kolumnie szukamy dwóch niezerowych wartości i, gdy je znajdziemy, zmieniamy ich znaki na przeciwne. Dalsze przeglądanie kolumny można już zaniechać.

 

Algorytm transponowania grafu zadanego macierzą incydencji

Wejście
n    liczba wierzchołków w grafie, n C
m    liczba krawędzi w grafie, m C
A    n x m elementowa macierz incydencji grafu wyjściowego
Wyjście:
A – n x m elementowa macierz incydencji grafu transponowanego
Elementy pomocnicze:
vc    zmienna logiczna używana do przerywania pętli po dwóch wierzchołkach
i,j    indeksy kolumn i wierszy, i,j C
Lista kroków:
K01: vc ← true ; licznik wierzchołków
K02: Dla i = 0,1,...,m-1 wykonuj K03...K07 ; przeglądamy kolejne kolumny
K03:    Dla j = 0,1,...,n-1 wykonuj K04...K07 ; przeglądamy komórki w kolumnie i-tej
K04:         Jeśli A[j,i] = 0, to następny obieg pętli K03 ; pomijamy wierzchołki nieincydentne z krawędzią i-tą
K05:         A[j,i] ← (-A[j,i]) ; zmieniamy kierunek krawędzi
K06         vc ← ¬ vc ; negujemy vc, co pozwoli wykryć dwa wierzchołki
K07:         Jeśli vc = true, to następny obieg pętli K02 ; po dwóch wierzchołkach przechodzimy do następnej kolumny
K08: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu skierowanego, tworzy macierz incydencji, a następnie oblicza dla niego graf transponowany i wyświetla wynik w oknie konsoli.

 

Przykładowe dane:
       7 11
0 3
1 0
2 0 2 1
4 1 4 2 4 5
5 2 5 3 5 6
6 4

 

Lazarus
// Transpozycja grafu
// Data: 22.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program transg;

// Typy dla dynamicznej macierzy incydencji
type
  nptr = array of shortint; // Wiersz
  mptr = array of nptr;     // Cała macierz

var
  n,m,i,j,v1,v2 : integer;
  A  : mptr;
  vc : boolean;

begin
  read(n,m);             // Czytamy liczbę wierzchołków i krawędzi

  SetLength(A,n);        // Tworzymy tablicę wskaźników

  for i := 0 to n - 1 do
    SetLength(A[i],m);   // Tworzymy wiersze

  // Macierz wypełniamy zerami

  for i := 0 to n - 1 do
    for j := 0 to m - 1 do
      A[i][j] := 0;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read(v1,v2);        // Wierzchołek startowy i końcowy krawędzi
    A[v1][i] := 1;      // Wierzchołek startowy
    A[v2][i] := -1;     // Wierzchołek końcowy
  end;

  // Transponujemy graf

  vc := true;

  for i := 0 to m - 1 do
    for j := 0 to n - 1 do
      if A[j,i] <> 0 then
      begin
        A[j,i] := -A[j,i];
        vc := not vc;
        if vc then break;
      end;

  writeln;

  // Wypisujemy zawartość macierzy incydencji

  write('   ');
  for i := 0 to m - 1 do write(i:3);
  writeln;
  writeln;
  for i := 0 to n - 1 do
  begin
    write(i:3);
    for j := 0 to m - 1 do write(A[i][j]:3);
    writeln;
  end;

  // Usuwamy macierz

  for i := 0 to n - 1 do SetLength(A[i],0);
  SetLength(A,0);

  writeln;
end.
Code::Blocks
// Transpozycja grafu
// Data: 22.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int n,m,i,j,v1,v2;
  signed char ** A;
  bool vc;

  cin >> n >> m;         // Czytamy liczbę wierzchołków i krawędzi

  A = new signed char * [n];    // Tworzymy tablicę wskaźników

  for(i = 0; i < n; i++)
    A[i] = new signed char [m]; // Tworzymy wiersze

  // Macierz wypełniamy zerami

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

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    A[v1][i] = 1;       // Wierzchołek startowy
    A[v2][i] = -1;      // Wierzchołek końcowy
  }

  // Transponujemy graf

  vc = true;

  for(i = 0; i < m; i++)
    for(j = 0; j < n; j++)
      if(A[j][i])
      {
        A[j][i] = -A[j][i];
        vc = !vc;
        if(vc) break;
      }

  cout << endl;

  // Wypisujemy zawartość macierzy incydencji

  cout << "   ";
  for(i = 0; i < m; i++) cout << setw(3) << i;
  cout << endl << endl;
  for(i = 0; i < n; i++)
  {
    cout << setw(3) << i;
    for(j = 0; j < m; j++) cout << setw(3) << (int) A[i][j];
    cout << endl;
  }

  // Usuwamy macierz

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

  cout << endl;

  return 0;
}
Free Basic
' Transpozycja grafu
' Data: 22.01.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

Dim As Integer n,m,i,j,v1,v2
Dim As Byte Ptr Ptr A
Dim As Byte vc

Open Cons For Input As #1

Input #1,n,m             ' Czytamy liczbę wierzchołków i krawędzi

A = New Byte Ptr [n]     ' Tworzymy tablicę wskaźników

For i = 0 To n - 1
  A[i] = New Byte [m]    ' Tworzymy wiersze
Next

' Macierz wypełniamy zerami

For i = 0 To n - 1
  For j = 0 To m - 1
    A[i][j] = 0
  Next
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m - 1
  Input #1,v1,v2        ' Wierzchołek startowy i końcowy krawędzi
  A[v1][i] = 1          ' Wierzchołek startowy
  A[v2][i] =-1          ' Wierzchołek końcowy
Next

Close #1

' Transponujemy graf

vc = 1

For i = 0 To m - 1
  For j = 0 To n - 1
    If A[j][i] Then
      A[j][i] = -A[j][i]
      vc = 1 - vc
      If vc = 1 Then Exit For
    End If
  Next
Next

Print

' Wypisujemy zawartość macierzy incydencji

Print "   ";
For i = 0 To m - 1
  Print Using "###";i;
Next
Print: Print
For i = 0 To n - 1
  Print Using "###";i;
  For j = 0 To m - 1
    Print Using "###";A[i][j];
  Next
  Print
Next

' Usuwamy macierz

For i = 0 To n - 1
  Delete [] A[i]
Next
Delete [] A

Print

End
Wynik
7 11
0 3
1 0
2 0 2 1
4 1 4 2 4 5
5 2 5 3 5 6
6 4

   0  1  2  3  4  5  6  7  8  9 10

0 -1  1  1  0  0  0  0  0  0  0  0
1  0 -1  0  1  1  0  0  0  0  0  0
2  0  0 -1 -1  0  1  0  1  0  0  0
3  1  0  0  0  0  0  0  0  1  0  0
4  0  0  0  0 -1 -1 -1  0  0  0  1
5  0  0  0  0  0  0  1 -1 -1 -1  0
6  0  0  0  0  0  0  0  0  0  1 -1

 

 


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

©2019 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