Algorytmy i Struktury Danych - Kolorowanie grafu

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

Elementy pomocnicze:

bc	:	zlicza ilość najstarszych cyfr-kolorów w liczniku, bc ∈ C.
i	:	zmienna do indeksowania cyfr w tablicy CT, i ∈ C.
u, v	:	numery wierzchołków grafu, u, v ∈ 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 kroku K09	pomijamy test pokolorowania, jeśli brak najstarszej cyfry w liczniku
K05:	Dla v = 0, 1, …, n : wykonuj kroki K06…K07	przeglądamy kolejne wierzchołki grafu
K06:	Dla każdego sąsiada u wierzchołka v : wykonuj krok K07	przeglądamy wszystkich sąsiadów
K07:	Jeśli CT [v] = CT [u ], to idź do kroku 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 bc ← bc+1	zliczamy najstarsze cyfry
K12:	Jeśli CT [i ] < b, to idź do kroku K04	kontynuujemy z następną kombinacją kolorów
K13:	CT [i] ← 0	jeśli cyfra jest równa podstawie, to zerujemy cyfrę licznika
K14:	bc ← bc-1	zmniejszamy liczbę najstarszych cyfr
K15:	i ← i+1	przesuwamy się do następnej cyfry
K16:	Jeśli i = n, to b ← b+1, to idź do kroku K09	jeśli wyczerpaliśmy cyfry, to należy zwiększyć podstawę
K17:	Idź do K10	kontynuujemy z następną cyfrą-kolorem

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

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

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

program graph_coloring;

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

var
  b, bc, n, m, i, u, v : integer;
  graf           : array of PSLel;
  CT             : array of integer;
  p, r           : PSLel;
  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.

C++

// 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 SLel
{
  SLel *next;          // Następny element listy
  int v;                  // Wierzchołek docelowy
};

int main()
{
  int b, bc, n, m, i, u, v, *CT;
  SLel **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 SLel * [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 SLel;      // Tworzymy element listy
    p->v = u;
    p->next = graf [v]; // Element dołączamy do listy sąsiadów v
    graf [v] = p;

    p = new SLel;      // 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;}

Basic

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

' Definicja elementu listy sąsiedztwa

Type SLel
  next As SLel 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 SLel Ptr Ptr graf
Dim As SLel 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 SLel 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 SLel            ' Tworzymy element listy
  p->v = u
  p->next = graf [v]       ' Element dołączamy do listy sąsiadów v
  graf [v] = p

  p = New SLel            ' 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

Na początek: podrozdziału strony

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 ∈ C.
graf	:	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.

Wyjście:

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 ∈ C.
u, v	:	numery wierzchołków grafu, u, v ∈ 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 kroki 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: i ← i + 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

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

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

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

program graph_coloring;

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

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

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.

C++

// 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 SLel
{
  SLel * next;               // Następny element listy;
  int v;                        // Wierzchołek docelowy
};

int main()
{
  int n, m, i, u, v;
  SLel **graf, *p, *r;
  int *CT;
  bool *C;

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

  graf = new SLel * [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 SLel;            // Tworzymy element listy
    p->v = u;
    p->next = graf [v];       // Element dołączamy do listy sąsiadów v
    graf [v] = p;

    p = new SLel;            // 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;}

Basic

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

' Definicja elementu listy sąsiedztwa

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

Dim As Integer n, m, i, u, v
Dim As SLel Ptr Ptr graf
Dim As SLel 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 SLel 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 SLel      ' Tworzymy element listy
  p->v = u
  p->next = graf [v] ' Element dołączamy do listy sąsiadów v
  graf [v] = p

  p = New SLel      ' 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

Na początek: podrozdziału strony

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 ∈ C.
graf	:	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.

Wyjście:

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 ∈ C.
u, v	:	numery wierzchołków grafu, u, v ∈ C.
d	:	przechowuje stopień wierzchołka w czasie sortowania, d ∈ C.

Lista kroków:

K01:	Dla v = 0, 1, …, n-1: wykonuj kroki 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:	d ← DT [v]	sortujemy tablice VT i DT malejąco względem stopni wychodzących
K06:	i ← v
K07:	Dopóki (i > 0) (DT [i-1] < d), wykonuj kroki 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:	i ← i-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 kroki 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 i ← i+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.

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

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

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

program lf_algorithm;

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

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

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.

C++

// 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 SLel
{
  SLel * next;               // Następny element listy;
  int v;                        // Wierzchołek docelowy
};

int main()
{
  int n, m, i, u, v, d, *CT, *DT, *VT;
  SLel **graf, *p, *r;
  bool *C;

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

  graf = new SLel * [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 SLel;            // Tworzymy element listy
    p->v = u;
    p->next = graf [v];       // Element dołączamy do listy sąsiadów v
    graf [v] = p;

    p = new SLel;            // 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;}

Basic

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

' Definicja elementu listy sąsiedztwa

Type SLel
  next As SLel 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 SLel Ptr Ptr graf
Dim As SLel 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 SLel 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 SLel      ' Tworzymy element listy
  p->v = u
  p->next = graf [v] ' Element dołączamy do listy sąsiadów v
  graf [v] = p

  p = New SLel      ' 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

Na początek: podrozdziału strony

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.

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

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

// 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
  PSLel = ^SLel;
  SLel = record
    next : PSLel; // 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 PSLel;
  CT, DT, VT : array of integer;
  C          : array of boolean;
  p, r, s    : PSLel;

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.

C++

// 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 SLel
{
  SLel * 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;
  SLel **G, **GE, *p, *r, *s;
  bool *C;

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

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

  GE = new SLel * [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 SLel;   // 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 SLel;   // 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 SLel;       // 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;}

Basic

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

' Definicja elementu listy sąsiedztwa

Type SLel
  Dim Next As SLel 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 SLel Ptr Ptr G, GE
Dim As SLel Ptr p, r, s
Dim As Byte Ptr C

Open Cons For Input As #1

Input #1, n, m            ' Czytamy rozmiary grafu

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

GE = New SLel 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 SLel   ' 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 SLel   ' 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 SLel ' 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

Na początek: podrozdziału strony

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.

Kolorowanie grafu

Problem

Algorytm dokładny

Algorytm optymalnego kolorowania grafu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm zachłanny

Algorytm zachłannego kolorowania grafu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm heurystyczny

Algorytm LF (ang. Largest First)

Algorytm LF kolorowania grafu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Kolorowanie krawędzi grafu

Przykładowe programy