Kolorowanie krawędzi

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Desargues graph 3color edge.svg

Kolorowanie krawędzi grafu – 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 \chi'.

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 \textrm{vdi}(G) będzie najmniejszą liczbą kolorów potrzebnych do takiego kolorowania, jeśli kolorowanie krawędzi grafu jest właściwe. Natomiast \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 \textrm{vdi}(G) \leqslant \sqrt{2n} + 24

Algorytmy kolorowania krawędzi[edytuj | edytuj kod]

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żą:

Zastosowania[edytuj | edytuj kod]

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

Zobacz też[edytuj | edytuj kod]