Wrzeciono Mosera
| Wrzeciono Mosera | |
|---|---|
 | |
| Nazwany po | Leo Moser , William Moser |
| Wierzchołki | 7 |
| Krawędzie | 11 |
| Promień | 2 |
| Średnica | 2 |
| Obwód | 3 |
| Automorfizmy | 8 |
| Liczba chromatyczna | 4 |
| Indeks chromatyczny | 4 |
| Nieruchomości |
płaski wykres Lamana odległości jednostkowej |
| Tabela wykresów i parametrów | |
W teorii grafów , gałęzi matematyki, wrzeciono Mosera (zwane także wrzecionem Mosera lub wykresem Mosera ) jest grafem nieskierowanym , nazwanym na cześć matematyków Leo Mosera i jego brata Williama, z siedmioma wierzchołkami i jedenastoma krawędziami. Jest to wykres odległości jednostkowej wymagający czterech kolorów w dowolnym kolorowaniu wykresu , a jego istnienie można wykorzystać do udowodnienia, że liczba chromatyczna płaszczyzny wynosi co najmniej cztery.
Wrzeciono Mosera zostało również nazwane grafem Hajósa na cześć György Hajósa , ponieważ można je postrzegać jako przykład konstrukcji Hajósa . Jednak nazwa „wykres Hajós” została również zastosowana do innego wykresu, w postaci trójkąta wpisanego w sześciokąt.
Budowa
Jako wykres odległości jednostkowej, wrzeciono Mosera jest utworzone przez dwa romby o kątach 60 i 120 stopni, tak że boki i krótkie przekątne rombów tworzą trójkąty równoboczne. Dwa romby są umieszczone na płaszczyźnie, dzieląc jeden z ich wierzchołków pod kątem ostrym, w taki sposób, że pozostałe dwa wierzchołki pod kątem ostrym są oddalone od siebie o jednostkę odległości. Jedenaście krawędzi wykresu to osiem boków rombu, dwie krótkie przekątne rombu i krawędź między parą wierzchołków o kącie ostrym w odległości jednostkowej.
Wrzeciono Mosera można również skonstruować grafowo-teoretycznie, bez odniesienia do osadzania geometrycznego, używając konstrukcji Hajósa , zaczynając od dwóch pełnych grafów na czterech wierzchołkach. Ta konstrukcja usuwa krawędź z każdego pełnego wykresu, łączy dwa punkty końcowe usuniętych krawędzi w jeden wierzchołek wspólny dla obu klik i dodaje nową krawędź łączącą pozostałe dwa punkty końcowe usuniętej krawędzi.
Innym sposobem konstruowania wrzeciona Mosera jest wykres dopełnienia wykresu utworzonego z wykresu użyteczności K 3,3 przez podzielenie jednej z jego krawędzi.
Zastosowanie do problemu Hadwigera-Nelsona
Hadwigera -Nelsona pyta, ile kolorów potrzeba do pokolorowania punktów płaszczyzny euklidesowej w taki sposób, aby każdej parze punktów w jednostkowej odległości od siebie przypisano różne kolory. Oznacza to, że pyta o liczbę chromatyczną nieskończonego wykresu, którego wierzchołkami są wszystkie punkty na płaszczyźnie, a krawędziami są wszystkie pary punktów w jednostkowej odległości.
Wrzeciono Mosera wymaga czterech kolorów w dowolnym kolorowaniu wykresu: w dowolnym trójkolorowym kolorze jednego z dwóch rombów, z których jest utworzone, dwa wierzchołki rombów pod ostrymi kątami musiałyby mieć ten sam kolor co inne. Ale jeśli wspólny wierzchołek dwóch rombów ma ten sam kolor co dwa przeciwległe wierzchołki o ostrych kątach, to te dwa wierzchołki mają ten sam kolor, co narusza wymóg, aby łącząca je krawędź miała punkty końcowe o różnych kolorach. Ta sprzeczność pokazuje, że trzy kolory są niemożliwe, więc konieczne są co najmniej cztery kolory. Cztery kolory wystarczą również do pokolorowania wrzeciona Mosera, co wynika chociażby z tego, że jest ono degeneracja wynosi trzy.
Alternatywny dowód na to, że wrzeciono Moser wymaga czterech kolorów, wynika z konstrukcji Hajós. Oba pełne wykresy, z których utworzono wrzeciono Mosera, wymagają czterech kolorów, a konstrukcja Hajós zachowuje tę właściwość. Jeszcze bardziej bezpośrednio, każdy niezależny zestaw we wrzecionie Mosera ma co najwyżej dwa wierzchołki, więc do pokrycia wszystkich siedmiu wierzchołków potrzeba co najmniej czterech niezależnych zestawów.
Ponieważ wrzeciono Mosera jest podgrafem nieskończonego wykresu jednostkowej odległości płaszczyzny, wykres płaszczyzny również wymaga co najmniej czterech kolorów w dowolnym zabarwieniu. Twierdzenie de Bruijna-Erdősa (przy założeniu, że aksjomat wyboru jest prawdą), liczba chromatyczna płaszczyzny jest taka sama, jak największa liczba chromatyczna dowolnego z jej skończonych podgrafów; aż do odkrycia rodziny 5-chromatycznych wykresów jednostkowych odległości w 2018 r. nie znaleziono żadnego podgrafu nieskończonego wykresu jednostkowego odległości, który wymagałby większej liczby kolorów niż wrzeciono Mosera. Jednak najlepsza górna granica liczby chromatycznej płaszczyzny wynosi siedem, znacznie więcej niż liczba kolorów wymagana dla wrzeciona Mosera.
Inne właściwości i zastosowania
Wrzeciono Mosera jest grafem planarnym , co oznacza, że można go narysować bez przecięć na płaszczyźnie. Nie jest jednak możliwe utworzenie takiego rysunku z prostymi krawędziami, który byłby jednocześnie rysunkiem odległości jednostkowych; to znaczy, że nie jest to wykres zapałek . Wrzeciono Mosera jest również grafem Lamana , co oznacza, że po osadzeniu w płaszczyźnie tworzy układ o minimalnej sztywności . Jako planarny graf Lamana jest to wykres pseudotriangulacji spiczastej, co oznacza, że można go osadzić w płaszczyźnie w taki sposób, że nieograniczoną ścianą jest otoczka wypukła osadzania i każda ograniczona ściana jest pseudotrójkątem z tylko trzema wierzchołkami wypukłymi.
Graf dopełniacza wykresu Mosera jest grafem bez trójkątów . Zatem osadzanie odległości jednostkowej wykresu Mosera można wykorzystać do rozwiązania problemu umieszczenia siedmiu punktów na płaszczyźnie w taki sposób, aby każda trójka punktów zawierała co najmniej jedną parę w odległości jednostkowej od siebie.
Dodanie dowolnej krawędzi do wrzeciona Mosera daje w wyniku wykres, którego nie można osadzić w płaszczyźnie jako wykresu odległości jednostkowej i nie istnieje homomorfizm wykresu od wrzeciona Mosera do jakiegokolwiek mniejszego wykresu odległości jednostkowej. Te dwie właściwości wrzeciona Mosera zostały wykorzystane przez Horvata, Kratochvíla i Pisanskiego (2011) do pokazania NP-twardości testowania, czy dany graf ma dwuwymiarową reprezentację jednostkową odległości; dowód wykorzystuje redukcję z 3SAT , w której wrzeciono Mosera jest używane jako centralny gadżet do ustalania prawdy w redukcji.
Wrzeciono Mosera może być również użyte do udowodnienia wyniku w teorii Euklidesa Ramseya : jeśli T jest dowolnym trójkątem na płaszczyźnie, a punkty płaszczyzny są dwukolorowe, czarno-białe, to istnieje albo czarne tłumaczenie T , albo para białych punktów w jednostkowej odległości od siebie. Niech bowiem M będzie jednostkowym osadzeniem wrzeciona Mosera i niech M + T będzie sumą Minkowskiego M i T . Jeśli M + T nie ma białej pary jednostka-odległość, to każda z trzech kopii wrzeciona Mosera w M + T musi mieć co najwyżej dwa białe punkty, ponieważ białe punkty w każdej kopii muszą tworzyć niezależny zbiór i największy niezależny zbiór w Moserze wrzeciono ma rozmiar dwa. Dlatego wśród siedmiu wierzchołków wrzeciona Mosera jest co najwyżej sześć, które mają białą kopię w M + T , więc musi istnieć jeden z siedmiu wierzchołków, których wszystkie kopie są czarne. Ale wtedy trzy kopie tego wierzchołka tworzą translację T .