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:

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:

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, ; jeśli brak najstarszej cyfry w liczniku,
     to idź do kroku K09 ; pomijamy test pokolorowania
K05: Dla v = 0, 1, …, n: ; przeglądamy kolejne wierzchołki grafu
     wykonuj kroki K06…K07
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], ; sprawdzamy warunek złego pokolorowania
         to idź do kroku K09
K08: Zakończ z wynikami 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, ; zliczamy najstarsze cyfry
     to bc ← bc+1
K12: Jeśli CT[i] < b, ; kontynuujemy z następną kombinacją kolorów
     to idź do kroku K04
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, ; jeśli wyczerpaliśmy cyfry,
     i idź do kroku K09 ; 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
    // Następny element listy
    next : PSLel;
    // Wierzchołek docelowy
    v : integer;
  end;

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

begin
  // Odczytujemy liczbę
  // wierzchołków i krawędzi grafu
  read(n, m);
  // Tablica list sąsiedztwa
  SetLength(graf, n);
  for i := 0 to n-1 do
    graf[i] := nil;
  // Tablica kolorów wierzchołków
  SetLength(CT, n);
  // Odczytujemy krawędzie grafu
  for i := 1 to m do
  begin
    // Wierzchołki krawędzi
    read(u, v);
    // Tworzymy element listy
    new(p);
    p^.v := u;
    // Element dołączamy
    // do listy sąsiadów v
    p^.next := graf[v];
    graf[v] := p;
    // To samo dla krawędzi
    // w drugą stronę
    new(p);
    p^.v := v;
    // Element dołączamy
    // do listy sąsiadów u
    p^.next := graf[u];
    graf[u] := p;
  end;
  // Rozpoczynamy algorytm
  // kolorowania grafu
  cnt := 0;
  // Inicjujemy licznik
  for i := 0 to n-1 do
    CT[i] := 0;
  // Zliczanie rozpoczynamy
  // przy podstawie 2
  b := 2;
  // Liczba najstarszych cyfr
  bc := 0;
  while true do
  begin
    // Kombinację sprawdzamy,
    // gdy zawiera najstarszą
    // cyfrę
    if bc > 0 then
    begin
      test := true;
      // Zwiększamy liczbę prób
      inc(cnt);
      // Przeglądamy wierzchołki
      // grafu
      for v := 0 to n-1 do
      begin
        // Przeglądamy sąsiadów
        // wierzchołka v
        p := graf[v];
        while p <> nil do
        begin
          // Testujemy pokolorowanie
          if CT[v] = CT[p^.v] then
          begin
            // Zaznaczamy porażkę
            test := false;
            // Opuszczamy pętlę while
            break;
          end;
          // Następny sąsiad
          p := p^.next;
        end;
        // Opuszczamy pętlę for
        if not test then break;
      end;
      // Kombinacja znaleziona,
      // kończymy pętlę główną
      if test then break;
    end;
    // Pętla modyfikacji licznika
    while true do
    begin
       i := 0;
       while i < n do
       begin
         // Zwiększamy cyfrę
         inc(CT[i]);
         if CT[i] = b-1 then inc(bc);
         if CT[i] < b then break;
         // Zerujemy cyfrę
         CT[i] := 0;
         dec(bc);
         // Modyfikujemy następną cyfrę
         inc(i);
       end;
       // Wychodzimy z pętli
       // zwiększania licznika
       if i < n then break;
       // Licznik się przewinął,
       // zwiększamy bazę
       inc(b);
    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
{
  // Następny element listy
  SLel *next;
  // Wierzchołek docelowy
  int v;
};

