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

Definicje

Odwzorowanie (funkcję) postaci nazywamy kolorowaniem krawędzi grafu , natomiast zbiór nazywamy wtedy: zbiorem kolorów (dla tego kolorowania).

Uwaga. Czasami – w odniesieniu do funkcji rozumianej jak w powyższym określeniu – używa się także pojęcia funkcji kolorowania (ang. coloring function), aby zaakcentować w słowie, że przy okazji przywoływania gdzieś dalej kolorowania (nazywanego dla odróżnienia, właśnie po prostu: kolorowaniem) chodzi nam nie tyle o samą jakąś (zadaną pewnym napisem) funkcję przyporządkowywania kolorów, krawędziom pewnego grafu; co pewną procedurę kolorowania – pewien szczególny zamysł (sposób rozumowania) za taką procedurą, stojący.

k-kolorowaniem nazywamy kolorowanie , czyli kolorujemy przy użyciu kolorów (w zadanym pewnym grafie).

Uwaga. Zauważmy tutaj jednocześnie, że w powyższej definicji -kolorowania, nie oczekujemy, aby funkcja kolorowania była surjekcją, to znaczy nie żądamy wykorzystania wszystkich, czy choćby większości, z kolorów, które zostały nam dane „do dyspozycji” („przy użyciu” których, mamy kolorować). Tym samym, dla przykładu: w dowolnym grafie, za pewne -kolorowanie krawędziowe, powinniśmy także uznać sytuację, w której wszystkie krawędzie tego grafu, zostały pokolorowane tym samym (pojedynczym) kolorem.

Pewne rodzaje kolorowania krawędziowego

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.

Optymalne pokolorowanie krawędzi grafu to prawidłowe (por. powyżej) pokolorowanie, przy którym zużyto najmniejszą możliwą liczbę kolorów.

Indeksem chromatyczny grafu nazywamy wielkość, określającą minimalną liczba kolorów wystarczająca do pokolorowania krawędzi tegoż grafu, w sposób prawidłowy (według definicji prawidłowego kolorowania powyżej). Indeks chromatyczny dla danego grafu , oznaczamy przy wykorzystaniu symbolu: .

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

Najmniejsza liczba kolorów

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

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 (krawędziowego), 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. Niech graf będzie grafem dwuregularnym, wówczas .

Algorytmy kolorowania krawędzi Problem kolorowania krawędzi, podobnie jak klasycznego kolorowania wierzchołków, należy do tak zwanej klasy problemów NP-trudnych – 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

Uwagi

Przypisy

Linki zewnętrzne [dostęp 2025-10-12].

Kategoria:Teoria grafów