Algorytmy i Struktury Danych - Graf krawędziowy

Graf krawędziowy (ang. line graph) powstaje z grafu w sposób następujący:


Oto graf wyjściowy		Wszystkie krawędzie zastępujemy wierzchołkami		Wierzchołki łączymy ze sobą wtedy, gdy w grafie wyjściowym ich krawędzie łączyły się poprzez wspólny wierzchołek.		Otrzymujemy graf krawędziowy.

Uogólniając, graf krawędziowy GE powstaje z grafu G w ten sposób, że krawędzie grafu G stają się wierzchołkami w grafie krawędziowym GE. Dwa wierzchołki (v₁, v₂) i (v₃, v₄) grafu krawędziowego GE łączą się krawędzią, jeśli:

w grafie nieskierowanym G: v₁ = v₃ lub v₁ = v₄ lub v₂ = v₃ lub v₂ = v₄, czyli krawędzie (v₁, v₂) i (v₃, v₄) łączą się ze sobą przez wspólny wierzchołek.
w grafie skierowanym G: v₂ = v₃, czyli ścieżka zawierająca krawędzie (v₁, v₂) i (v₃, v₄) przechodzi przez wspólny wierzchołek.

Aby efektywnie przekształcić graf G w jego graf krawędziowy GE, musimy wymyślić sposób numeracji krawędzi. Numery krawędzi mogą być zawarte w samej definicji grafu G: dla każdej krawędzi u – v zapamiętujemy oba wierzchołki u i v oraz numer i. Zatem krawędź będzie reprezentowana trójką liczb (u, v, i). Sam numer i może być generowany automatycznie w trakcie tworzenia grafu lub wczytywany z danych wejściowych, gdy zależy nam na określonej numeracji krawędzi.

Poniższy algorytm działa poprawnie zarówno dla grafu skierowanego jak i dla nieskierowanego. W pierwszym przypadku graf krawędziowy będzie skierowany, w drugim nieskierowany. Musimy jedynie pamiętać, aby w grafie nieskierowanym nadać krawędzi odwrotnej ten sam numer porządkowy.

Algorytm tworzenia grafu krawędziowego

Wejście:

n	:	liczba wierzchołków w grafie G, n C.
m	:	liczba krawędzi w grafie G, m C.
G	:	graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

graf krawędziowy grafu G.

Elementy pomocnicze:

v, u, w	:	numery wierzchołków w grafie, v, u, w C.
i_v-u, i_u-w	:	numery krawędzi w grafie G, i_v-u, i_u-w C.

Lista kroków:

K01:	Utwórz zerowy graf GE o m wierzchołkach	graf zawiera m wierzchołków, nie zawiera krawędzi
K02:	Dla v = 0, 1, …, n-1, wykonuj kroki K03…K08	przechodzimy przez kolejne wierzchołki grafu G
K03:	Dla każdego sąsiada u wierzchołka v : wykonuj kroki K04…K08	przeglądamy wszystkich sąsiadów wierzchołka v
K04:	i_v-u ← numer krawędzi v – u	mamy krawędź v-u, które jest wchodząca w wierzchołku u
K05:	Dla każdego sąsiada w wierzchołka u : wykonuj kroki K06…K08	przeglądamy wszystkich sąsiadów wierzchołka u
K06:	Jeśli w = v, to następny obieg pętli K05	pomijamy wierzchołek startowy
K07:	i_u-w ← numer krawędzi u – w	mamy krawędź u-w, która jest wychodząca w wierzchołku u
K08:	Dodaj krawędź (i_v-u, i_u-w) do grafu GE	w GE krawędź wchodzącą łączymy z krawędzią wychodzącą
K09:	Zakończ z wynikiem GE

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 wyznacza graf krawędziowy (w postaci tablicy list sąsiedztwa) dla danego grafu nieskierowanego. Definicja danych wejściowych jest następująca:

W pierwszym wierszu program odczytuje kolejno liczbę wierzchołków n oraz liczbę krawędzi m. W m kolejnych wierszach znajdują się definicje krawędzi. Definicja składa się z trzech liczb u v i. Dwie pierwsze liczby definiują numery wierzchołków, pomiędzy którymi jest krawędź. Trzecia liczba oznacza numer tej krawędzi.