int main()
{
  int b,bc,n,m,i,u,v,*CT;
  SLel **graf, *p, *r;
  // Licznik prób
  unsigned long long cnt;
  bool test;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi grafu
  cin >> n >> m;
  // Tablica list sąsiedztwa
  graf = new SLel * [n];
  for(i = 0; i < n; i++)
    graf[i] = nullptr;
  // Tablica kolorów wierzchołków
  CT = new int [n];
  // Odczytujemy krawędzie grafu
  for(i = 0; i < m; i++)
  {
    // Wierzchołki krawędzi
    cin >> u >> v;
    // Tworzymy element listy
    p = new SLel;
    p->v = u;
    // Element dołączamy
    // do listy sąsiadów v
    p->next = graf[v];
    graf[v] = p;
    // To samo dla krawędzi
    // w drugą stronę
    p = new SLel;
    p->v = v;
    // Element dołączamy
    // do listy sąsiadów u
    p->next = graf[u];
    graf[u] = p;
  }
  // Rozpoczynamy algorytm
  // kolorowania grafu
  cnt = 0;
  // Inicjujemy licznik
  for(i = 0; i < n; i++)
    CT[i] = 0;
  // Zliczanie rozpoczynamy
  // przy podstawie 2
  b = 2;
  // Liczba najstarszych cyfr
  bc = 0;
  while(true)
  {
    // Kombinację sprawdzamy,
    // gdy zawiera najstarszą cyfrę
    if(bc)
    {
      test = true;
      // Zwiększamy liczbę prób
      cnt++;
      // Przeglądamy
      // wierzchołki grafu
      for(v = 0; v < n; v++)
      {
        // Przeglądamy sąsiadów
        // wierzchołka v
        for(p = graf[v];p;p = p->next)
          // Testujemy pokolorowanie
          if(CT[v] == CT[p->v])
          {
            // Zaznaczamy porażkę
            test = false;
            // Opuszczamy pętlę for
            break;
          }
        // Opuszczamy pętlę for
        if(!test) break;
      }
      // Kombinacja znaleziona,
      // kończymy pętlę główną
      if(test) break;
    }
    // Pętla modyfikacji licznika
    while(true)
    {
       for(i = 0; i < n; i++)
       {
         // Zwiększamy cyfrę
         CT[i]++;
         if(CT[i] == b-1) bc++;
         if(CT[i] < b) break;
         // Zerujemy cyfrę
         CT[i] = 0;
         bc--;
       }
       // Wychodzimy z pętli
       // zwiększania licznika
       if(i < n) break;
       // Licznik się przewinął,
       // zwiększamy bazę
       b++;
    }
  }
  // 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
  ' Następny element listy
  next As SLel Ptr
  ' Wierzchołek docelowy
  v As Integer
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
' Licznik prób
Dim As ULongInt cnt
Dim As Byte test

Open Cons For Input As #1
' Odczytujemy liczbę
' wierzchołków
' i krawędzi grafu
Input #1, n, m
' Tablica
' list sąsiedztwa
graf = New SLel Ptr [n]
For i = 0 To n-1
  graf[i] = 0
Next
' Tablica kolorów
' wierzchołków
CT = New Integer [n]
' Odczytujemy
' krawędzie grafu
For i = 1 To m
  ' Wierzchołki krawędzi
  Input #1, u, v
  ' Tworzymy
  ' element listy
  p = New SLel
  p->v = u
  ' Element dołączamy
  ' do listy sąsiadów v
  p->next = graf[v]
  graf[v] = p
  ' To samo dla krawędzi
  ' w drugą stronę
  p = New SLel
  p->v = v
  ' Element dołączamy
  ' do listy sąsiadów u
  p->next = graf[u]
  graf[u] = p
Next
Close #1
' Rozpoczynamy algorytm
' kolorowania grafu
cnt = 0
For i = 0 To n-1
  ' Inicjujemy licznik
  CT[i] = 0
Next
' Zliczanie rozpoczynamy
' przy podstawie 2
b = 2
' Liczba najstarszych cyfr
bc = 0
while 1
  ' Kombinację sprawdzamy,
  ' gdy zawiera najstarszą
  ' cyfrę
  If bc > 0 Then
    test = 1
    ' Zwiększamy liczbę prób
    cnt += 1
    ' Przeglądamy
    ' wierzchołki grafu
    For v = 0 To n-1
      p = graf[v]
      ' Przeglądamy sąsiadów
      ' wierzchołka v
      While p
        ' Testujemy pokolorowanie
        If CT[v] = CT[p->v] Then
          ' Zaznaczamy porażkę
          test = 0
          ' Opuszczamy pętlę
          ' while
          Exit While
        End If
        p = p->next
      Wend
      ' Opuszczamy pętlę for
      If test = 0 Then Exit For
    Next
    ' Kombinacja znaleziona,
    ' kończymy pętlę główną
    If test = 1 Then Exit While
  End If
  ' Pętla modyfikacji
  ' licznika
  While 1
    For i = 0 To n-1
      ' Zwiększamy cyfrę
      CT[i] += 1
      If CT[i] = b-1 Then bc += 1
      If CT[i] < b Then Exit For
      ' Zerujemy cyfrę
      CT[i] = 0
      bc -= 1
    Next
    ' Wychodzimy z pętli
    ' zwiększania licznika
    If i < n Then Exit While
    ' Licznik się przewinął,
    ' zwiększamy bazę
    b += 1
  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

Python (dodatek)

# Optymalne kolorowanie
# grafu nieskierowanego
# Data: 12.03.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

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


# Odczytujemy liczbę
# wierzchołków
# i krawędzi grafu
x = input().split()
n = int(x[0])
m = int(x[1])
# Tablica
# list sąsiedztwa
graf = [None] * n
# Tablica kolorów
# wierzchołków
ct = [0] * n
test = False
# Odczytujemy
# krawędzie grafu
for i in range(m):
    # Wierzchołki krawędzi
    x = input().split()
    u = int(x[0])
    v = int(x[1])
    # Tworzymy
    # element listy
    p = SLel()
    p.v = u
    # Element dołączamy
    # do listy sąsiadów v
    p.next = graf[v]
    graf[v] = p
    # To samo dla krawędzi
    # w drugą stronę
    p = SLel()
    p.v = v
    # Element dołączamy
    # do listy sąsiadów u
    p.next = graf[u]
    graf[u] = p
# Rozpoczynamy algorytm
# kolorowania grafu
cnt = 0
# Zliczanie rozpoczynamy
# przy podstawie 2
b = 2
# Liczba najstarszych cyfr
bc = 0
while True:
    # Kombinację sprawdzamy,
    # gdy zawiera najstarszą
    # cyfrę
    if bc:
        test = True
        # Zwiększamy liczbę prób
        cnt += 1
        # Przeglądamy
        # wierzchołki grafu
        for v in range(n):
            p = graf[v]
            # Przeglądamy sąsiadów
            # wierzchołka v
            while p:
                # Testujemy
                # pokolorowanie
                if ct[v] == ct[p.v]:
                    # Zaznaczamy
                    # porażkę
                    test = False
                    # Opuszczamy
                    # pętlę while
                    break
                p = p.next
            # Opuszczamy pętlę for
            if not test: break
        # Kombinacja znaleziona,
        # kończymy pętlę główną
        if test: break
    # Pętla modyfikacji
    # licznika
    while True:
        i = 0
        while i < n:
            # Zwiększamy cyfrę
            ct[i] += 1
            if ct[i] == b-1: bc += 1
            if ct[i] < b: break
            # Zerujemy cyfrę
            ct[i] = 0
            bc -= 1
            i += 1
        # Wychodzimy z pętli
        # zwiększania licznika
        if i < n: break
        # Licznik się przewinął,
        # zwiększamy bazę
        b += 1
# Wyświetlamy wyniki
print()
for v in range(n):
    print("vertex",v,
          "has color",ct[v])
print()
print("graph chromatic number =",b)
print("number of tries        =",cnt)
print()
# Usuwamy tablice dynamiczne
for v in range(n):
    while graf[v]:
        graf[v] = graf[v].next
del graf, ct

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

do podrozdziału do 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:

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 ∈ 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: ; przechodzimy przez pozostałe wierzchołki grafu
     wykonuj kroki K04…K08
K04:   Wypełnij tablicę C wartościami false ; oznaczamy wszystkie kolory jako niezajęte
K05:   Dla każdego sąsiada u wierzchołka v: ; przeglądamy sąsiadów wierzchołka v.
       wykonuj:
         Jeśli CT[u] >-1, ; Kolor sąsiada oznaczamy jako zajęty 
         to C[CT[u]] ← true
K06:   i = 0
K07:   Dopóki C[i] = true, ; szukamy najniższego z dostępnych kolorów
       wykonuj: i ← i + 1
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
    // Następny element listy
    next : PSLel;
    // Wierzchołek docelowy
    v : integer;
  end;

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

begin
  // Odczytujemy liczbę
  // wierzchołków
  // i krawędzi grafu
  read(n, m);
  // Tablica list sąsiedztwa
  SetLength(graf, n);
  for i := 0 to n-1 do
    graf[i] := nil;
  // Tablica
  // kolorów wierzchołków
  SetLength(CT, n);
  // Tablica
  // dostępności kolorów
  SetLength(C, n);
  // Odczytujemy
  // krawędzie grafu
  for i := 1 to m do
  begin
    // Wierzchołki krawędzi
    read(u, v);
    // Tworzymy
    // element listy
    new(p);
    p^.v := u;
    // Element dołączamy
    // do listy sąsiadów v
    p^.next := graf[v];
    graf[v] := p;
    // To samo dla krawędzi
    // w drugą stronę
    new(p);
    p^.v := v;
    // Element dołączamy
    // do listy sąsiadów u
    p^.next := graf[u];
    graf[u] := p;
  end;
  // Rozpoczynamy algorytm
  // kolorowania grafu
  for i := 1 to n-1 do
    CT[i] := -1;
  // Kolor pierwszego
  // wierzchołka
  CT[0] := 0;
  for v := 1 to n-1 do
  begin
    for i := 0 to n-1 do
      C[i] := false;
    // Przeglądamy
    // listę sąsiadów v
    p := graf[v];
    while p <> nil do
    begin
      // Kolor u zaznaczamy
      // jako zajęty
      if CT[p^.v] >-1 then
        C[CT[p^.v]] := true;
      // Następny sąsiad
      p := p^.next;
    end;
    i := 0;
    // Szukamy wolnego koloru
    while C[i] do inc(i);
    // Kolorujemy wierzchołek v
    CT[v] := i;
  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
{
  // Następny element listy;
  SLel * next;
  // Wierzchołek docelowy
  int v;
};

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

  // Odczytujemy liczbę
  // wierzchołków
  // i krawędzi grafu
  cin >> n >> m;
  // Tablica
  // list sąsiedztwa
  graf = new SLel * [n];
  for(i = 0; i < n; i++)
    graf[i] = nullptr;
  // Tablica
  // kolorów wierzchołków
  CT = new int [n];
  // Tablica
  // dostępności kolorów
  C  = new bool [n];
  // Odczytujemy
  // krawędzie grafu
  for(i = 0; i < m; i++)
  {
    // Wierzchołki krawędzi
    cin >> u >> v;
    // Tworzymy element listy
    p = new SLel;
    p->v = u;
    // Element dołączamy
    // do listy sąsiadów v
    p->next = graf[v];
    graf[v] = p;
    // To samo dla krawędzi
    // w drugą stronę
    p = new SLel;
    p->v = v;
    // Element dołączamy
    // do listy sąsiadów u
    p->next = graf[u];
    graf[u] = p;
  }
  // Rozpoczynamy algorytm
  // kolorowania grafu
  for(i = 1; i < n; i++)
    CT[i] = -1;
  // Kolor
  // pierwszego wierzchołka
  CT[0] = 0;
  for(v = 1; v < n; v++)
  {
    for(i = 0; i < n; i++)
      C[i] = false;
    // Przeglądamy
    // listę sąsiadów v
    for(p = graf[v]; p; p = p->next)
      if(CT[p->v] >-1)
        // Kolor u
        // zaznaczamy jako zajęty
        C[CT [p->v]] = true;
    // Szukamy wolnego koloru
    for(i = 0; C[i]; i++);
    // Kolorujemy wierzchołek v
    CT[v] = i;
  }
  // 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
  ' Następny
  ' element listy
  next As SLel Ptr
  ' Wierzchołek docelowy
  v As Integer
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
' Odczytujemy liczbę
' wierzchołków
' i krawędzi grafu
Input #1, n, m
' Tablica
' list sąsiedztwa
graf = New SLel Ptr [n]
For i = 0 To n-1
  graf[i] = 0
Next
' Tablica
' kolorów wierzchołków
CT = New Integer [n]
' Tablica
' dostępności kolorów
C  = New Byte [n]
' Odczytujemy krawędzie grafu
For i = 1 To m
  ' Wierzchołki krawędzi
  Input #1, u, v
  ' Tworzymy element listy
  p = New SLel
  p->v = u
  ' Element dołączamy
  ' do listy sąsiadów v
  p->next = graf[v]
  graf[v] = p
  ' To samo dla krawędzi
  ' w drugą stronę
  p = New SLel
  p->v = v
  ' Element dołączamy
  ' do listy sąsiadów u
  p->next = graf[u]
  graf[u] = p
Next
Close #1
' Rozpoczynamy algorytm
' kolorowania grafu
For i = 1 To n-1
  CT[i] = -1
Next
' Kolor
' pierwszego wierzchołka
CT[0] = 0
For v = 1 To n-1
  For i = 0 To n-1
    C[i] = 0
  Next
  p = graf[v]
  ' Przeglądamy
  ' listę sąsiadów v
  While p
    ' Kolor u zaznaczamy
    ' jako zajęty
    If CT[p->v] >-1 Then _
      C[CT[p->v]] = 1
    ' Następny sąsiad
    p = p->Next
  Wend
  i = 0
  ' Szukamy
  ' wolnego koloru
  While C[i] = 1
    i += 1
  Wend
  ' Kolorujemy
  ' wierzchołek v
  CT[v] = i
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

Python (dodatek)

# Zachłanne kolorowanie
# grafu nieskierowanego
# Data: 13.03.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

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


# Odczytujemy liczbę
# wierzchołków
# i krawędzi grafu
x = input().split()
n = int(x[0])
m = int(x[1])
# Tablica
# list sąsiedztwa
graf = [None] * n
# Tablica
# kolorów wierzchołków
ct = [-1] * n
# Tablica
# dostępności kolorów
c = [False] * n
# Odczytujemy
# krawędzie grafu
for i in range(m):
    # Wierzchołki krawędzi
    x = input().split()
    u = int(x[0])
    v = int(x[1])
    # Tworzymy element listy
    p = SLel()
    p.v = u
    # Element dołączamy
    # do listy sąsiadów v
    p.next = graf[v]
    graf[v] = p
    # To samo dla krawędzi
    # w drugą stronę
    p = SLel()
    p.v = v
    # Element dołączamy
    # do listy sąsiadów u
    p.next = graf[u]
    graf[u] = p
# Rozpoczynamy algorytm
# kolorowania grafu
#----------------------
# Kolor
# pierwszego wierzchołka
ct[0] = 0
for v in range(1,n):
    for i in range(n):
        c[i] = False
    p = graf[v]
    # Przeglądamy
    # listę sąsiadów v
    while p:
        # Kolor u zaznaczamy
        # jako zajęty
        if ct[p.v] >-1:
            c[ct[p.v]] = True
        # Następny sąsiad
        p = p.next
    i = 0
    # Szukamy
    # wolnego koloru
    while c[i]:
        i += 1
    # Kolorujemy
    # wierzchołek v
    ct[v] = i
# Wyświetlamy wyniki
print()
for v in range(n):
    print("verte",v,
          "has color",ct[v])
# Usuwamy tablice dynamiczne
for v in range(n):
    while graf[v]:
        graf[v] = graf[v].next
del graf, ct, c

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

do podrozdziału do 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:

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 ∈ 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: ; przeglądamy kolejne wierzchołki grafu
     wykonuj kroki K02…K13
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), ; szukamy pozycji wierzchołka
       wykonuj kroki K08…K10 ; 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: ; przechodzimy przez pozostałe wierzchołki grafu
     wykonuj kroki K16…K20
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]: ; przeglądamy sąsiadów wierzchołka VT[v].
       wykonuj:
         Jeśli CT[u] >-1, ; Kolor sąsiada oznaczamy jako zajęty 
         to C[CT[u]] ← true
