Kolorystyka krawędzi wykresu – Wikipedia

W teorii grafów i algorytmice, a Kolorystyka krawędzi wykresu polega na przypisywaniu koloru każdej krawędzi, zapobiegającym dwóch krawędzi o wspólnym końcu, aby mieć ten sam kolor.

Figurka przeciwna jest przykładem prawidłowego zabarwienia krawędzi. Rzeczywiście jest weryfikowane, że żaden szczyt nie jest wspólny dla dwóch krawędzi tego samego koloru. Należy zauważyć, że tutaj nie byłoby możliwe zabarwienie krawędzi wykresu tylko dwoma kolorami.

Wspomniane bez dodatkowych wyjaśnień, wyrażenie „kolorowanie krawędzi wykresu” wyznacza fakt przypisywania każdemu krawędziowi koloru, tak że dwie sąsiednie krawędzie (to znaczy posiadanie wspólnego końca) i nigdy nie miały tego samego koloru. (Jest to podwójne pojęcie kolorowania szczytów wykresu.)

Minimalna liczba kolorów wymaganych do pokolorowania krawędzi wykresu G jest nazywany indeks chromatyczny z G Lub Chromatyczna liczba krawędzi z G i odnotowano χ ′ ( G ), a czasem χ _Pierwszy ( G ). Nie należy go mylić z liczbą chromatyczną (szczytami) G , zauważono χ ( G ).

Si d ( G ) to maksymalny stopień G i μ ( G ) Jego mnogość (maksymalna liczba krawędzi na pert pików), następnie:

Klasyfikacja wykresów i określenie ich liczby chromatycznej [[[ modyfikator |. Modyfikator i kod ]

Jak wspomniano powyżej, χ ′ ( G ) jest zawsze równy δ ( G ) lub à δ ( G ) + 1. G Klasa 1 jest powiedziana w pierwszym przypadku i klasie 2 w drugim.

W 1981 roku Holyer udowodnił ^{[[[ Pierwszy ]} To, że określenie przynależności prostego wykresu do jednej lub drugiej z tych dwóch klas jest problemem NP. Jednak w niektórych szczególnych przypadkach istnieją zasady, które pozwalają szybko zakończyć.

Na przykład, zwrócone ^{[[[ 2 ]} Że prosty wykres maksymalnego stopnia stopnia co najmniej 8, jest zawsze klasy 1 i przypuszczał, że tak samo dla maksymalnego stopnia równego 6 lub 7 (znamy proste wykresy stopnia płaskie maksymalnie 2, 3, 4 lub 5 i klasa 2). Sanders (W) et Zhao ^{[[[ 3 ]} wykazali przypadek δ ( G ) = 7 do przypuszczenia.

Ta domniemanie znajduje zastosowanie w całkowitej kolorystyce (W) .

Kolorowanie krawędzi kompletnych wykresów może być użyte do zaprogramowania turnieju okrągłego w jak najmniejszych rundach, tak aby każda para konkurentów staru się starci w jednej z rund. W tej aplikacji szczyty wykresu odpowiadają konkurentom turnieju, krawędzie odpowiadają gier, a kolory krawędzi odpowiadają rundom ^{[[[ 4 ]} .

Kolejną aplikacją może być planowanie produkcji zestawu obiektów z ograniczeniem, że każde zadanie produkcyjne musi być wykonywane na konkretnym komputerze, uniemożliwiając jednocześnie wykonanie tego samego maszyny. Jeśli wszystkie zadania mają taki sam czas trwania, problem ten można sformalizować jako kolorowanie dwustronnego multigrafu, w którym szczyty po jednej stronie dwustronnej reprezentują obiekty, które mają być wyprodukowane, szczyty po drugiej stronie dwustronnej reprezentują Maszyny produkcyjne, krawędzie reprezentują zadania do wykonania, a kolory reprezentują odstępy czasu, w których można wykonać każde zadanie ^{[[[ 5 ]} .

• (W) Tommy R. Jensen a Bjarne toft, Problemy z kolorowaniem wykresu , John Wiley & Sons, 2011 ( Pierwszy ^Odnośnie wyd. 1995), 320 P. (ISBN 978-1-118-03074-5 W Czytaj online )
• (z) Dénes kőnig, ‘ O wykresach i ich zastosowaniu w celu ustalenia teorii i teorii ilościowej » W Annały matematyczne W tom. 77, N ^O 4, 1916 W P. 453-465 (Doi 10.1007 / BF01456961 W Czytaj online [[[ Archive Du 19 stycznia 2015 ] , skonsultuałem się z 30 września 2013 )