Kolorowanie krawędzi

Kolorowanie krawędzi grafu – rozszerzenie klasycznego kolorowania grafu na krawędzie. Jest to przyporządkowywanie krawędziom grafu liczb naturalnych symbolizujących kolory.

Odwzorowanie ${\displaystyle c\colon E(G)\to S}$ nazywamy kolorowaniem krawędzi grafu ${\displaystyle G,}$ natomiast zbiór ${\displaystyle S}$ zbiorem kolorów.

Niech ${\displaystyle S(v)}$ oznacza zbiór kolorów krawędzi incydentnych z wierzchołkiem ${\displaystyle v.}$

Prawidłowe pokolorowanie krawędzi (legalne, właściwe) to takie przyporządkowanie krawędziom kolorów, gdzie żadne dwie sąsiednie krawędzie nie są pokolorowane tak samo. (Krawędzie są sąsiednie jeśli mają wspólny jeden z końców). Czyli kolorowanie krawędzi nazywamy właściwym, jeżeli ${\displaystyle c(e)\neq c(f)}$ dla każdych dwóch sąsiednich krawędzi, w przeciwnym przypadku kolorowanie nazywamy niewłaściwym^[1].

k-kolorowaniem nazywamy kolorowanie ${\displaystyle c\colon E(G)\to \{1,\dots ,k\},}$ czyli kolorujemy przy użyciu ${\displaystyle k}$ kolorów.

Optymalne pokolorowanie krawędzi grafu to legalne pokolorowanie, przy którym zużyto najmniejszą możliwą liczbę kolorów.

Indeks chromatyczny grafu to minimalna liczba kolorów wystarczająca do pokolorowania krawędzi grafu legalnie, oznaczamy go przez ${\displaystyle \chi '}$^[1].

Kolorowanie krawędzi jest równoważne kolorowaniu wierzchołków grafu krawędziowego.

Kolorowanie krawędzi grafu ${\displaystyle G}$ nazywamy kolorowaniem krawędzi rozróżniającym wierzchołki, jeśli dla każdej pary wierzchołków ${\displaystyle u}$ i ${\displaystyle v}$ zbiory ${\displaystyle S(u),}$ ${\displaystyle S(v)}$ są różne. Niech ${\displaystyle {\textrm {vdi}}(G)}$ będzie najmniejszą liczbą kolorów potrzebnych do takiego kolorowania, jeśli kolorowanie krawędzi grafu jest właściwe. Natomiast ${\displaystyle {\textrm {gvdi}}(G)}$ będzie najmniejszą liczbą kolorów potrzebnych do niewłaściwego kolorowania rozróżniającego wierzchołki.

P.N. Balister, B. Bollobás oraz R.H. Schelp udowodnili następujące twierdzenie: Twierdzenie 1. Niech graf G będzie grafem dwuregularnym, wówczas ${\displaystyle {\textrm {vdi}}(G)\leqslant {\sqrt {2n}}+24}$

Algorytmy kolorowania krawędzi

Problem kolorowania krawędzi, podobnie jak klasycznego kolorowania wierzchołków, jest NP-trudny – nie istnieją wielomianowe algorytmy kolorujące grafy zawsze w sposób optymalny. Do algorytmów przybliżonych należą:

• algorytm NC
• algorytm NTL (Nishizeki, Terada, Leven)

Zastosowania

Kolorowanie krawędzi grafu pełnego posłużyło do zdefiniowania liczb Ramseya.

Zobacz też

• indeks chromatyczny

Przypisy