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 nazywamy kolorowaniem krawędzi grafu , natomiast zbiór zbiorem kolorów.

Niech oznacza zbiór kolorów krawędzi incydentnych z wierzchołkiem .

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 dla każdych dwóch sąsiednich krawędzi, w przeciwnym przypadku kolorowanie nazywamy niewłaściwym[1].

k-kolorowaniem nazywamy kolorowanie , czyli kolorujemy przy użyciu 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 [1].

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

Kolorowanie krawędzi grafu nazywamy kolorowaniem krawędzi rozróżniającym wierzchołki, jeśli dla każdej pary wierzchołków i zbiory , są różne. Niech będzie najmniejszą liczbą kolorów potrzebnych do takiego kolorowania, jeśli kolorowanie krawędzi grafu jest właściwe. Natomiast 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

Algorytmy kolorowania krawędzi[edytuj]

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]

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

Zobacz też[edytuj]

Przypisy

  1. a b Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 96. ISBN 0-387-95014-1.