Na wyjściu program wyświetla zawartość tablicy list sąsiedztwa dla grafu krawędziowego.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

6 9
0 1 0 0 2 1 0 3 2
1 4 3
2 3 4 2 5 6
3 4 5 3 5 7
4 5 8

Pascal

// Graf krawędziowy
// Data   : 22.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program line_graph;

// Definicja elementu listy sąsiedztwa
type
  PSLel = ^SLel;
  SLel = record
    next : PSLel;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
    i : integer;                  // Numer krawędzi
  end;

var
  n, m : integer;                 // Liczba wierzchołków, liczba krawędzi
  G, GE : array of PSLel;      // Grafy
  i, u, v, ei : integer;
  p, r, s : PSLel;
begin
  read (n, m);                  // Czytamy rozmiary grafu

  SetLength (G, n);             // Tworzymy zerowy graf G
  for i := 0 to n-1 do G [i] := nil;

  SetLength (GE, m);            // Tworzymy zerowy graf GE
  for i := 0 to m-1 do GE [i] := nil;

  // Odczytujemy definicje krawędzi grafu G

  for i := 1 to m do
  begin
    read (v, u, ei);            // Czytamy wierzchołki i numer krawędzi
    new (p);                    // Tworzymy rekord listy
    p^.v := u;                    // Wypełniamy go danymi
    p^.i := ei;
    p^.next := G [v];           // Rekord dołączamy do listy sąsiedztwa wierzchołka v
    G [v] := p;

    new (p);                    // To samo dla krawędzi odwrotnej
    p^.v := v;
    p^.i := ei;
    p^.next := G [u];
    G [u] := p;
  end;

  // Tworzymy graf krawędziowy

  for v := 0 to n-1 do          // Przechodzimy przez kolejne wierzchołki grafu
  begin
    p := G [v];                 // Przechodzimy przez listę sąsiadów wierzchołka v
    while p <> nil do
    begin
      r := G [p^.v];            // Przechodzimy przez listę sąsiadów sąsiada v
      while r <> nil do
      begin
        if r^.v <> v then
        begin
          new (s);              // Tworzymy nowy element listy
          s^.v := r^.i;           // Wierzchołkiem docelowym będzie krawędź wychodząca
          s^.next := GE [p^.i]; // Wierzchołkiem startowym będzie krawędź wchodząca
          GE [p^.i] := s;       // Dodajemy krawędź do grafu krawędziowego
        end;
        r := r^.next;             // Następny sąsiad
      end;
      p := p^.next;               // Następny sąsiad
    end;
  end;

  // Wyświetlamy wyniki

  writeln;

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

  // Usuwamy dynamiczne struktury

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

  for i := 0 to m-1 do
  begin
    p := GE [i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
  end;
  SetLength (GE, 0);

end.

C++

// Graf krawędziowy
// Data   : 22.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct SLel
{
  SLel * next;                 // Następny element listy;
  int v;                          // Wierzchołek docelowy
  int i;                          // Numer krawędzi
};

int main()
{
  int n, m;                       // Liczba wierzchołków, liczba krawędzi
  SLel **G, **GE;              // Grafy
  int i, u, v, ei;
  SLel *p, *r, *s;

  cin >> n >> m;                  // Czytamy rozmiary grafu

  G = new SLel * [n];        // Tworzymy zerowy graf G
  for(i = 0; i < n; i++) G [i] = NULL;

  GE = new SLel * [m];       // Tworzymy zerowy graf GE
  for(i = 0; i < m; i++) GE [i] = NULL;

  // Odczytujemy definicje krawędzi grafu G

  for(i = 0; i < m; i++)
  {
    cin >> v >> u >> ei;          // Czytamy wierzchołki i numer krawędzi
    p = new SLel;              // Tworzymy rekord listy
    p->v = u;                     // Wypełniamy go danymi
    p->i = ei;
    p->next = G [v];            // Element dołączamy do listy sąsiedztwa wierzchołka v
    G [v] = p;

    p = new SLel;              // To samo dla krawędzi odwrotnej
    p->v = v;
    p->i = ei;
    p->next = G [u];
    G [u] = p;
  }

  // Tworzymy graf krawędziowy

  for(v = 0; v < n; v++)       // Przechodzimy przez kolejne wierzchołki grafu
    for(p = G [v]; p; p = p->next) // Przechodzimy przez listę sąsiadów wierzchołka v
      for(r = G [p->v]; r; r = r->next) // Przechodzimy przez listę sąsiadów sąsiada v
        if(r->v != v)
        {
          s = new SLel;        // Tworzymy nowy element listy
          s->v = r->i;            // Wierzchołkiem docelowym będzie krawędź wychodząca
          s->next = GE [p->i];  // Wierzchołkiem startowym będzie krawędź wchodząca
          GE [p->i] = s;        // Dodajemy krawędź do grafu krawędziowego
        }

  // Wyświetlamy wyniki

  cout << endl;

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

  // Usuwamy dynamiczne struktury

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

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

  return 0;}

Basic

' Graf krawędziowy
' Data   : 22.04.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Definicja elementu listy sąsiedztwa

Type SLel
  Dim Next As SLel Ptr        ' Następny element listy
  Dim v As Integer               ' Wierzchołek docelowy
  Dim i As Integer               ' Numer krawędzi
End Type

Dim As Integer n, m              ' Liczba wierzchołków, liczba krawędzi
Dim As SLel Ptr Ptr G, GE     ' Grafy
Dim As Integer i, u, v, ei
Dim As SLel Ptr p, r, s

Open Cons For Input As #1

Input #1, n, m                   ' Czytamy rozmiary grafu

G = New SLel Ptr [n]        ' Tworzymy zerowy graf G
For i = 0 To n-1
  G [i] = 0
Next

GE = New SLel Ptr [m]       ' Tworzymy zerowy graf GE
For i = 0 To m-1
  GE [i] = 0
Next

' Odczytujemy definicje krawędzi grafu G

For i = 1 To m
  Input #1, v, u, ei              ' Czytamy wierzchołki i numer krawędzi
  p = New SLel                 ' Tworzymy element listy
  p->v = u                        ' Wypełniamy go danymi
  p->i = ei
  p->next = G [v]               ' Element dołączamy do listy sąsiedztwa wierzchołka v
  G [v] = p

  p = New SLel                 ' To samo dla krawędzi odwrotnej
  p->v = v
  p->i = ei
  p->next = G [u]
  G [u] = p
Next

Close #1

' Tworzymy graf krawędziowy

For v = 0 To n-1                ' Przechodzimy przez kolejne wierzchołki grafu
  p = G [v]                     ' Przechodzimy przez listę sąsiadów wierzchołka v
  While p
    r = G [p->v]                ' Przechodzimy przez listę sąsiadów sąsiada v
    While r
      If r->v <> v Then
        s = New SLel           ' Tworzymy nowy element listy
        s->v = r->i               ' Wierzchołkiem docelowym będzie krawędź wychodząca
        s->next = GE [p->i]     ' Wierzchołkiem startowym będzie krawędź wchodząca
        GE [p->i] = s           ' Dodajemy krawędź do grafu krawędziowego
      End If
      r = r->Next                 ' Następny sąsiad
    Wend
    p = p->Next                   ' Następny sąsiad
  Wend
Next

' Wyświetlamy wyniki

Print

For i = 0 To m-1
  Print Using "&:";i;
  p = GE [i]
  While p
    Print p->v;
    p = p->Next
  Wend
  Print
Next

' Usuwamy dynamiczne struktury

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

For i = 0 To m-1
  p = GE [i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [] GE

End

Wynik:
6 9 0 1 0 0 2 1 0 3 2 1 4 3 2 3 4 2 5 6 3 4 5 3 5 7 4 5 8 0: 1 2 3 1: 0 2 4 6 2: 0 1 4 5 7 3: 0 5 8 4: 1 6 2 5 7 5: 2 4 7 3 8 6: 1 4 7 8 7: 2 4 5 6 8 8: 3 5 6 7	→

Przerób powyższy program, tak aby wyznaczał graf krawędziowy dla grafu skierowanego (sam algorytm pozostaje bez zmian!).

Na początek: podrozdziału strony

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.

Graf krawędziowy