Kolorowanie krawędzi

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Kolorowanie krawędzi grafu to rozszerzenie klasycznego kolorowania grafu na krawędzie. Jest to przyporządkowywanie krawędziom grafu liczb naturalnych symbolizujących kolory. Odwzorowanie $c \colon E(G) \to S$ nazywamy kolorowaniem krawędzi grafu $G$ , natomiast zbiór $S$ zbiorem kolorów.

Niech $S (v)$ oznacza zbiór kolorów krawędzi incydentnych z wierzchołkiem $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 $c(e) \neq c(f)$ dla każdych dwóch sąsiednich krawędzi, w przeciwnym przypadku kolorowanie nazywamy niewłaściwym.

$k$-kolorowaniem nazywamy kolorowanie $c \colon E(G) \to \{1,\ldots,k\}$ , czyli kolorujemy przy użyciu $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 $χ'$ .

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

Kolorowanie krawędzi grafu $G$ nazywamy kolorowaniem krawędzi rozróżniającym wierzchołki, jeśli dla każdej pary wierzchołków $u$ i $v$ zbiory $S (u)$ , $S (v)$ są różne. Niech $vdi(G)$ będzie najmniejszą liczbą kolorów potrzebnych do takiego kolorowania, jeśli kolorowanie krawędzi grafu jest właściwe. Natomiast $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 $\textrm{vdi}(G) \leqslant \sqrt{2n} + 24$

[edytuj] 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żą: