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

©2022 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
©2022 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.