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

Graf krawędziowy

SPIS TREŚCI

Problem

Dla danego grafu nieskierowanego należy znaleźć jego graf krawędziowy

Rozwiązanie

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

obrazek        obrazek        obrazek        obrazek
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 1, v 2 ) i ( v 3, v 4 ) grafu krawędziowego GE  łączą się krawędzią, jeśli:

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 uv  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  symbol C.
m  –  liczba krawędzi w grafie G, m  symbol C.
G  –  graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

GE  –  graf krawędziowy grafu G.
Zmienne pomocnicze:
v, u, w  –  numery wierzchołków w grafie, v, u, w  symbol C.
i v-u, i u-w  –  numery krawędzi w grafie G, i v-u, i u-w  symbol 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 ):
obrazek     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
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // 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 PslistEl;      // Grafy
  i, u, v, ei : integer;
  p, r, s : PslistEl;
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 slistEl
{
  slistEl * 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
  slistEl **G, **GE;              // Grafy
  int i, u, v, ei;
  slistEl *p, *r, *s;

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

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

  GE = new slistEl * [ 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 slistEl;              // 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 slistEl;              // 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 slistEl;        // 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 slistEl
  Dim Next As slistEl 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 slistEl Ptr Ptr G, GE     ' Grafy
Dim As Integer i, u, v, ei
Dim As slistEl Ptr p, r, s

Open Cons For Input As #1

Input #1, n, m                   ' Czytamy rozmiary grafu

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

GE = New slistEl 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 slistEl                 ' 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 slistEl                 ' 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 slistEl           ' 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
obrazek  → obrazek

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 

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.