Kolorowanie grafu


Tematy pokrewne   Podrozdziały
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
  Algorytm dokładny
Algorytm zachłanny
Algorytm heurystyczny
Kolorowanie krawędzi grafu

Problem

Za pomocą minimalnej liczby kolorów pokoloruj wierzchołki grafu tak, aby żadne dwa sąsiednie wierzchołki nie były tego samego koloru.

 

 

Przez kolorowanie wierzchołków grafu będziemy rozumieli przypisanie tym wierzchołkom odpowiednich etykiet, np. numerów, które umownie reprezentują "kolory". Zadanie polega na takim przypisaniu wierzchołkom tych numerów, aby ilość użytych kolorów była najmniejsza z możliwych (minimalna ilość kolorów do pokolorowania danego grafu nosi nazwę liczby chromatycznej grafu). W przypadku ogólnym jest to zadanie bardzo trudne. Istnieją jednak algorytmy, które pozwalają rozwiązać ten problem w sposób przybliżony, tzn. uzyskane rozwiązanie może nie być optymalne, lecz zwykle jest zadowalające.

 

Algorytm dokładny

Zadanie kolorowania wierzchołków grafu najmniejszą możliwą liczbą kolorów da się rozwiązać za pomocą algorytmu, który sprawdza kolejno wszystkie możliwe układy kolorów wierzchołków i wybiera ten układ, w którym zużyta jest najmniejsza liczba kolorów. Z uwagi na bardzo niekorzystną klasę złożoności obliczeniowej rozwiązanie możemy otrzymać w sensownym czasie jedynie dla małych grafów (do 10...11 wierzchołków). Zasada działania algorytmu jest bardzo prosta:

 

Zakładamy, że graf nie jest zerowy.

Najpierw kolorujemy wierzchołki grafu wszystkimi możliwymi kombinacjami dwóch pierwszych kolorów. Przy każdej kombinacji sprawdzamy warunek pokolorowania – żadne dwa sąsiednie wierzchołki nie są tego samego koloru. Jeśli warunek będzie spełniony, kończymy.

W kolejnych krokach zwiększamy liczbę kombinacji kolorów do 3, 4, ..., n i powtarzamy powyższy krok aż do znalezienia takiej kombinacji, która będzie spełniała warunek pokolorowania grafu.

 

Podstawowym problemem jest tutaj tworzenie kombinacji kolorów poszczególnych wierzchołków. Na szczęście problem ten rozwiązujemy prosto metodą licznika. Wyobraźmy sobie, że poszczególne wierzchołki grafu są kolejnymi cyframi licznika. Na początku przyjmujemy podstawę 2. Oznacza to, że cyfry mogą przyjmować wartości 0 lub 1. Jeśli mamy w grafie 4 wierzchołki, to ustawiamy je na 0, otrzymując początkową kombinację 0000. Następne kombinacje otrzymujemy tak:

Zwiększamy o 1 ostatnią cyfrę. Jeśli jej wartość jest równa podstawie, to cyfrę zerujemy i zwiększamy w ten sam sposób cyfrę następną. Jeśli osiągnie 2, to zerujemy ją i zwiększamy następną cyfrę, itd. Otrzymamy następujące kombinacje:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Jeśli teraz zwiększymy ostatnią cyfrę, to licznik się wyzeruje. Otrzymaliśmy wszystkie kombinację 2 kolorów. W takiej sytuacji zwiększamy podstawę o 1 do 3 i znów zliczamy:

0000
0001
0002
0010
0011
0012
0020
0021
0022
0100
0101
0102
0110
0111
...
2220
2221
2222

Zwróć uwagę, że nowe kombinacje mamy tylko wtedy, gdy występuje w nich nowa cyfra (kolor) 2. Jeśli nie ma cyfry 2, to dana kombinacja była już sprawdzona w poprzednim obiegu licznika dla podstawy 2 i możemy jej nie sprawdzać (w trakcie zwiększania licznika zapamiętujemy ilość cyfr 2 i, jeśli jest ona zerowa, to pomijamy testowanie warunku pokolorowania grafu). Gdy licznik się wyzeruje, znów zwiększamy podstawę do 4 i kontynuujemy poszukiwania takiego układu kolorów wierzchołków, które spełnia warunek pokolorowania grafu.

 

Algorytm optymalnego kolorowania grafu

Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.
Wyjście:
CT  –  n elementowa tablica, która określa numery kolorów wierzchołków. Elementy są liczbami całkowitymi. CT[i] jest kolorem i-tego wierzchołka grafu.
b  – liczba użytych kolorów (liczba chromatyczna grafu), b symbol C
Elementy pomocnicze:
bc  –  zlicza ilość najstarszych cyfr-kolorów w liczniku, bc symbol C
i  –  zmienna do indeksowania cyfr w tablicy CT, i symbol C
u,v  –  numery wierzchołków grafu, u,v symbol C
Lista kroków:
K01: Wyzeruj tablicę CT  
K02: b ← 2 ; podstawa licznika
K03: bc ← 0 ; licznik najstarszej cyfry
K04: Jeśli bc = 0, to idź do K09 ; pomijamy test pokolorowania, jeśli brak najstarszej cyfry w liczniku
K05: Dla v = 0,1,...,n wykonuj K06...K07 ; przeglądamy kolejne wierzchołki grafu
K06:     Dla każdego sąsiada u wierzchołka v wykonuj K07 ; przeglądamy wszystkich sąsiadów
K07:         Jeśli CT[v] = CT[u], to idź do K09 ; sprawdzamy warunek złego pokolorowania
K08: Zakończ z wynikiem CT i b ; graf jest pokolorowany
K09: i ← 0 ; modyfikujemy licznik CT
K10: CT[i] ← CT[i] + 1 ; zwiększamy cyfrę-kolor
K11: Jeśli CT[i] = b - 1, to bcbc + 1 ; zliczamy najstarsze cyfry
K12: Jeśli CT[i] < b, to idź do K04 ; kontynuujemy z następną kombinacją kolorów
K13: CT[i] ← 0 ; jeśli cyfra jest równa podstawie, to zerujemy cyfrę licznika
K14: bcbc - 1 ; zmniejszamy liczbę najstarszych cyfr
K15: ii + 1 ; przesuwamy się do następnej cyfry
K16: Jeśli i = n, to bb + 1; idź do K09 ; jeśli wyczerpaliśmy cyfry, to należy zwiększyć podstawę
K17: Idź do K10 ; kontynuujemy z następną cyfrą-kolorem

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 odczytuje definicję grafu nieskierowanego i koloruje jego wierzchołki. Na koniec wyświetla dla każdego wierzchołka numer przydzielonego mu koloru oraz liczbę chromatyczną. Dodatkowo jest wyświetlana liczba przebadanych kombinacji kolorów.

Przykładowe dane dla programu:

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

 