K18:   i = 0
K19:   Dopóki C[i] = true, ; szukamy najniższego z dostępnych kolorów
       wykonuj i ← i+1
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
    // Następny element listy
    next : PSLel;
    // Wierzchołek docelowy
    v : integer;
  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
  // Odczytujemy liczbę
  // wierzchołków
  // i krawędzi grafu
  read(n, m);
  // Tablica list sąsiedztwa
  SetLength(graf, n);
  for i := 0 to n-1 do
    graf[i] := nil;
  // Tablica
  // kolorów wierzchołków
  SetLength(CT, n);
  // Tablica
  // stopni wyjściowych
  // wierzchołków
  SetLength(DT, n);
  // Tablica
  // numerów wierzchołków
  SetLength(VT, n);
  // Tablica
  // dostępności kolorów
  SetLength(C, n);
  // Odczytujemy
  // krawędzie grafu
  for i := 1 to m do
  begin
    // Wierzchołki krawędzi
    read(u, v);
    // Tworzymy
    // element listy
    new(p);
    p^.v := u;
    // Element dołączamy
    // do listy sąsiadów v
    p^.next := graf[v];
    graf[v] := p;
    // To samo dla krawędzi
    // w drugą stronę
    new(p);
    p^.v := v;
    // Element dołączamy
    // do listy sąsiadów u
    p^.next := graf[u];
    graf[u] := p;
  end;
  // Rozpoczynamy algorytm
  // kolorowania grafu
  //----------------------
  // Przeglądamy kolejne
  // wierzchołki grafu
  for v := 0 to n-1 do
  begin
    // Zapamiętujemy
    // numer wierzchołka
    VT[v] := v;
    // Zerujemy jego
    // stopień wyjściowy
    DT[v] := 0;
    // Przeglądamy
    // kolejnych sąsiadów
    p := graf[v];
    while p <> nil do
    begin
      // Obliczamy stopień
      // wyjściowy
      // wierzchołka v
      inc(DT[v]);
      // Następny sąsiad
      p := p^.next;
    end;
    // Sortujemy DT i VT
    //------------------
    // Zapamiętujemy wyliczony
    // stopień wyjściowy
    d := DT[v];
    // Pozycja
    // wstawiania elementu
    i := v;
    // Szukamy miejsca
    // na wstawienie
    while (i > 0) and
          (DT[i-1] < d) do
    begin
      // Przesuwamy
      // elementy obu tablic
      DT[i] := DT[i-1];
      VT[i] := VT[i-1];
      // Nowa pozycja wstawiania
      dec(i);
    end;
    // Wstawiamy element
    DT[i] := d;
    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;
  // Wierzchołek startowy
  CT[VT[0]] := 0;
  // Przeglądamy resztę grafu
  for v := 1 to n-1 do
  begin
    for i := 0 to n-1 do
      C[i] := false;
    // Przeglądamy sąsiadów
    // bieżącego wierzchołka
    p := graf[VT[v]];
    while p <> nil do
    begin
      // Oznaczamy kolor
      // jako zajęty
      if CT[p^.v] > -1 then
        C[CT[p^.v]] := true;
      // Następny sąsiad
      p := p^.next;
    end;
    i := 0;
    // Szukamy wolnego koloru
    while C[i] do inc(i);
    // Przypisujemy go
    // bieżącemu wierzchołkowi
    CT[VT[v]] := i;
  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
{
  // Następny
  // element listy;
  SLel * next;
  // Wierzchołek docelowy
  int v;
};

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

  // Odczytujemy liczbę
  // wierzchołków
  // i krawędzi grafu
  cin >> n >> m;
  // Tablica
  // list sąsiedztwa
  graf = new SLel * [n];
  for(i = 0; i < n; i++)
    graf[i] = nullptr;
  // Tablica
  // kolorów wierzchołków
  CT = new int [n];
  // Tablica stopni
  // wyjściowych
  // wierzchołków
  DT = new int [n];
  // Tablica
  // numerów wierzchołków
  VT = new int [n];
  // Tablica
  // dostępności kolorów
  C  = new bool [n];
  // Odczytujemy
  // krawędzie grafu
  for(i = 0; i < m; i++)
  {
    // Wierzchołki krawędzi
    cin >> u >> v;
    // Tworzymy
    // element listy
    p = new SLel;
    p->v = u;
    // Element dołączamy
    // do listy sąsiadów v
    p->next = graf[v];
    graf[v] = p;
    // To samo dla krawędzi
    // w drugą stronę
    p = new SLel;
    p->v = v;
    // Element dołączamy
    // do listy sąsiadów u
    p->next = graf[u];
    graf[u] = p;
  }
  // Rozpoczynamy algorytm
  // kolorowania grafu
  //----------------------

  // Przeglądamy kolejne
  // wierzchołki grafu
  for(v = 0; v < n; v++)
  {
    // Zapamiętujemy
    // numer wierzchołka
    VT[v] = v;
    // Zerujemy jego
    // stopień wyjściowy
    DT[v] = 0;
    // Przeglądamy
    // kolejnych sąsiadów
    for(p = graf[v]; p; p = p->next)
      // Obliczamy stopień
      // wyjściowy wierzchołka v
      DT[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;
  // Przeglądamy
  // resztę grafu
  for(v = 1; v < n; v++)
  {
    for(i = 0; i < n; i++)
      C[i] = false;
    // Przeglądamy sąsiadów
    // bieżącego wierzchołka
    for(p = graf[VT[v]];
        p; p = p->next)
      // Oznaczamy
      // kolor jako zajęty
      if(CT[p->v] > -1)
        C[CT[p->v]] = true;
    // Szukamy wolnego koloru
    for(i = 0; C[i]; i++);
    // Przypisujemy go
    // bieżącemu wierzchołkowi
    CT[VT[v]] = i;
  }
  // 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
  ' Następny element listy
  next As SLel Ptr
  ' Wierzchołek docelowy
  v As Integer
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
' Odczytujemy liczbę
' wierzchołków
' i krawędzi grafu
Input #1, n, m
' Tablica
' list sąsiedztwa
graf = New SLel Ptr [n]
For i = 0 To n-1
  graf [i] = 0
Next
' Tablica
' kolorów wierzchołków
CT = New Integer [n]
' Tablica stopni
' wyjściowych wierzchołków
DT = New Integer [n]
' Tablica
' numerów wierzchołków
VT = New Integer [n]
' Tablica
' dostępności kolorów
C  = New Byte [n]
' Odczytujemy
' krawędzie grafu
For i = 1 To m
  ' Wierzchołki krawędzi
  Input #1, u, v
  ' Tworzymy
  ' element listy
  p = New SLel
  p->v = u
  ' Element dołączamy
  ' do listy sąsiadów v
  p->next = graf[v]
  graf[v] = p
  ' To samo dla krawędzi
  ' w drugą stronę
  p = New SLel
  p->v = v
  ' Element dołączamy
  ' do listy sąsiadów u
  p->next = graf[u]
  graf[u] = p
Next
Close #1
' Rozpoczynamy algorytm
' kolorowania grafu
'----------------------
' Przeglądamy kolejne
' wierzchołki grafu
For v = 0 To n-1
  ' Zapamiętujemy
  ' numer wierzchołka
  VT[v] = v
  ' Zerujemy jego
  ' stopień wyjściowy
  DT[v] = 0
  p = graf[v]
  ' Przeglądamy
  ' kolejnych sąsiadów
  While p <> 0
    ' Obliczamy stopień
    ' wyjściowy wierzchołka v
    DT[v] += 1
    ' Następny sąsiad
    p = p->next
  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
' Wierzchołek startowy
CT[VT[0]] = 0
' Przeglądamy resztę grafu
For v = 1 To n-1
  For i = 0 To n-1
    C[i] = 0
  Next
  p = graf[VT[v]]
  ' Przeglądamy sąsiadów
  ' bieżącego wierzchołka
  While p <> 0
    ' Oznaczamy kolor
    ' jako zajęty
    If CT[p->v] > -1 Then _
      C[CT[p->v]] = 1
    ' Następny sąsiad
    p = p->next
  Wend
  i = 0
  ' Szukamy wolnego koloru
  While C[i] = 1
    i += 1
  Wend
  ' Przypisujemy go
  ' bieżącemu wierzchołkowi
  CT[VT[v]] = i
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

Python (dodatek)

# Algorytm LF kolorowania
# grafu nieskierowanego
# Data: 14.03.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

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


# Odczytujemy liczbę
# wierzchołków
# i krawędzi grafu
x = input().split()
n = int(x[0])
m = int(x[1])
# Tablica
# list sąsiedztwa
graf = [None] * n
# Tablica
# kolorów wierzchołków
ct = [-1] * n
# Tablica stopni
# wyjściowych wierzchołków
dt = [0] * n
# Tablica
# numerów wierzchołków
vt = [0] * n
# Tablica
# dostępności kolorów
c = [False] * n
# Odczytujemy
# krawędzie grafu
for i in range(m):
    # Wierzchołki krawędzi
    x = input().split()
    u = int(x[0])
    v = int(x[1])
    # Tworzymy
    # element listy
    p = SLel()
    p.v = u
    # Element dołączamy
    # do listy sąsiadów v
    p.next = graf[v]
    graf[v] = p
    # To samo dla krawędzi
    # w drugą stronę
    p = SLel()
    p.v = v
    # Element dołączamy
    # do listy sąsiadów u
    p.next = graf[u]
    graf[u] = p
# Rozpoczynamy algorytm
# kolorowania grafu
#----------------------
# Przeglądamy kolejne
# wierzchołki grafu
for v in range(n):
    # Zapamiętujemy
    # numer wierzchołka
    vt[v] = v
    # Zerujemy jego
    # stopień wyjściowy
    dt[v] = 0
    p = graf[v]
    # Przeglądamy
    # kolejnych sąsiadów
    while p:
        # Obliczamy stopień
        # wyjściowy wierzchołka v
        dt[v] += 1
        # Następny sąsiad
        p = p.next
    # Sortujemy DT i VT
    d = dt[v]
    i = v
    while (i > 0) and \
          (dt[i-1] < d):
        dt[i] = dt[i-1]
        vt[i] = vt[i-1]
        i -= 1
    dt[i] = d
    vt[i] = v
# Teraz stosujemy
# algorytm zachłanny,
# lecz wierzchołki
# wybieramy wg VT
# Wierzchołek startowy
ct[vt[0]] = 0
# Przeglądamy resztę grafu
for v in range(1,n):
    for i in range(n):
        c[i] = False
    p = graf[vt[v]]
    # Przeglądamy sąsiadów
    # bieżącego wierzchołka
    while p:
        # Oznaczamy kolor
        # jako zajęty
        if ct[p.v] > -1:
            c[ct[p.v]] = True
        # Następny sąsiad
        p = p.next
    i = 0
    # Szukamy wolnego koloru
    while c[i]:
        i += 1
    # Przypisujemy go
    # bieżącemu wierzchołkowi
    ct[vt[v]] = i
# Wyświetlamy wyniki
print()
for v in range(n):
    print("vertex",v,
          "has color",ct[v])
print()
# Usuwamy tablice dynamiczne
for v in range(n):
    while graf[v]:
        graf[v] = graf[v].next
del graf, ct, dt, vt, c

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

do podrozdziału do 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
    // Następny element listy
    next : PSLel;
    // Wierzchołek docelowy
    v : integer;
    // Numer krawędzi
    i : integer;
  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
  // Odczytujemy liczbę
  // wierzchołków
  // i krawędzi grafu
  read(n, m);
  // Tworzymy zerowy graf G
  SetLength(G, n);
  for i := 0 to n-1 do
    G[i] := nil;
  // Tworzymy zerowy graf GE
  SetLength(GE, m);
  for i := 0 to m-1 do
    GE[i] := nil;
  // Tablica
  // kolorów wierzchołków
  SetLength(CT, m);
  // Tablica stopni
  // wyjściowych wierzchołków
  SetLength(DT, m);
  // Tablica
  // numerów wierzchołków
  SetLength(VT, m);
  // Tablica
  // dostępności kolorów
  SetLength(C, m);
  // Odczytujemy definicje
  // krawędzi grafu G
  for i := 0 to m-1 do
  begin
    // Czytamy wierzchołki
    read(v, u);
    // Tworzymy rekord listy
    new(p);
    // Wypełniamy go danymi
    p^.v := u;
    p^.i := i;
    // Rekord dołączamy
    // do listy sąsiedztwa
    // wierzchołka v
    p^.next := G[v];
    G[v] := p;
    // To samo dla
    // krawędzi odwrotnej
    new(p);
    p^.v := v;
    p^.i := i;
    p^.next := G[u];
    G[u] := p;
  end;
  // Tworzymy
  // graf krawędziowy
  //-----------------
  // Przechodzimy przez
  // kolejne wierzchołki grafu
  for v := 0 to n-1 do
  begin
    // Przechodzimy przez listę
    // sąsiadów wierzchołka v
    p := G[v];
    while p <> nil do
    begin
      // Przechodzimy przez listę
      // sąsiadów sąsiada v
      r := G[p^.v];
      while r <> nil do
      begin
        if r^.v <> v then
        begin
          // Tworzymy
          // nowy element listy
          new(s);
          // Wierzchołkiem docelowym
          // będzie krawędź wychodząca
          s^.v := r^.i;
          // Wierzchołkiem startowym
          // będzie krawędź wchodząca
          s^.next := GE[p^.i];
          // Dodajemy krawędź
          // do grafu krawędziowego
          GE[p^.i] := s;
        end;
        // Następny sąsiad
        r := r^.next;
      end;
      // Następny sąsiad
      p := p^.next;
    end;
  end;
  // Rozpoczynamy algorytm
  // kolorowania grafu krawędziowego
  //--------------------------------
  // Przeglądamy kolejne
  // wierzchołki grafu
  for v := 0 to m-1 do
  begin
    // Zapamiętujemy
    // numer wierzchołka
    VT[v] := v;
    // Zerujemy jego
    // stopień wyjściowy
    DT[v] := 0;
    // Przeglądamy
    // kolejnych sąsiadów
    p := GE[v];
    while p <> nil do
    begin
      // Obliczamy stopień
      // wyjściowy wierzchołka v
      inc(DT[v]);
      // Następny sąsiad
      p := p^.next;
    end;
    // Sortujemy DT i VT
    //------------------
    // Zapamiętujemy wyliczony
    // stopień wyjściowy
    d := DT[v];
    // Pozycja
    // wstawiania elementu
    i := v;
    // Szukamy miejsca
    // na wstawienie
    while (i > 0) and
          (DT [i-1] < d) do
    begin
      // Przesuwamy elementy
      // obu tablic
      DT[i] := DT[i-1];
      VT[i] := VT[i-1];
      // Nowa pozycja wstawiania
      dec(i);
    end;
    // Wstawiamy element
    DT[i] := d;
    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;
  // Wierzchołek startowy
  CT[VT[0]] := 0;
  // Przeglądamy resztę grafu
  for v := 1 to m-1 do
  begin
    for i := 0 to m-1 do
      C[i] := false;
    // Przeglądamy sąsiadów
    // bieżącego wierzchołka
    p := GE[VT[v]];
    while p <> nil do
    begin
      // Oznaczamy kolor
      // jako zajęty
      if CT[p^.v] > -1 then
        C[CT[p^.v]] := true;
      // Następny sąsiad
      p := p^.next;
    end;
    i := 0;
    // Szukamy wolnego koloru
    while C[i] do inc(i);
    // Przypisujemy go
    // bieżącemu wierzchołkowi
    CT[VT[v]] := i;
  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
{
  // Następny element listy;
  SLel * next;
  // Wierzchołek docelowy
  int v;
  // Numer krawędzi
  int i;
};

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

  // Odczytujemy liczbę
  // wierzchołków
  // i krawędzi grafu
  cin >> n >> m;
  // Tworzymy zerowy graf G
  G = new SLel * [n];
  for(i = 0; i < n; i++)
    G[i] = nullptr;
  // Tworzymy zerowy graf GE
  GE = new SLel * [m];
  for(i = 0; i < m; i++)
    GE[i] = nullptr;
  // Tablica
  // kolorów wierzchołków
  CT = new int [m];
  // Tablica stopni
  // wyjściowych wierzchołków
  DT = new int [m];
  // Tablica
  // numerów wierzchołków
  VT = new int [m];
  // Tablica
  // dostępności kolorów
  C = new bool [m];
  // Odczytujemy definicje
  // krawędzi grafu G
  for(i = 0; i < m; i++)
  {
    // Czytamy wierzchołki
    cin >> v >> u;
    // Tworzymy rekord listy
    p = new SLel;
    // Wypełniamy go danymi
    p->v = u;
    p->i = i;
    // Element dołączamy
    // do listy sąsiedztwa
    // wierzchołka v
    p->next = G[v];
    G[v] = p;
    // To samo
    // dla krawędzi odwrotnej
    p = new SLel;
    p->v = v;
    p->i = i;
    p->next = G[u];
    G[u] = p;
  }
  // Tworzymy graf krawędziowy
  //--------------------------
  // Przechodzimy przez
  // kolejne wierzchołki grafu
  for(v = 0; v < n; v++)
    // Przechodzimy przez
    // listę sąsiadów
    // wierzchołka v
    for(p = G [v]; p; p = p->next)
      // Przechodzimy przez
      // listę sąsiadów sąsiada v
      for(r = G[p->v]; r; r = r->next)
        if(r->v != v)
        {
          // Tworzymy nowy element listy
          s = new SLel;
          // Wierzchołkiem docelowym
          // będzie krawędź wychodząca
          s->v = r->i;
          // Wierzchołkiem startowym
          // będzie krawędź wchodząca
          s->next = GE[p->i];
          // Dodajemy krawędź
          // do grafu krawędziowego
          GE[p->i] = s;
        }
  // Rozpoczynamy algorytm
  // kolorowania grafu krawędziowego
  //--------------------------------
  // Przeglądamy kolejne
  // wierzchołki grafu
  for(v = 0; v < m; v++)
  {
    // Zapamiętujemy
    // numer wierzchołka
    VT[v] = v;
    // Zerujemy
    // jego stopień wyjściowy
    DT[v] = 0;
    // Przeglądamy kolejnych sąsiadów
    for(p = GE[v]; p; p = p->next)
      // Obliczamy stopień
      // wyjściowy wierzchołka v
      DT[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;
  // Wierzchołek startowy
  CT[VT[0]] = 0;
  // Przeglądamy resztę grafu
  for(v = 1; v < m; v++)
  {
    for(i = 0; i < m; i++)
      C[i] = false;
    // Przeglądamy sąsiadów
    // bieżącego wierzchołka
    for(p = GE[VT[v]]; p; p = p->next)
      // Oznaczamy kolor jako zajęty
      if(CT[p->v] > -1)
        C[CT[p->v]] = true;
    // Szukamy wolnego koloru
    for(i = 0; C[i]; i++);
    // Przypisujemy go
    // bieżącemu wierzchołkowi
    CT[VT[v]] = i;
  }
  // 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
  ' Następny element listy
  Dim Next As SLel Ptr
  ' Wierzchołek docelowy
  Dim v As Integer
  ' Numer krawędzi
  Dim i As Integer
End Type

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
' Czytamy
' rozmiary grafu
Input #1, n, m
' Tworzymy
' zerowy graf G
G = New SLel Ptr [n]
For i = 0 To n-1
  G[i] = 0
Next
' Tworzymy
' zerowy graf GE
GE = New SLel Ptr [m]
For i = 0 To m-1
  GE[i] = 0
Next
' Tablica
' kolorów wierzchołków
CT = New Integer [m]
' Tablica stopni
' wyjściowych wierzchołków
DT = New Integer [m]
' Tablica
' numerów wierzchołków
VT = New Integer [m]
' Tablica
' dostępności kolorów
C  = New Byte [m]
' Odczytujemy definicje
' krawędzi grafu G
For i = 0 To m-1
  ' Czytamy wierzchołki
  Input #1, v, u
  ' Tworzymy
  ' element listy
  p = New SLel
  ' Wypełniamy go danymi
  p->v = u
  p->i = i
  ' Element dołączamy
  ' do listy sąsiedztwa
  ' wierzchołka v
  p->next = G[v]
  G[v] = p
  ' To samo dla
  ' krawędzi odwrotnej
  p = New SLel
  p->v = v
  p->i = i
  p->next = G[u]
  G[u] = p
Next
Close #1
' Tworzymy
' graf krawędziowy
' Przechodzimy przez
' kolejne wierzchołki grafu
For v = 0 To n-1
  ' Przechodzimy przez
  ' listę sąsiadów
  ' wierzchołka v
  p = G[v]
  While p
    ' Przechodzimy przez
    ' listę sąsiadów sąsiada v
    r = G[p->v]
    While r
      If r->v <> v Then
        ' Tworzymy nowy
        ' element listy
        s = New SLel
        ' Wierzchołkiem docelowym
        ' będzie krawędź wychodząca
        s->v = r->i
        ' Wierzchołkiem startowym
        ' będzie krawędź wchodząca
        s->next = GE[p->i]
        ' Dodajemy krawędź
        ' do grafu krawędziowego
        GE[p->i] = s
      End If
      ' Następny sąsiad
      r = r->next
    Wend
    ' Następny sąsiad
    p = p->next
  Wend
Next
' Rozpoczynamy algorytm
' kolorowania
' grafu krawędziowego
'----------------------
' Przeglądamy kolejne
' wierzchołki grafu
For v = 0 To m-1
  ' Zapamiętujemy
  ' numer wierzchołka
  VT[v] = v
  ' Zerujemy jego
  ' stopień wyjściowy
  DT[v] = 0
  p = GE[v]
  ' Przeglądamy
  ' kolejnych sąsiadów
  While p <> 0
    ' Obliczamy stopień
    ' wyjściowy wierzchołka v
    DT[v] += 1
    ' Następny sąsiad
    p = p->next
  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
' Wierzchołek startowy
CT[VT[0]] = 0
' Przeglądamy resztę grafu
For v = 1 To m-1
  For i = 0 To m-1
    C[i] = 0
  Next
  p = GE[VT[v]]
  ' Przeglądamy sąsiadów
  ' bieżącego wierzchołka
  While p <> 0
    ' Oznaczamy kolor
    ' jako zajęty
    If CT[p->v] > -1 Then _
      C[CT[p->v]] = 1
    ' Następny sąsiad
    p = p->next
  Wend
  i = 0
  ' Szukamy wolnego koloru
  While C[i] = 1
    i += 1
  Wend
  ' Przypisujemy go
  ' bieżącemu wierzchołkowi
  CT[VT[v]] = i
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 <> 0
    r = p
    p = p->next
    Delete r
  Wend
Next
For v = 0 To m-1
  p = GE[v]
  While p <> 0
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] G
Delete [] GE
Delete [] CT
Delete [] DT
Delete [] VT
Delete [] C
End

Python (dodatek)

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

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


# Czytamy
# rozmiary grafu
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy
# zerowy graf G
g = [None] * n
# Tworzymy
# zerowy graf GE
ge = [None] * m
# Tablica
# kolorów wierzchołków
ct = [-1] * m
# Tablica stopni
# wyjściowych wierzchołków
dt = [0] * m
# Tablica
# numerów wierzchołków
vt = [0] * m
# Tablica
# dostępności kolorów
c = [False] * m
# Odczytujemy definicje
# krawędzi grafu G
for i in range(m):
    # Czytamy wierzchołki
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy
    # element listy
    p = SLel()
    # Wypełniamy go danymi
    p.v = u
    p.i = i
    # Element dołączamy
    # do listy sąsiedztwa
    # wierzchołka v
    p.next = g[v]
    g[v] = p
    # To samo dla
    # krawędzi odwrotnej
    p = SLel()
    p.v = v
    p.i = i
    p.next = g[u]
    g[u] = p
# Tworzymy
# graf krawędziowy
# Przechodzimy przez
# kolejne wierzchołki grafu
for v in range(n):
    # Przechodzimy przez
    # listę sąsiadów
    # wierzchołka v
    p = g[v]
    while p:
        # Przechodzimy przez
        # listę sąsiadów sąsiada v
        r = g[p.v]
        while r:
            if r.v != v:
                # Tworzymy nowy
                # element listy
                s = SLel()
                # Wierzchołkiem
                # docelowym będzie
                # krawędź wychodząca
                s.v = r.i
                # Wierzchołkiem
                # startowym będzie
                # krawędź wchodząca
                s.next = ge[p.i]
                # Dodajemy krawędź do
                # grafu krawędziowego
                ge[p.i] = s
            # Następny sąsiad
            r = r.next
        # Następny sąsiad
        p = p.next
# Rozpoczynamy algorytm
# kolorowania
# grafu krawędziowego
#----------------------
# Przeglądamy kolejne
# wierzchołki grafu
for v in range(m):
    # Zapamiętujemy
    # numer wierzchołka
    vt[v] = v
    # Zerujemy jego
    # stopień wyjściowy
    dt[v] = 0
    p = ge[v]
    # Przeglądamy
    # kolejnych sąsiadów
    while p:
        # Obliczamy stopień
        # wyjściowy wierzchołka v
        dt[v] += 1
        # Następny sąsiad
        p = p.next
    # Sortujemy DT i VT
    d = dt[v]
    i = v
    while i and (dt[i-1] < d):
        dt[i] = dt[i-1]
        vt[i] = vt[i-1]
        i -= 1
    dt[i] = d
    vt[i] = v
# Teraz stosujemy
# algorytm zachłanny,
# lecz wierzchołki
# wybieramy wg VT
for i in range(m):
    ct[i] = -1
# Wierzchołek startowy
ct[vt[0]] = 0
# Przeglądamy resztę grafu
for v in range(1,m):
    for i in range(m):
        c[i] = False
    p = ge[vt[v]]
    # Przeglądamy sąsiadów
    # bieżącego wierzchołka
    while p:
        # Oznaczamy kolor
        # jako zajęty
        if ct[p.v] > -1:
            c[ct[p.v]] = True
        # Następny sąsiad
        p = p.next
    i = 0
    # Szukamy wolnego koloru
    while c[i]:
        i += 1
    # Przypisujemy go
    # bieżącemu wierzchołkowi
    ct[vt[v]] = i
# Wyświetlamy wyniki
print()
for i in range(m):
    c[i] = True
for v in range(n):
    p = g[v]
    while p:
        if c[p.i]:
            c[p.i] = False
            print("edge ",v,"-",p.v,
                  " has color ",
                  ct[p.i],sep="")
        p = p.next
print()
# Usuwamy
# tablice dynamiczne
for v in range(n):
    while g[v]:
        g[v] = g[v].next
for v in range(m):
    while ge[v]:
        ge[v] = ge[v].next
del g, ge, ct, dt, vt, c

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

do podrozdziału do 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