Łańcuch Kempe
W matematyce łańcuch Kempe jest urządzeniem używanym głównie do badania twierdzenia o czterech kolorach . Intuicyjnie jest to połączony łańcuch punktów na wykresie o naprzemiennych kolorach.
Historia
Łańcuchy Kempe zostały po raz pierwszy użyte przez Alfreda Kempe w jego próbie udowodnienia twierdzenia o czterech kolorach. Chociaż jego dowód okazał się niekompletny, metoda łańcuchów Kempe jest kluczowa dla udanych współczesnych dowodów (Appel i Haken, Robertson i in., itp.). Ponadto metoda ta jest używana w dowodzie twierdzenia o pięciu kolorach autorstwa Percy'ego Johna Heawooda , słabszej postaci twierdzenia o czterech kolorach.
Definicja formalna
Termin „łańcuch Kempe” jest używany na dwa różne, ale powiązane sposoby.
Załóżmy, że G jest grafem o zbiorze wierzchołków V i mamy daną funkcję kolorującą
gdzie S jest skończonym zbiorem kolorów, zawierającym co najmniej dwa różne kolory a i b . Jeśli v jest wierzchołkiem o kolorze a , to łańcuch ( a , b )-Kempe G zawierający v jest maksymalnie spójnym podzbiorem V , który zawiera v i którego wszystkie wierzchołki są kolorowe a lub b .
Powyższa definicja jest tym, z czym pracował Kempe. Zazwyczaj zbiór S ma cztery elementy (cztery kolory z twierdzenia o czterech kolorach), a c jest właściwym kolorowaniem , to znaczy każdej parze sąsiednich wierzchołków w V przypisano różne kolory.
Bardziej ogólna definicja, która jest używana we współczesnych komputerowych dowodach twierdzenia o czterech kolorach, jest następująca. Załóżmy ponownie, że G jest grafem o zbiorze krawędzi E i tym razem mamy funkcję kolorującą
Jeśli e jest krawędzią, której przypisano kolor a , to łańcuch ( a , b )-Kempe G zawierający e jest maksymalnie spójnym podzbiorem E , który zawiera e i którego wszystkie krawędzie są w kolorze a lub b .
Ta druga definicja jest zwykle stosowana, gdy S ma trzy elementy, powiedzmy a , b i c , a V jest grafem sześciennym , to znaczy każdy wierzchołek ma trzy incydentne krawędzie. Jeśli taki graf jest odpowiednio pokolorowany, to każdy wierzchołek musi mieć krawędzie w trzech różnych kolorach, a łańcuchy Kempe kończą się ścieżkami , co jest prostsze niż w przypadku pierwszej definicji.
W kwestii map
Zastosowanie do twierdzenia o czterech kolorach
W twierdzeniu o czterech kolorach Kempe był w stanie udowodnić, że wszystkie grafy koniecznie mają wierzchołek o wartości pięciu lub mniejszej lub zawierają wierzchołek, który styka się z pięcioma innymi wierzchołkami, zwanymi sąsiadami . W związku z tym, aby udowodnić twierdzenie o czterech kolorach, wystarczy udowodnić, że wszystkie wierzchołki o liczbie pięciu lub mniejszej były czterokolorowe. Kempe był w stanie udowodnić przypadek stopnia czwartego i dać częściowy dowód stopnia piątego za pomocą łańcuchów Kempe.
W tym przypadku łańcuchy Kempe służą do udowodnienia tezy, że żaden wierzchołek nie może stykać się z czterema kolorami różnymi od siebie, czyli mieć stopień 4. Po pierwsze , można stworzyć graf z wierzchołkiem v i czterema wierzchołkami jako sąsiadami. Jeśli usuniemy wierzchołek v , możemy pokolorować pozostałe wierzchołki czterokrotnie. Możemy ustawić kolory jako (w kolejności zgodnej z ruchem wskazówek zegara) czerwony, żółty, niebieski i zielony. W tej sytuacji może istnieć łańcuch Kempe łączący czerwonych i niebieskich sąsiadów lub łańcuch Kempe łączący zielonych i żółtych sąsiadów, ale nie oba, ponieważ te dwie ścieżki musiałyby się przecinać, a wierzchołek, w którym się przecinają, nie może być pokolorowany. Zakładając, że łańcuch Kempe łączy zielonych i żółtych sąsiadów, czerwony i niebieski niekoniecznie muszą mieć między sobą łańcuch Kempe. Tak więc, umieszczając oryginalny wierzchołek v z powrotem do grafu, możemy po prostu odwrócić kolory czerwonego wierzchołka i jego sąsiadów (w tym czerwonego wierzchołka, czyniąc go niebieskim) i pokolorować wierzchołek v jako czerwony. Daje to czterokolorowy wykres.
Inne aplikacje
Łańcuchy Kempe zostały wykorzystane do rozwiązania problemów związanych z przedłużaniem kolorów .