Lazarus
// Optymalne kolorowanie grafu nieskierowanego
// Data   : 23.05.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------------------

program graph_coloring;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

var
  b,bc,n,m,i,u,v : integer;
  graf           : array of PslistEl;
  CT             : array of integer;
  p,r            : PslistEl;
  cnt            : qword;         // Licznik prób
  test           : boolean;

begin
  read(n,m);                      // Odczytujemy liczbę wierzchołków i krawędzi grafu

  SetLength(graf,n);              // Tablica list sąsiedztwa
  for i := 0 to n - 1 do graf[i] := nil;

  SetLength(CT,n);                // Tablica kolorów wierzchołków

  // Odczytujemy krawędzie grafu

  for i := 1 to m do
  begin
    read(u,v);                    // Wierzchołki krawędzi
    new(p);                       // Tworzymy element listy
    p^.v := u;
    p^.next := graf[v];           // Element dołączamy do listy sąsiadów v
    graf[v] := p;

    new(p);                       // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := graf[u];           // Element dołączamy do listy sąsiadów u
    graf[u] := p;
  end;

  // Rozpoczynamy algorytm kolorowania grafu

  cnt := 0;

  for i := 0 to n - 1 do CT[i] := 0; // Inicjujemy licznik

  b := 2;                         // Zliczanie rozpoczynamy przy podstawie 2
  bc := 0;                        // Liczba najstarszych cyfr

  while true do
  begin
    if bc > 0 then                // Kombinację sprawdzamy, gdy zawiera najstarszą cyfrę
    begin
      test := true;
      inc(cnt);                   // Zwiększamy liczbę prób
      for v := 0 to n - 1 do      // Przeglądamy wierzchołki grafu
      begin
        p := graf[v];             // Przeglądamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          if CT[v] = CT[p^.v] then // Testujemy pokolorowanie
          begin
            test := false;        // Zaznaczamy porażkę
            break;                // Opuszczamy pętlę while
          end;
          p := p^.next;           // Następny sąsiad
        end;
        if not test then break;   // Opuszczamy pętlę for
      end;
      if test then break;         // Kombinacja znaleziona, kończymy pętlę główną
    end;

    while true do                 // Pętla modyfikacji licznika
    begin
       i := 0;
       while i < n do
       begin
         inc(CT[i]);              // Zwiększamy cyfrę
         if CT[i] = b - 1 then inc(bc);
         if CT[i] < b then break;
         CT[i] := 0;              // Zerujemy cyfrę
         dec(bc);
         inc(i);                  // Modyfikujemy następną cyfrę
       end;
       if i < n then break;       // Wychodzimy z pętli zwiększania licznika
       inc(b);                    // Licznik się przewinął, zwiększamy bazę
    end;
  end;

  // Wyświetlamy wyniki

  writeln;
  for v := 0 to n - 1 do
    writeln('vertex ',v,' has color ',CT[v]);
  writeln;
  writeln('graph chromatic number = ',b);
  writeln('number of tries        = ',cnt);
  writeln;

  // Usuwamy tablice dynamiczne

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

  SetLength(graf,0);
  SetLength(CT,0);

end.
Code::Blocks
// Optymalne kolorowanie grafu nieskierowanego
// Data   : 23.05.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 main()
{
  int b,bc,n,m,i,u,v,*CT;
  slistEl **graf,*p,*r;
  unsigned long long cnt;         // Licznik prób
  bool test;

  cin >> n >> m;                  // Odczytujemy liczbę wierzchołków i krawędzi grafu

  graf = new slistEl * [n];       // Tablica list sąsiedztwa
  for(i = 0; i < n; i++) graf[i] = NULL;

  CT = new int [n];               // Tablica kolorów wierzchołków

  // Odczytujemy krawędzie grafu

  for(i = 0; i < m; i++)
  {
    cin >> u >> v;                // Wierzchołki krawędzi
    p = new slistEl;              // Tworzymy element listy
    p->v = u;
    p->next = graf[v];            // Element dołączamy do listy sąsiadów v
    graf[v] = p;

    p = new slistEl;              // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf[u];            // Element dołączamy do listy sąsiadów u
    graf[u] = p;
  }

  // Rozpoczynamy algorytm kolorowania grafu

  cnt = 0;

  for(i = 0; i < n; i++) CT[i] = 0; // Inicjujemy licznik

  b = 2;                          // Zliczanie rozpoczynamy przy podstawie 2
  bc = 0;                         // Liczba najstarszych cyfr

  while(true)
  {
    if(bc)                        // Kombinację sprawdzamy, gdy zawiera najstarszą cyfrę
    {
      test = true;
      cnt++;                      // Zwiększamy liczbę prób
      for(v = 0; v < n; v++)      // Przeglądamy wierzchołki grafu
      {
        for(p = graf[v];p;p = p->next) // Przeglądamy sąsiadów wierzchołka v
          if(CT[v] == CT[p->v])   // Testujemy pokolorowanie
          {
            test = false;         // Zaznaczamy porażkę
            break;                // Opuszczamy pętlę for
          }
        if(!test) break;          // Opuszczamy pętlę for
      }
      if(test) break;             // Kombinacja znaleziona, kończymy pętlę główną
    }

    while(true)                   // Pętla modyfikacji licznika
    {
       for(i = 0; i < n; i++)
       {
         CT[i]++;                 // Zwiększamy cyfrę
         if(CT[i] == b - 1) bc++;
         if(CT[i] < b) break;
         CT[i] = 0;               // Zerujemy cyfrę
         bc--;
       }

       if(i < n) break;           // Wychodzimy z pętli zwiększania licznika
       b++;                       // Licznik się przewinął, zwiększamy bazę
    }
  }

  // Wyświetlamy wyniki

  cout << endl;
  for(v = 0; v < n; v++)
    cout << "vertex " << v << " has color " << CT[v] << endl;
  cout << endl
       << "graph chromatic number = " << b << endl
       << "number of tries        = " << cnt << endl << endl;

  // Usuwamy tablice dynamiczne

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

  delete [] graf;
  delete [] CT;

  return 0;
}
Free Basic
' Optymalne kolorowanie grafu nieskierowanego
' Data   : 23.05.2014
' (C)2014 mgr Jerzy Wałaszek
'--------------------------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  next As slistEl Ptr             ' Następny element listy
  v As Integer                    ' Wierzchołek docelowy
End Type

Dim As Integer b,bc,n,m,i,u,v
Dim As Integer Ptr CT
Dim As slistEl Ptr Ptr graf
Dim As slistEl Ptr p,r
Dim As ULongInt cnt               ' Licznik prób
Dim As Byte test

Open Cons For Input As #1

Input #1,n,m                      ' Odczytujemy liczbę wierzchołków i krawędzi grafu

graf = New slistEl Ptr [n]        ' Tablica list sąsiedztwa
For i = 0 To n - 1
  graf[i] = 0
