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

©2026 mgr Jerzy Wałaszek

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 wejściowego grafu nieskierowanego w sposób następujący:

Oto graf wejściowy

obrazek

Wszystkie krawędzie
zastępujemy
wierzchołkami:

obrazek

Wierzchołki łączymy ze
sobą wtedy, gdy w grafie
wejściowym ich krawędzie
łączyły się poprzez
wspólny wierzchołek.:

obrazek

Otrzymujemy
graf krawędziowy.

obrazek

Uogólniając, graf krawędziowy GE powstaje z wejściowego 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ć wejściowy 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 wejściowy 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 ∈ C.
iv-u, iu-w : numery krawędzi w grafie G, iv-u, iu-w ∈ C.

Lista kroków:

K01: Utwórz zerowy graf GE ; graf zawiera m wierzchołków,
     o m wierzchołkach ; nie zawiera krawędzi
K02: Dla v = 0, 1, …, n-1, ; przechodzimy przez kolejne
     wykonuj kroki K03…K08 ; wierzchołki grafu G
K03:   Dla każdego sąsiada u wierzchołka v : ; przeglądamy
       wykonuj kroki K04…K08 ; 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 : ; przeglądamy
       wykonuj kroki K06…K08 ; wszystkich sąsiadów wierzchołka u
K06:     Jeśli w = v, ; pomijamy wierzchołek startowy
         to następny obieg pętli K05
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) ; w GE krawędź wchodzącą
         do grafu GE ; łą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
  PSLel = ^SLel;
  SLel = record
    // Następny element listy
    next : PSLel;
    // Wierzchołek docelowy
    v : integer;
    // Numer krawędzi
    i : integer;
  end;

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

begin
  // Czytamy rozmiary grafu
  read(n, m);
  // Tworzymy zerowy graf G
  SetLength(G, n);
  for i := 0 to n-1 do
    G[i] := nil;
  // Tworzymy zerowy graf GE
  SetLength(GE, m);
  for i := 0 to m-1 do
    GE[i] := nil;
  // Odczytujemy definicje
  // krawędzi grafu G
  for i := 1 to m do
  begin
    // Czytamy wierzchołki
    // i numer krawędzi
    read(v, u, ei);
    // Tworzymy rekord listy
    new(p);
    // Wypełniamy go danymi
    p^.v := u;
    p^.i := ei;
    // Rekord dołączamy
    // do listy sąsiedztwa
    // wierzchołka v
    p^.next := G[v];
    G[v] := p;
    // To samo dla krawędzi
    // odwrotnej
    new(p);
    p^.v := v;
    p^.i := ei;
    p^.next := G[u];
    G[u] := p;
  end;
  // Tworzymy graf krawędziowy
  // Przechodzimy przez kolejne
  // wierzchołki grafu G
  for v := 0 to n-1 do
  begin
    // Przechodzimy przez listę
    // sąsiadów wierzchołka v
    p := G[v];
    while p <> nil do
    begin
      // Przechodzimy przez
      // listę sąsiadów sąsiada v
      r := G[p^.v];
      while r <> nil do
      begin
        if r^.v <> v then
        begin
          // Tworzymy nowy element listy
          new(s);
          // Wierzchołkiem docelowym
          // będzie krawędź wychodząca
          s^.v := r^.i;
          // Wierzchołkiem startowym
          // będzie krawędź wchodząca
          s^.next := GE[p^.i];
          // Dodajemy krawędź do
          // grafu krawędziowego
          GE[p^.i] := s;
        end;
        // Następny sąsiad
        r := r^.next;
      end;
      // Następny sąsiad
      p := p^.next;
    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
{
  // Następny element listy;
  SLel * next;
  // Wierzchołek docelowy
  int v;
  // Numer krawędzi
  int i;
};

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

  // Czytamy rozmiary grafu
  cin >> n >> m;
  // Tworzymy zerowy graf G
  G = new SLel * [n];
  for(i = 0; i < n; i++)
    G[i] = nullptr;
  // Tworzymy zerowy graf GE
  GE = new SLel * [m];
  for(i = 0; i < m; i++)
    GE[i] = nullptr;
  // Odczytujemy definicje
  // krawędzi grafu G
  for(i = 0; i < m; i++)
  {
    // Czytamy wierzchołki
    // i numer krawędzi
    cin >> v >> u >> ei;
    // Tworzymy rekord listy
    p = new SLel;
    // Wypełniamy go danymi
    p->v = u;
    p->i = ei;
    // Element dołączamy
    // do listy sąsiedztwa
    // wierzchołka v
    p->next = G[v];
    G[v] = p;
    // To samo dla
    // krawędzi odwrotnej
    p = new SLel;
    p->v = v;
    p->i = ei;
    p->next = G[u];
    G[u] = p;
  }
  // Tworzymy graf krawędziowy
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for(v = 0; v < n; v++)
    // Przechodzimy przez listę
    // sąsiadów wierzchołka v
    for(p = G[v]; p; p = p->next)
      // Przechodzimy przez listę
      // sąsiadów sąsiada v
      for(r = G[p->v]; r; r = r->next)
        if(r->v != v)
        {
          // Tworzymy nowy element listy
          s = new SLel;
          // Wierzchołkiem docelowym
          // będzie krawędź wychodząca
          s->v = r->i;
          // Wierzchołkiem startowym będzie
          // krawędź wchodząca
          s->next = GE[p->i];
          // Dodajemy krawędź do grafu
          // krawędziowego
          GE[p->i] = s;
        }
  // 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
  ' Następny element listy
  Dim Next As SLel Ptr
  ' Wierzchołek docelowy
  Dim v As Integer
  ' Numer krawędzi
  Dim i As Integer
