Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Transpozycja grafu

SPIS TREŚCI
Podrozdziały

Problem

Należy wykonać transpozycję 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

obrazek

       Graf transponowany

obrazek

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.

Na początek:  podrozdziału   strony 

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.
Zmienne 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 kroki K04...K11
przechodzimy kolejno przez wszystkie wierzchołki grafu
K04:     p  ← A [ v  ] w p ustawiamy adres początku listy sąsiedztwa dla v
K05:     Dopóki p  ≠ nil,
    wykonuj kroki K06...K11
przechodzimy przez kolejne elementy listy
K06:         Utwórz nowy element listy  
K07:         r  ← adres nowego elementu  
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  

Przykładowe programy

Uwaga:

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.
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek        7 11
0 3
1 0
2 0 2 1
4 1 4 2 4 5
5 2 5 3 5 6
6 4
Pascal
// 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.
C++
// 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;
}
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
obrazek
Na początek:  podrozdziału   strony 

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 × m  elementowa macierz incydencji grafu wyjściowego.

Wyjście:

A – n × m  elementowa macierz incydencji grafu transponowanego
Zmienne 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 kroki K03...K07
przeglądamy kolejne kolumny
K03:     Dla j  = 0, 1, ..., n - 1:
    wykonuj kroki 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  

Przykładowe programy

Uwaga:

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.
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):
obrazek        7 11
0 3
1 0
2 0 2 1
4 1 4 2 4 5
5 2 5 3 5 6
6 4
Pascal
// 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.
C++
// 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;
}
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
obrazek
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.