Next

CT = New Integer [n]              ' Tablica kolorów wierzchołków

' Odczytujemy krawędzie grafu

For i = 1 To m
  Input #1,u,v                    ' Wierzchołki krawędzi
  p = New slistEl                 ' Tworzymy element listy
  p->v = u
  p->next = graf[v]               ' Element dołączamy do listy sąsiadów v
  graf[v] = p

  p = New slistEl                 ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = graf[u]               ' Element dołączamy do listy sąsiadów u
  graf[u] = p
Next

Close #1

' Rozpoczynamy algorytm kolorowania grafu

cnt = 0

For i = 0 To n - 1
  CT[i] = 0                       ' Inicjujemy licznik
Next

b = 2                             ' Zliczanie rozpoczynamy przy podstawie 2
bc = 0                            ' Liczba najstarszych cyfr

while 1
  If bc > 0 Then                  ' Kombinację sprawdzamy, gdy zawiera najstarszą cyfrę
    test = 1
    cnt += 1                      ' Zwiększamy liczbę prób
    For v = 0 To n - 1            ' Przeglądamy wierzchołki grafu
      p = graf[v]
      While p                     ' Przeglądamy sąsiadów wierzchołka v
        If CT[v] = CT[p->v] Then  ' Testujemy pokolorowanie
          test = 0                ' Zaznaczamy porażkę
          Exit While              ' Opuszczamy pętlę while
        End If
        p = p->Next
      Wend
      If test = 0 Then Exit For   ' Opuszczamy pętlę for
    Next
    
    If test = 1 Then Exit While   ' Kombinacja znaleziona, kończymy pętlę główną
  End If

  While 1                         ' Pętla modyfikacji licznika
    For i = 0 To n - 1
      CT[i] += 1                  ' Zwiększamy cyfrę
      If CT[i] = b - 1 Then bc += 1
      If CT[i] < b Then Exit For
      CT[i] = 0                   ' Zerujemy cyfrę
      bc -= 1
    Next

    If i < n Then Exit While      ' Wychodzimy z pętli zwiększania licznika
    b += 1                       ' Licznik się przewinął, zwiększamy bazę
  Wend
Wend

' Wyświetlamy wyniki

Print
For v = 0 To n - 1
  Print "vertex";v;" has color";CT[v]
Next 
Print
Print "graph chromatic number =";b
Print "number of tries        = ";cnt
Print

' Usuwamy tablice dynamiczne

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

Delete [] graf
Delete [] CT

End
Wynik
9 22
0 1 0 3 0 4
1 2 1 3 1 5 1 6
2 3 2 4 2 5 2 7
3 4 3 6 3 7
4 5 4 6 4 8
5 6 5 7 5 8
6 7
7 8

vertex 0 has color 0
vertex 1 has color 1
vertex 2 has color 0
vertex 3 has color 2
vertex 4 has color 1
vertex 5 has color 2
vertex 6 has color 0
vertex 7 has color 1
vertex 8 has color 0

graph chromatic number = 3
number of tries        = 3131

 

 

Algorytm zachłanny

Jednym z algorytmów kolorujących grafy jest prosty algorytm zachłanny, który działa w sposób następujący:

 

Kolory są reprezentowane przez kolejne liczby 0,1,2,...

Wybieramy w grafie dowolny wierzchołek i kolorujemy go pierwszym kolorem nr 0.

Dla każdego z pozostałych wierzchołków grafu kolor ustalamy jako najniższy kolor, który nie jest użyty przez żadnego z jego sąsiadów.

 

Zobaczmy na przykładzie, jak działa ten algorytm.

 

Oto graf do pokolorowania. Początkowo rezerwujemy tyle kolorów, ile graf posiada wierzchołków. Kolory numerujemy odpowiednio od 0 do 5.
W grafie wybieramy wierzchołek nr 0 (może być to dowolny inny wierzchołek) i kolorujemy go pierwszym kolorem nr 0, czyli kolorem czerwonym.
Wybieramy wierzchołek nr 1. Przeglądamy wszystkich jego sąsiadów (0, 2, 4, 5) i wykreślamy z tabeli kolory zużyte. W tym przypadku będzie to kolor czerwony nr 0 wierzchołka nr 0. Z pozostałych kolorów wybieramy kolor o najniższym numerze 1 i przypisujemy go wierzchołkowi nr 1.
Wybieramy wierzchołek nr 2. Eliminujemy z listy kolory jego sąsiadów. Tutaj będzie to kolor nr 1 wierzchołka nr 1. Z pozostałych kolorów wybieramy najniższy, czyli kolor nr 0. Kolor ten przypisujemy wierzchołkowi nr 2.
Wybieramy wierzchołek nr 3. Na liście kolorów eliminujemy kolor czerwony nr 2, którym jest pokolorowany sąsiad nr 2. Z pozostałych na liście kolorów wybieramy kolor żółty nr 1 i kolorujemy nim wierzchołek nr 3.
Wybieramy wierzchołek nr 4. Z listy kolorów wykreślamy kolor czerwony nr 0 (sąsiad 0) oraz kolor żółty nr 1 (sąsiedzi nr 1 i 3). Z pozostałych kolorów wybieramy kolor zielony nr 2 (kolor o najniższym numerze) i nim kolorujemy wierzchołek nr 4.
Wybieramy ostatni wierzchołek nr 5. Jego sąsiedzi mają kolory nr 1 i 2, które wykreślamy z listy. Jako kolor wierzchołka nr 5 wybieramy kolor czerwony nr 0, ponieważ posiada on najniższy numer.

Graf jest pokolorowany. Zużyliśmy 3 kolory: czerwony 0, żółty 1 i zielony 2.

 

Algorytm zachłannego kolorowania grafu

Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.
Wyjście:
CT  –  n elementowa tablica, która określa numery kolorów wierzchołków. Elementy są liczbami całkowitymi. CT[i] jest kolorem i-tego wierzchołka grafu.
Elementy pomocnicze:
C  –  n elementowa tablica logiczna dostępności kolorów
i  –  zmienna do indeksowania tablicy C, i symbol C
u,v  –  numery wierzchołków grafu, u,v symbol C
Lista kroków:
K01: Wypełnij tablicę CT wartościami -1 ; -1 oznacza brak przypisanego koloru
K02: CT[0] ← 0 ; pierwszemu wierzchołkowi przypisujemy najniższy kolor.
K03: Dla v = 1,2,...,n - 1  wykonuj K04...K08 ; przechodzimy przez pozostałe wierzchołki grafu
K04:     Wypełnij tablicę C wartościami false ; oznaczamy wszystkie kolory jako niezajęte
K05     Dla każdego sąsiada u wierzchołka v wykonuj:
        Jeśli CT[u] > - 1, to C[CT[u]] ← true