End Type

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

Open Cons For Input As #1
' Czytamy rozmiary grafu
Input #1, n, m
' Tworzymy zerowy graf G
G = New SLel Ptr [n]
For i = 0 To n-1
  G[i] = 0
Next
' Tworzymy zerowy graf GE
GE = New SLel Ptr [m]
For i = 0 To m-1
  GE[i] = 0
Next
' Odczytujemy definicje krawędzi grafu G
For i = 1 To m
  ' Czytamy wierzchołki i numer krawędzi
  Input #1, v, u, ei
  ' Tworzymy element listy
  p = New SLel
  ' Wypełniamy go danymi
  p->v = u
  p->i = ei
  ' Element dołączamy do listy
  ' sąsiedztwa wierzchołka v
  p->next = G[v]
  G[v] = p
  ' To samo dla krawędzi odwrotnej
  p = New SLel
  p->v = v
  p->i = ei
  p->next = G[u]
  G[u] = p
Next
Close #1
' Tworzymy graf krawędziowy
' Przechodzimy przez kolejne
' wierzchołki grafu
For v = 0 To n-1
  ' Przechodzimy przez listę
  ' sąsiadów wierzchołka v
  p = G[v]
  While p
    ' Przechodzimy przez listę
    ' sąsiadów sąsiada v
    r = G[p->v]
    While r
      If r->v <> v Then
        ' Tworzymy nowy element listy
        s = New SLel
        ' Wierzchołkiem docelowym będzie
        ' krawędź wychodząca
        s->v = r->i
        ' Wierzchołkiem startowym będzie
        ' krawędź wchodząca
        s->next = GE[p->i]
        ' Dodajemy krawędź do
        ' grafu krawędziowego
        GE[p->i] = s
      End If
      ' Następny sąsiad
      r = r->Next
    Wend
    ' Następny sąsiad
    p = p->Next
  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
Python (dodatek)
# Graf krawędziowy
# Data: 17.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Klasa elementu listy sąsiedztwa
class SLel:
    def __init__(self):
        # Następny element listy
        self.next = None
        # Wierzchołek docelowy
        self.v = 0
        # Numer krawędzi
        self.i = 0


# Czytamy rozmiary grafu
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy zerowy graf G
g = [None] * n
# Tworzymy zerowy graf GE
ge = [None] * m
# Odczytujemy definicje krawędzi grafu G
for i in range(m):
    # Czytamy wierzchołki i numer krawędzi
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    e = int(x[2])
    # Tworzymy element listy
    p = SLel()
    # Wypełniamy go danymi
    p.v = u
    p.i = e
    # Element dołączamy do listy
    # sąsiedztwa wierzchołka v
    p.next = g[v]
    g[v] = p
    # To samo dla krawędzi odwrotnej
    p = SLel()
    p.v = v
    p.i = e
    p.next = g[u]
    g[u] = p
# Tworzymy graf krawędziowy
# Przechodzimy przez kolejne
# wierzchołki grafu
for v in range(n):
    # Przechodzimy przez listę
    # sąsiadów wierzchołka v
    p = g[v]
    while p:
        # Przechodzimy przez listę
        # sąsiadów sąsiada v
        r = g[p.v]
        while r:
            if r.v != v:
                # Tworzymy nowy element listy
                s = SLel()
                # Wierzchołkiem docelowym będzie
                # krawędź wychodząca
                s.v = r.i
                # Wierzchołkiem startowym będzie
                # krawędź wchodząca
                s.next = ge[p.i]
                # Dodajemy krawędź do
                # grafu krawędziowego
                ge[p.i] = s
            # Następny sąsiad
            r = r.next
        # Następny sąsiad
        p = p.next
# Wyświetlamy wyniki
print()
for i in range(m):
    print(i,": ", sep="", end="")
    p = ge[i]
    while p:
        print(p.v, end=" ")
        p = p.next
    print()
# Usuwamy dynamiczne struktury
for i in range(n):
    while g[i]:
        g[i] = g[i].next
del g
for i in range(m):
    while ge[i]:
        ge[i] = ge[i].next
del ge
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!).


do podrozdziału  do strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2026 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.