Graf krawędziowy


Tematy pokrewne  
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
 

Problem

Dla danego grafu nieskierowanego znaleźć jego 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 (v1,v2) i (v3,v4) 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.
Elementy pomocnicze:
v,u,w  –  numery wierzchołków w grafie, v,u,w symbol C
iv-u,iu-w  –  numery krawędzi w grafie G, iv-u,iu-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 K03...K08 ; przechodzimy przez kolejne wierzchołki grafu G
K03:     Dla każdego sąsiada u wierzchołka v wykonuj K04...K08 ; przeglądamy wszystkich sąsiadów wierzchołka v
K04:         iv-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 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:             iu-w ← numer krawędzi u–w ; mamy krawędź u-w, która jest wychodząca w wierzchołku u
K08:             Dodaj krawędź (iv-u,iu-w) do grafu GE ; w GE krawędź wchodzącą łączymy z krawędzią wychodzącą
K09: Zakończ z wynikiem GE  

 

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

 

Przykładowe dane wejściowe

    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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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
  

 

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



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



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

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.