; przeglądamy sąsiadów wierzchołka v
; kolor sąsiada oznaczamy jako zajęty
K06:     i = 0  
K07:     Dopóki C[i] = true, wykonuj ii + 1 ; szukamy najniższego z dostępnych kolorów
K08:     CT[v] ← i ; znaleziony kolor przypisujemy wierzchołkowi v
K09: Zakończ z wynikiem CT  

 

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 odczytuje definicję grafu nieskierowanego i koloruje jego wierzchołki. Na koniec wyświetla dla każdego wierzchołka numer przydzielonego mu koloru.

Przykładowe dane dla programu:

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

 

Lazarus
// Zachłanne kolorowanie grafu nieskierowanego
// Data   : 22.05.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------------------

program graph_coloring;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

var
  n,m,i,u,v : integer;
  graf      : array of PslistEl;
  CT        : array of integer;
  C         : array of boolean;
  p,r       : PslistEl;

begin
  read(n,m);                      // Odczytujemy liczbę wierzchołków i krawędzi grafu

  SetLength(graf,n);              // Tablica list sąsiedztwa
  for i := 0 to n - 1 do graf[i] := nil;

  SetLength(CT,n);                // Tablica kolorów wierzchołków
  SetLength(C,n);                 // Tablica dostępności kolorów

  // Odczytujemy krawędzie grafu

  for i := 1 to m do
  begin
    read(u,v);                    // Wierzchołki krawędzi
    new(p);                       // Tworzymy element listy
    p^.v := u;
    p^.next := graf[v];           // Element dołączamy do listy sąsiadów v
    graf[v] := p;

    new(p);                       // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := graf[u];           // Element dołączamy do listy sąsiadów u
    graf[u] := p;
  end;

  // Rozpoczynamy algorytm kolorowania grafu

  for i := 1 to n - 1 do CT[i] := -1;

  CT[0] := 0;                     // Kolor pierwszego wierzchołka

  for v := 1 to n - 1 do
  begin
    for i := 0 to n - 1 do C[i] := false;

    p := graf[v];                 // Przeglądamy listę sąsiadów v
    while p <> nil do
    begin
      if CT[p^.v] > - 1 then C[CT[p^.v]] := true; // Kolor u zaznaczamy jako zajęty
      p := p^.next;               // Następny sąsiad
    end;
    i := 0;
    while C[i] do inc(i);         // Szukamy wolnego koloru
    CT[v] := i;                   // Kolorujemy wierzchołek v
  end;

  // Wyświetlamy wyniki

  writeln;
  for v := 0 to n - 1 do
    writeln('vertex ',v,' has color ',CT[v]);

  // Usuwamy tablice dynamiczne

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

  SetLength(graf,0);
  SetLength(CT,0);
  SetLength(C,0);

end.
Code::Blocks
// Zachłanne kolorowanie grafu nieskierowanego
// Data   : 22.05.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 main()
{
  int n,m,i,u,v;
  slistEl **graf, *p, *r;
  int *CT;
  bool *C;

  cin >> n >> m;                  // Odczytujemy liczbę wierzchołków i krawędzi grafu

  graf = new slistEl * [n];       // Tablica list sąsiedztwa
  for(i = 0; i < n; i++) graf[i] = NULL;

  CT = new int [n];               // Tablica kolorów wierzchołków
  C  = new bool [n];              // Tablica dostępności kolorów

  // Odczytujemy krawędzie grafu

  for(i = 0; i < m; i++)
  {
    cin >> u >> v;                // Wierzchołki krawędzi
    p = new slistEl;              // Tworzymy element listy
    p->v = u;
    p->next = graf[v];            // Element dołączamy do listy sąsiadów v
    graf[v] = p;

    p = new slistEl;              // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf[u];            // Element dołączamy do listy sąsiadów u
    graf[u] = p;
  }

  // Rozpoczynamy algorytm kolorowania grafu

  for(i = 1; i < n; i++) CT[i] = -1;

  CT[0] = 0;                      // Kolor pierwszego wierzchołka

  for(v = 1; v < n; v++)
  {
    for(i = 0; i < n; i++) C[i] = false;

    for(p = graf[v]; p; p = p->next) // Przeglądamy listę sąsiadów v
      if(CT[p->v] > - 1) C[CT[p->v]] = true; // Kolor u zaznaczamy jako zajęty

    for(i = 0; C[i]; i++);        // Szukamy wolnego koloru
    CT[v] = i;                    // Kolorujemy wierzchołek v
  }

  // Wyświetlamy wyniki

  cout << endl;
  for(v = 0; v < n; v++)
    cout << "vertex " << v << " has color " << CT[v] << endl;

  // Usuwamy tablice dynamiczne

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

  delete [] graf;
  delete [] CT;
  delete [] C;

  return 0;
}
Free Basic
' Zachłanne kolorowanie grafu nieskierowanego
' Data   : 22.05.2014
' (C)2014 mgr Jerzy Wałaszek
'--------------------------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  next As slistEl Ptr             ' Następny element listy
  v As Integer                    ' Wierzchołek docelowy
End Type

Dim As Integer n,m,i,u,v
Dim As slistEl Ptr Ptr graf
Dim As slistEl Ptr p, r
Dim As integer Ptr CT
Dim As Byte Ptr C

Open Cons For Input As #1

Input #1,n,m                      ' Odczytujemy liczbę wierzchołków i krawędzi grafu

graf = New slistEl Ptr [n]        ' Tablica list sąsiedztwa
For i = 0 To n - 1
  graf[i] = 0
Next

CT = New Integer [n]              ' Tablica kolorów wierzchołków
C  = New Byte [n]                 ' Tablica dostępności kolorów

' Odczytujemy krawędzie grafu

For i = 1 To m
  Input #1,u,v                    ' Wierzchołki krawędzi
  p = New slistEl                 ' Tworzymy element listy
  p->v = u
  p->next = graf[v]               ' Element dołączamy do listy sąsiadów v
  graf[v] = p

  p = New slistEl                 ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = graf[u]               ' Element dołączamy do listy sąsiadów u
  graf[u] = p
Next

Close #1

' Rozpoczynamy algorytm kolorowania grafu

For i = 1 To n - 1
  CT[i] = -1
Next

CT[0] = 0                         ' Kolor pierwszego wierzchołka

For v = 1 To n - 1
  For i = 0 To n - 1
  	 C[i] = 0
  Next

  p = graf[v]
  While p                         ' Przeglądamy listę sąsiadów v
    If CT[p->v] > - 1 Then C[CT[p->v]] = 1 ' Kolor u zaznaczamy jako zajęty
    p = p->Next                   ' Następny sąsiad
  Wend
  
  i = 0
  While C[i] = 1                  ' Szukamy wolnego koloru
    i += 1
  Wend
  
  CT[v] = i                       ' Kolorujemy wierzchołek v
Next

