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.

Desargues graph 3color edge.svg

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ędziEdytuj

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

ZastosowaniaEdytuj

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

Zobacz teżEdytuj

PrzypisyEdytuj

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