' Wyświetlamy wyniki

Print
For v = 0 To n - 1
  Print "vertex";v;" has color";CT[v]
Next

' Usuwamy tablice dynamiczne

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

Delete [] graf
Delete [] CT
Delete [] C

End
Wynik
6 9
0 1 0 4
1 2 1 4 1 5
2 3
3 4 3 5
4 5

vertex 0 has color 0
vertex 1 has color 1
vertex 2 has color 0
vertex 3 has color 1
vertex 4 has color 2
vertex 5 has color 0

 

Algorytm heurystyczny

Zmieniając odpowiednio kolejność przetwarzanych w algorytmie wierzchołków, da się uzyskać lepsze przybliżenie kolorowania dokładnego. Na tej zasadzie działają różne algorytmy heurystyczne. Poniżej przedstawiamy jeden z najprostszych algorytmów heurystycznych.

Algorytm LF (ang. Largest First)

Najpierw tworzymy ciąg wierzchołków uporządkowany malejąco wg stopni wyjściowych. Następnie wierzchołki te kolorujemy zachłannie wg tej kolejności.

Algorytm LF kolorowania grafu

Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.
Wyjście:
CT  –  n elementowa tablica, która określa numery kolorów wierzchołków. Elementy są liczbami całkowitymi. CT[i] jest kolorem i-tego wierzchołka grafu.
Elementy pomocnicze:
C  –  n elementowa tablica logiczna dostępności kolorów
VT  –  n elementowa tablica numerów wierzchołków grafu
DT  –  n elementowa tablica stopni wyjściowych wierzchołków grafu
i  –  zmienna do indeksowania, i symbol C
u,v  –  numery wierzchołków grafu, u,v symbol C
d  –  przechowuje stopień wierzchołka w czasie sortowania, d symbol C
Lista kroków:
K01: Dla v = 0,1,...,n - 1 wykonuj K02...K13 ; przeglądamy kolejne wierzchołki grafu
K02:     VT[v] ← v ; umieszczamy numer wierzchołka w tablicy VT
K03:     DT[v] ← 0 ; zerujemy stopień wyjściowy wierzchołka v
K04:     Dla każdego sąsiada u wierzchołka v wykonuj:
        DT[v] ← DT[v] + 1

; obliczamy stopień wyjściowy wierzchołka v
K05:     dDT[v] ; sortujemy tablice VT i DT malejąco względem stopni wychodzących
K06:     iv  
K07:     Dopóki (i > 0) (DT[i - 1] < d) wykonuj K08...K10 ; szukamy pozycji wierzchołka w posortowanych tablicach
K08:         DT[i] ← DT[i - 1] ; przesuwamy elementy w DT, aby zrobić miejsce dla d
K09:         VT[i] ← VT[i - 1] ; to samo w tablicy VT
K10:         ii - 1 ; cofamy się o jedną pozycję
K11:     DT[i] ← d ; element wstawiamy na właściwe miejsce w obu tablicach
K12:     VT[i] ← v  
K13: Wypełnij tablicę CT wartościami -1 ; -1 oznacza brak przypisanego koloru
K14: CT[VT[0]] ← 0 ; pierwszemu wierzchołkowi wg VT przypisujemy najniższy kolor.
K15: Dla v = 1,2,...,n - 1  wykonuj K16...K20 ; przechodzimy przez pozostałe wierzchołki grafu
K16:     Wypełnij tablicę C wartościami false ; oznaczamy wszystkie kolory jako niezajęte
K17     Dla każdego sąsiada u wierzchołka VT[v] wykonuj:
        Jeśli CT[u] > - 1, to C[CT[u]] ← true
; przeglądamy sąsiadów wierzchołka VT[v]
; kolor sąsiada oznaczamy jako zajęty
K18:     i = 0  
K19:     Dopóki C[i] = true, wykonuj ii + 1 ; szukamy najniższego z dostępnych kolorów
K20:     CT[VT[v]] ← i ; znaleziony kolor przypisujemy wierzchołkowi VT[v]
K21: Zakończ z wynikiem CT  

 

Klasę złożoności algorytmu można poprawić przez zastosowanie lepszego algorytmu sortującego. Rozwiązanie tego problemu pozostawiam zdolnym czytelnikom.

 

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 odczytuje definicję grafu nieskierowanego i koloruje jego wierzchołki. Na koniec wyświetla dla każdego wierzchołka numer przydzielonego mu koloru.

Przykładowe dane dla programu:

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

 

Lazarus
// Algorytm LF kolorowania grafu nieskierowanego
// Data   : 24.05.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

program lf_algorithm;

// Definicja elementu listy sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    v : integer;                  // Wierzchołek docelowy
  end;

var
  n,m,i,u,v,d : integer;
  graf        : array of PslistEl;
  CT,DT,VT    : array of integer;
  C           : array of boolean;
  p,r         : PslistEl;

begin
  read(n,m);                      // Odczytujemy liczbę wierzchołków i krawędzi grafu

  SetLength(graf,n);              // Rablica list sąsiedztwa
  for i := 0 to n - 1 do graf[i] := nil;

  SetLength(CT,n);                // Tablica kolorów wierzchołków
  SetLength(DT,n);                // Tablica stopni wyjściowych wierzchołków
  SetLength(VT,n);                // Tablica numerów wierzchołków
  SetLength(C,n);                 // Tablica dostępności kolorów

  // Odczytujemy krawędzie grafu

  for i := 1 to m do
  begin
    read(u,v);                    // Wierzchołki krawędzi
    new(p);                       // Tworzymy element listy
    p^.v := u;
    p^.next := graf[v];           // Element dołączamy do listy sąsiadów v
    graf[v] := p;

    new(p);                       // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := graf[u];           // Element dołączamy do listy sąsiadów u
    graf[u] := p;
  end;

  // Rozpoczynamy algorytm kolorowania grafu

  for v := 0 to n - 1 do          // Przeglądamy kolejne wierzchołki grafu
  begin
    VT[v] := v;                   // Zapamiętujemy numer wierzchołka
    DT[v] := 0;                   // Zerujemy jego stopień wyjściowy

    p := graf[v];                 // Przeglądamy kolejnych sąsiadów
    while p <> nil do
    begin
      inc(DT[v]);                 // Obliczamy stopień wyjściowy wierzchołka v
      p := p^.next;               // Następny sąsiad
    end;

    // Sortujemy DT i VT

    d := DT[v];                   // Zapamiętujemy wyliczony stopień wyjściowy
    i := v;                       // Pozycja wstawiania elementu
    while (i > 0) and (DT[i-1] < d) do // Szukamy miejsca na wstawienie
    begin
      DT[i] := DT[i - 1];         // Przesuwamy elementy obu tablic
      VT[i] := VT[i - 1];
      dec(i);                     // Nowa pozycja wstawiania
    end;
    DT[i] := d;                   // Wstawiamy element
    VT[i] := v;
  end;

  // Teraz stosujemy algorytm zachłanny, lecz wierzchołki wybieramy wg VT

  for i := 0 to n - 1 do CT[i] := -1;

  CT[VT[0]] := 0;                 // Wierzchołek startowy

  for v := 1 to n - 1 do          // Przeglądamy resztę grafu
  begin
    for i := 0 to n - 1 do C[i] := false;
    p := graf[VT[v]];             // Przeglądamy sąsiadów bieżącego wierzchołka
    while p <> nil do
    begin
      if CT[p^.v] > -1 then C[CT[p^.v]] := true; // Oznaczamy kolor jako zajęty
      p := p^.next;               // Następny sąsiad
    end;
    i := 0;
    while C[i] do inc(i);         // Szukamy wolnego koloru
    CT[VT[v]] := i;               // Przypisujemy go bieżącemu wierzchołkowi
  end;

  // Wyświetlamy wyniki

  writeln;
  for v := 0 to n - 1 do
    writeln('vertex ',v,' has color ',CT[v]);
  writeln;

  // Usuwamy tablice dynamiczne

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

  SetLength(graf,0);
  SetLength(CT,0);
  SetLength(DT,0);
  SetLength(VT,0);
  SetLength(C,0);

end.
Code::Blocks
// Algorytm LF kolorowania grafu nieskierowanego
// Data   : 24.05.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 main()
{
  int n,m,i,u,v,d,*CT,*DT,*VT;
  slistEl **graf,*p,*r;
  bool *C;

  cin >> n >> m;                  // Odczytujemy liczbę wierzchołków i krawędzi grafu

  graf = new slistEl * [n];       // Tablica list sąsiedztwa
  for(i = 0; i < n; i++) graf[i] = NULL;

  CT = new int [n];               // Tablica kolorów wierzchołków
  DT = new int [n];               // Tablica stopni wyjściowych wierzchołków
  VT = new int [n];               // Tablica numerów wierzchołków
  C  = new bool [n];              // Tablica dostępności kolorów

  // Odczytujemy krawędzie grafu

  for(i = 0; i < m; i++)
  {
    cin >> u >> v;                // Wierzchołki krawędzi
    p = new slistEl;              // Tworzymy element listy
    p->v = u;
    p->next = graf[v];            // Element dołączamy do listy sąsiadów v
    graf[v] = p;

    p = new slistEl;              // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf[u];            // Element dołączamy do listy sąsiadów u
    graf[u] = p;
  }

  // Rozpoczynamy algorytm kolorowania grafu

  for(v = 0; v < n; v++)          // Przeglądamy kolejne wierzchołki grafu
  {
    VT[v] = v;                    // Zapamiętujemy numer wierzchołka
    DT[v] = 0;                    // Zerujemy jego stopień wyjściowy

    for(p = graf[v]; p; p = p->next) // Przeglądamy kolejnych sąsiadów
      DT[v]++;                    // Obliczamy stopień wyjściowy wierzchołka v

    // Sortujemy DT i VT

    d = DT[v];

    for(i = v; (i > 0) && (DT[i-1] < d); i--)
    {
      DT[i] = DT[i - 1];
      VT[i] = VT[i - 1];
    }

    DT[i] = d;
    VT[i] = v;
  }

  // Teraz stosujemy algorytm zachłanny, lecz wierzchołki wybieramy wg VT

  for(i = 0; i < n; i++) CT[i] = -1;

  CT[VT[0]] = 0;                  // Wierzchołek startowy

  for(v = 1; v < n; v++)          // Przeglądamy resztę grafu
  {
    for(i = 0; i < n; i++) C[i] = false;

    for(p = graf[VT[v]]; p; p = p->next) // Przeglądamy sąsiadów bieżącego wierzchołka
      if(CT[p->v] > -1) C[CT[p->v]] = true; // Oznaczamy kolor jako zajęty

    for(i = 0; C[i]; i++);        // Szukamy wolnego koloru

    CT[VT[v]] = i;                // Przypisujemy go bieżącemu wierzchołkowi
  }

  // Wyświetlamy wyniki

  cout << endl;
  for(v = 0; v < n; v++)
    cout << "vertex " << v << " has color " << CT[v] << endl;
  cout << endl;

  // Usuwamy tablice dynamiczne

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

  delete [] graf;
  delete [] CT;
  delete [] DT;
  delete [] VT;
  delete [] C;

  return 0;
}
Free Basic
' Algorytm LF kolorowania grafu nieskierowanego
' Data   : 24.05.2014
' (C)2014 mgr Jerzy Wałaszek
'--------------------------------------------

' Definicja elementu listy sąsiedztwa

Type slistEl
  next As slistEl Ptr             ' Następny element listy
  v As Integer                    ' Wierzchołek docelowy
End Type

Dim As Integer n,m,i,u,v,d
Dim As Integer Ptr CT,DT,VT
Dim As slistEl Ptr Ptr graf
Dim As slistEl Ptr p,r
Dim As Byte Ptr C

Open Cons For Input As #1

Input #1,n,m                      ' Odczytujemy liczbę wierzchołków i krawędzi grafu

graf = New slistEl Ptr [n]        ' Tablica list sąsiedztwa
For i = 0 To n - 1
  graf[i] = 0
Next

CT = New Integer [n]              ' Tablica kolorów wierzchołków
DT = New Integer [n]              ' Tablica stopni wyjściowych wierzchołków
VT = New Integer [n]              ' Tablica numerów wierzchołków
C  = New Byte [n]                 ' Tablica dostępności kolorów

' Odczytujemy krawędzie grafu

For i = 1 To m
  Input #1,u,v                    ' Wierzchołki krawędzi
  p = New slistEl                 ' Tworzymy element listy
  p->v = u
  p->next = graf[v]               ' Element dołączamy do listy sąsiadów v
  graf[v] = p

  p = New slistEl                 ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = graf[u]               ' Element dołączamy do listy sąsiadów u
  graf[u] = p
Next

Close #1

' Rozpoczynamy algorytm kolorowania grafu

For v = 0 To n - 1                ' Przeglądamy kolejne wierzchołki grafu
  VT[v] = v                       ' Zapamiętujemy numer wierzchołka
  DT[v] = 0                       ' Zerujemy jego stopień wyjściowy

  p = graf[v]
  While p                         ' Przeglądamy kolejnych sąsiadów
    DT[v] += 1                    ' Obliczamy stopień wyjściowy wierzchołka v
    p = p->Next                   ' Następny sąsiad
  Wend
  
  ' Sortujemy DT i VT

  d = DT[v]

  i = v
  While (i > 0) AndAlso (DT[i-1] < d)
    DT[i] = DT[i - 1]
    VT[i] = VT[i - 1]
    i -= 1
  Wend
  
  DT[i] = d
  VT[i] = v
Next

' Teraz stosujemy algorytm zachłanny, lecz wierzchołki wybieramy wg VT

For i = 0 To n - 1
  CT[i] = -1
Next

CT[VT[0]] = 0                     ' Wierzchołek startowy

For v = 1 To n - 1                ' Przeglądamy resztę grafu
  For i = 0 To n - 1
  	 C[i] = 0
  Next

  p = graf[VT[v]]
  While p                    ' Przeglądamy sąsiadów bieżącego wierzchołka
    If CT[p->v] > -1 Then C[CT[p->v]] = 1 ' Oznaczamy kolor jako zajęty
    p = p->Next                   ' Następny sąsiad
  Wend
  
  i = 0
  While C[i] = 1                  ' Szukamy wolnego koloru
    i += 1
  Wend
  
  CT[VT[v]] = i                   ' Przypisujemy go bieżącemu wierzchołkowi
Next

' Wyświetlamy wyniki

Print
For v = 0 To n - 1
  Print "vertex";v;" has color";CT[v]
Next
Print

' Usuwamy tablice dynamiczne

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

Delete [] graf
Delete [] CT
Delete [] DT
Delete [] VT
Delete [] C

End
Wynik
9 29
0 1 0 2 0 3 0 4 0 6 0 7 0 8
1 2 1 3 1 4 1 5 1 6 1 8
2 3 2 4 2 5 2 7 2 8
3 6 3 7 3 8
4 5 4 6 4 8
5 7 5 8
6 7 6 8
7 8

vertex 0 has color 1
vertex 1 has color 2
vertex 2 has color 3
vertex 3 has color 4
vertex 4 has color 4
vertex 5 has color 1
vertex 6 has color 3
vertex 7 has color 2
vertex 8 has color 0

 

Kolorowanie krawędzi grafu

Problem kolorowania grafu przenosi się czasem na krawędzie, które należy pokolorować tak, aby żadne dwie krawędzie połączone wspólnym wierzchołkiem nie posiadały tego samego koloru. Zadanie to rozwiązujemy dwuetapowo. Najpierw tworzymy graf krawędziowy. Następnie kolorujemy wierzchołki grafu krawędziowego. Kolory wierzchołków grafu krawędziowego odpowiadają kolorom krawędzi grafu wyjściowego. Zadanie zostaje więc rozwiązane.

 

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 odczytuje definicję grafu nieskierowanego i koloruje jego krawędzie. Na koniec wyświetla dla każdej krawędzi numer przydzielonego jej koloru.

Przykładowe dane dla programu:

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

 

Lazarus
// Algorytm kolorowania krawędzi grafu nieskierowanego
// Data   : 26.05.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------------

program edge_coloring;

// 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,i,u,v,d : integer;
  G,GE        : array of PslistEl;
  CT,DT,VT    : array of integer;
  C           : array of boolean;
  p,r,s       : PslistEl;

begin
  read(n,m);                      // Odczytujemy liczbę wierzchołków i krawędzi 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;

  SetLength(CT,m);                // Tablica kolorów wierzchołków
  SetLength(DT,m);                // Tablica stopni wyjściowych wierzchołków
  SetLength(VT,m);                // Tablica numerów wierzchołków
  SetLength(C,m);                 // Tablica dostępności kolorów

  // Odczytujemy definicje krawędzi grafu G

  for i := 0 to m - 1 do
  begin
    read(v,u);                    // Czytamy wierzchołki
    new(p);                       // Tworzymy rekord listy
    p^.v := u;                    // Wypełniamy go danymi
    p^.i := i;
    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 := i;
    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;

  // Rozpoczynamy algorytm kolorowania grafu krawędziowego

  for v := 0 to m - 1 do          // Przeglądamy kolejne wierzchołki grafu
  begin
    VT[v] := v;                   // Zapamiętujemy numer wierzchołka
    DT[v] := 0;                   // Zerujemy jego stopień wyjściowy

    p := GE[v];                   // Przeglądamy kolejnych sąsiadów
    while p <> nil do
    begin
      inc(DT[v]);                 // Obliczamy stopień wyjściowy wierzchołka v
      p := p^.next;               // Następny sąsiad
    end;

    // Sortujemy DT i VT

    d := DT[v];                   // Zapamiętujemy wyliczony stopień wyjściowy
    i := v;                       // Pozycja wstawiania elementu
    while (i > 0) and (DT[i-1] < d) do // Szukamy miejsca na wstawienie
    begin
      DT[i] := DT[i - 1];         // Przesuwamy elementy obu tablic
      VT[i] := VT[i - 1];
      dec(i);                     // Nowa pozycja wstawiania
    end;
    DT[i] := d;                   // Wstawiamy element
    VT[i] := v;
  end;

  // Teraz stosujemy algorytm zachłanny, lecz wierzchołki wybieramy wg VT

  for i := 0 to m - 1 do CT[i] := -1;

  CT[VT[0]] := 0;                 // Wierzchołek startowy

  for v := 1 to m - 1 do          // Przeglądamy resztę grafu
  begin
    for i := 0 to m - 1 do C[i] := false;
    p := GE[VT[v]];               // Przeglądamy sąsiadów bieżącego wierzchołka
    while p <> nil do
    begin
      if CT[p^.v] > -1 then C[CT[p^.v]] := true; // Oznaczamy kolor jako zajęty
      p := p^.next;               // Następny sąsiad
    end;
    i := 0;
    while C[i] do inc(i);         // Szukamy wolnego koloru
    CT[VT[v]] := i;               // Przypisujemy go bieżącemu wierzchołkowi
  end;

  // Wyświetlamy wyniki

  writeln;
  for i := 0 to m - 1 do C[i] := true;
  for v := 0 to n - 1 do
  begin
    p := G[v];
    while p <> nil do
    begin
      if C[p^.i] then
      begin
        C[p^.i] := false;
        writeln('edge ',v,'-',p^.v,' has color ',CT[p^.i]);
      end;
      p := p^.next;
    end;
  end;
  writeln;

  // Usuwamy tablice dynamiczne

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

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

  SetLength(G,0);
  SetLength(GE,0);
  SetLength(CT,0);
  SetLength(DT,0);
  SetLength(VT,0);
  SetLength(C,0);

end.
Code::Blocks
// Algorytm kolorowania krawędzi grafu nieskierowanego
// Data   : 26.05.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,i,u,v,d,*CT,*DT,*VT;
  slistEl **G,**GE,*p,*r,*s;
  bool *C;

  cin >> n >> m;                  // Odczytujemy liczbę wierzchołków i krawędzi 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;

  CT = new int [m];               // Tablica kolorów wierzchołków
  DT = new int [m];               // Tablica stopni wyjściowych wierzchołków
  VT = new int [m];               // Tablica numerów wierzchołków
  C  = new bool [m];              // Tablica dostępności kolorów

  // Odczytujemy definicje krawędzi grafu G

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;                // Czytamy wierzchołki
    p = new slistEl;              // Tworzymy rekord listy
    p->v = u;                     // Wypełniamy go danymi
    p->i = i;
    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 = i;
    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
        }

  // Rozpoczynamy algorytm kolorowania grafu krawędziowego

  for(v = 0; v < m; v++)          // Przeglądamy kolejne wierzchołki grafu
  {
    VT[v] = v;                    // Zapamiętujemy numer wierzchołka
    DT[v] = 0;                    // Zerujemy jego stopień wyjściowy

    for(p = GE[v]; p; p = p->next) // Przeglądamy kolejnych sąsiadów
      DT[v]++;                    // Obliczamy stopień wyjściowy wierzchołka v

    // Sortujemy DT i VT

    d = DT[v];

    for(i = v; (i > 0) && (DT[i-1] < d); i--)
    {
      DT[i] = DT[i - 1];
      VT[i] = VT[i - 1];
    }

    DT[i] = d;
    VT[i] = v;
  }

  // Teraz stosujemy algorytm zachłanny, lecz wierzchołki wybieramy wg VT

  for(i = 0; i < m; i++) CT[i] = -1;

  CT[VT[0]] = 0;                  // Wierzchołek startowy

  for(v = 1; v < m; v++)          // Przeglądamy resztę grafu
  {
    for(i = 0; i < m; i++) C[i] = false;

    for(p = GE[VT[v]]; p; p = p->next) // Przeglądamy sąsiadów bieżącego wierzchołka
      if(CT[p->v] > -1) C[CT[p->v]] = true; // Oznaczamy kolor jako zajęty

    for(i = 0; C[i]; i++);        // Szukamy wolnego koloru

    CT[VT[v]] = i;                // Przypisujemy go bieżącemu wierzchołkowi
  }

  // Wyświetlamy wyniki

  cout << endl;
  for(i = 0; i < m; i++) C[i] = true;
  for(v = 0; v < n; v++)
    for(p = G[v]; p; p = p->next)
      if(C[p->i])
      {
        C[p->i] = false;
        cout << "edge " << v << "-" << p->v << " has color " << CT[p->i] << endl;
      }
  cout << endl;

  // Usuwamy tablice dynamiczne

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

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

  delete [] G;
  delete [] GE;
  delete [] CT;
  delete [] DT;
  delete [] VT;
  delete [] C;

  return 0;
}
Free Basic
' Algorytm kolorowania krawędzi grafu nieskierowanego
' Data   : 26.05.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,i,u,v,d
Dim As Integer Ptr CT,DT,VT
Dim As slistEl Ptr Ptr G,GE
Dim As slistEl Ptr p,r,s
Dim As Byte Ptr C

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

CT = New Integer [m]              ' Tablica kolorów wierzchołków
DT = New Integer [m]              ' Tablica stopni wyjściowych wierzchołków
VT = New Integer [m]              ' Tablica numerów wierzchołków
C  = New Byte [m]                 ' Tablica dostępności kolorów

  ' Odczytujemy definicje krawędzi grafu G

For i = 0 To m - 1
  Input #1,v,u                    ' Czytamy wierzchołki
  p = New slistEl                 ' Tworzymy element listy
  p->v = u                        ' Wypełniamy go danymi
  p->i = i
  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 = i
  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

' Rozpoczynamy algorytm kolorowania grafu krawędziowego

For v = 0 To m - 1                ' Przeglądamy kolejne wierzchołki grafu
  VT[v] = v                       ' Zapamiętujemy numer wierzchołka
  DT[v] = 0                       ' Zerujemy jego stopień wyjściowy

  p = GE[v]
  While p                         ' Przeglądamy kolejnych sąsiadów
    DT[v] += 1                    ' Obliczamy stopień wyjściowy wierzchołka v
    p = p->Next                   ' Następny sąsiad
  Wend
  
  ' Sortujemy DT i VT

  d = DT[v]

  i = v
  While (i > 0) AndAlso (DT[i-1] < d)
    DT[i] = DT[i - 1]
    VT[i] = VT[i - 1]
    i -= 1
  Wend
  
  DT[i] = d
  VT[i] = v
Next

' Teraz stosujemy algorytm zachłanny, lecz wierzchołki wybieramy wg VT

For i = 0 To m - 1
  CT[i] = -1
Next

CT[VT[0]] = 0                     ' Wierzchołek startowy

For v = 1 To m - 1                ' Przeglądamy resztę grafu
  For i = 0 To m - 1
  	 C[i] = 0
  Next

  p = GE[VT[v]]
  While p                         ' Przeglądamy sąsiadów bieżącego wierzchołka
    If CT[p->v] > -1 Then C[CT[p->v]] = 1 ' Oznaczamy kolor jako zajęty
    p = p->Next                   ' Następny sąsiad
  Wend
  
  i = 0
  While C[i] = 1                  ' Szukamy wolnego koloru
    i += 1
  Wend
  
  CT[VT[v]] = i                   ' Przypisujemy go bieżącemu wierzchołkowi
Next

' Wyświetlamy wyniki

Print
For i = 0 To m - 1
  C[i] = 1
Next

For v = 0 To n - 1
  p = G[v]
  While p 
    If C[p->i] = 1 Then
      C[p->i] = 0
      Print Using "edge &-& has color &";v;p->v;CT[p->i]
    End If
    p = p->Next
  Wend
Next
Print

' Usuwamy tablice dynamiczne

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

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

Delete [] G
Delete [] GE
Delete [] CT
Delete [] DT
Delete [] VT
Delete [] C

End
Wynik
9 29
0 1 0 2 0 3 0 4 0 6 0 7 0 8
1 2 1 3 1 4 1 5 1 6 1 8
2 3 2 4 2 5 2 7 2 8
3 6 3 7 3 8
4 5 4 6 4 8
5 7 5 8
6 7 6 8
7 8

edge 0-8 has color 0
edge 0-7 has color 5
edge 0-6 has color 6
edge 0-4 has color 3
edge 0-3 has color 4
edge 0-2 has color 1
edge 0-1 has color 2
edge 1-8 has color 1
edge 1-6 has color 3
edge 1-5 has color 4
edge 1-4 has color 6
edge 1-3 has color 5
edge 1-2 has color 0
edge 2-8 has color 2
edge 2-7 has color 3
edge 2-5 has color 8
edge 2-4 has color 5
edge 2-3 has color 6
edge 3-8 has color 3
edge 3-7 has color 1
edge 3-6 has color 0
edge 4-8 has color 4
edge 4-6 has color 1
edge 4-5 has color 0
edge 5-8 has color 7
edge 5-7 has color 9
edge 6-8 has color 5
edge 6-7 has color 2
edge 7-8 has color 6

 



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.