Liczba przejść (teoria grafów)

Rysunek wykresu Heawood z trzema skrzyżowaniami. Jest to minimalna liczba przecięć spośród wszystkich rysunków tego wykresu, więc graf ma liczbę przecięć

cr(G) = 3

.

W teorii grafów liczba przecięć $cr(G)$ grafu G jest najmniejszą liczbą przecięć krawędzi $płaskiego$ rysunku grafu $G$ . Na przykład graf jest planarny wtedy i tylko wtedy, gdy jego liczba przejść wynosi zero. Określenie liczby przecięć nadal ma ogromne znaczenie w rysowaniu wykresów, ponieważ badania użytkowników wykazały, że rysowanie wykresów z niewielką liczbą przecięć ułatwia ludziom zrozumienie rysunku.

Badanie numerów skrzyżowań wywodzi się z problemu cegielni Turána , w którym Pál Turán poprosił o plan fabryki, który zminimalizowałby liczbę skrzyżowań między torami łączącymi cegielnie z miejscami składowania. Matematycznie problem ten można sformalizować jako pytanie o numer przecięcia kompletnego wykresu dwudzielnego . Ten sam problem pojawił się niezależnie w socjologii mniej więcej w tym samym czasie, w związku z konstruowaniem socjogramów . Przypuszczalny wzór Turána na przecinające się liczby kompletnych grafów dwudzielnych pozostaje niesprawdzony, podobnie jak analogiczny wzór na pełne grafy .

liczby przecięć stwierdza, że dla grafów, w których liczba $e$ krawędzi jest wystarczająco większa $e 3 / n niż$ liczba $n$ wierzchołków , liczba przecięć jest co najmniej proporcjonalna do 2 . Ma zastosowania w VLSI i geometrii padania .

Bez dalszych zastrzeżeń, liczba skrzyżowań umożliwia rysunki, w których krawędzie mogą być reprezentowane przez dowolne krzywe. Odmiana tej koncepcji, prostoliniowa liczba przecięć , wymaga, aby wszystkie krawędzie były odcinkami linii prostych i może różnić się od liczby przecięć. W szczególności liczba przecięć prostoliniowych pełnego wykresu jest zasadniczo taka sama, jak minimalna liczba wypukłych czworoboków określona przez zbiór $n$ punktów w ogólnej pozycji. Problem określenia tej liczby jest ściśle powiązany z problemem szczęśliwego zakończenia .

Definicje

Na potrzeby określenia liczby przecięć rysunek grafu nieskierowanego jest odwzorowaniem wierzchołków grafu na punkty rozłączne na płaszczyźnie oraz krawędzi grafu na krzywe łączące ich dwa końce. Żaden wierzchołek nie powinien być odwzorowywany na krawędzi, której nie jest punktem końcowym, a gdy dwie krawędzie mają przecinające się krzywe (inne niż we wspólnym punkcie końcowym), ich przecięcia powinny tworzyć skończony zestaw właściwych skrzyżowań, w których dwie krzywe są poprzeczne . Przecięcie jest liczone osobno dla każdego z tych punktów przecięcia, dla każdej pary przecinających się krawędzi. Liczba przecięć wykresu jest zatem minimalną liczbą przecięć na wszystkich takich rysunkach na rysunku.

Niektórzy autorzy dodają więcej ograniczeń do definicji rysunku, na przykład, że każda para krawędzi ma co najwyżej jeden punkt przecięcia (wspólny punkt końcowy lub skrzyżowanie). W przypadku liczby przecięć, jak zdefiniowano powyżej, ograniczenia te nie mają znaczenia, ponieważ minimalny rysunek przecięcia nie może mieć krawędzi z wieloma punktami przecięcia. Jeśli dwie krawędzie ze wspólnym punktem końcowym przecinają się, rysunek można zmienić lokalnie w punkcie przecięcia, pozostawiając resztę rysunku bez zmian, aby utworzyć inny rysunek z jednym przecięciem mniej. I podobnie, jeśli dwie krawędzie przecinają się dwa lub więcej razy, rysunek można zmienić lokalnie w dwóch punktach przecięcia, aby utworzyć inny rysunek z dwoma przecięciami. Jednak te ograniczenia są istotne dla wariantów definicji liczby skrzyżowań, które na przykład liczą tylko liczbę par przecinających się krawędzi, a nie liczbę skrzyżowań.

Przypadki specjalne

Od kwietnia 2015 r. Przecinające się numery są znane z bardzo niewielu rodzin grafów. W szczególności, z wyjątkiem kilku początkowych przypadków, liczba przecięć pełnych grafów, dwudzielnych pełnych grafów i iloczynów cykli pozostaje nieznana, chociaż nastąpił pewien postęp w dolnych granicach.

Kompletne grafy dwudzielne

Optymalny rysunek

K 4,7

pokazujący, że problem cegielni Turána z 4 miejscami składowania (żółte plamy) i 7 piecami (niebieskie plamy) wymaga 18 skrzyżowań (czerwone kropki)

Podczas II wojny światowej węgierski matematyk Pál Turán był zmuszony do pracy w cegielni, pchając wagony cegieł z pieców do miejsc składowania. Fabryka miała tory z każdego pieca do każdego miejsca składowania, a wagony były trudniejsze do pchania w miejscach, w których tory się krzyżowały, z czego Turán został poprowadzony, aby zadać problem swojej cegielni: w jaki sposób piece, miejsca składowania i tory zorganizować tak, aby zminimalizować całkowitą liczbę przejazdów? Z matematycznego punktu widzenia piece i miejsca składowania można sformalizować jako wierzchołki kompletnego grafu dwudzielnego , z torami jako jego krawędziami. Układ fabryki można przedstawić jako rysunek tego wykresu, więc pojawia się problem: jaka jest minimalna możliwa liczba skrzyżowań na rysunku kompletnego wykresu dwudzielnego ?

Kazimierz Zarankiewicz próbował rozwiązać problem cegielni Turána; jego dowód zawierał błąd, ale ustalił prawidłową górną granicę

{\ Displaystyle {\ textrm {cr}} (K_ {m, n}) \ równoważnik \ lewo \lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}} \right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor}

dla numeru przecięcia kompletnego grafu dwudzielnego $K m,n$ . Przypuszcza się, że ta granica jest optymalną liczbą przejść dla wszystkich kompletnych grafów dwudzielnych.

Kompletne wykresy i kolorowanie wykresów

Problem określenia liczby przecięć pełnego grafu został po raz pierwszy postawiony przez Anthony'ego Hilla i pojawił się drukiem w 1960 roku. Hill i jego współpracownik John Ernest byli dwoma artystami konstrukcjonistami zafascynowanymi matematyką. Nie tylko sformułowali ten problem, ale także zapoczątkowali domniemaną formułę tego skrzyżowania, którą Richard K. Guy opublikował w 1960 roku. Mianowicie wiadomo, że zawsze istnieje rysunek z

{\ Displaystyle {\ textrm {cr}} (K_ {p}) \ równoważnik {\ frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor}

przejścia. Ten wzór daje wartości $1, 3, 9, 18, 36, 60, 100, 150$ dla $p = 5, ..., 12$ ; patrz sekwencja A000241 w On-line Encyclopedia of Integer Sequences . Przypuszcza się, że nie może być lepszego rysunku, więc ten wzór daje optymalną liczbę przecięć dla pełnych grafów. Niezależne sformułowanie tego samego przypuszczenia zostało sformułowane przez Thomasa L. Saaty'ego w 1964 roku.

Saaty dodatkowo zweryfikował, że ten wzór daje optymalną liczbę skrzyżowań dla $p \leq 10,$ a Pan i Richter wykazali, że jest on również optymalny dla $p = 11, 12$ .

Hipoteza Albertsona , $Kn sformułowana$ przez Michaela O. Albertsona w 2007 roku, mówi, że spośród wszystkich grafów o liczbie chromatycznej $n$ graf pełny ma najmniejszą liczbę przejść. Oznacza to, że jeśli domniemany wzór na liczbę przecięć całego grafu jest poprawny, to każdy $n$ -chromatyczny ma liczbę przecięć co najmniej równą tej samej formule. Obecnie wiadomo, że hipoteza Albertsona obowiązuje dla $n \leq 16$ .

Wykresy sześcienne

Znane są najmniejsze grafy sześcienne z przecinającymi się liczbami 1–8 i 11 (sekwencja A110507 w OEIS ). Najmniejszym grafem sześciennym przecinającym 1 jest pełny graf dwudzielny $K 3,3$ , z 6 wierzchołkami. Najmniejszym grafem sześciennym z dwoma przecięciami jest graf Petersena z 10 wierzchołkami. Najmniejszym grafem sześciennym z trzema skrzyżowaniami jest graf Heawooda z 14 wierzchołkami. Najmniejszym grafem sześciennym z 4 skrzyżowaniami jest graf Möbiusa-Kantora z 16 wierzchołkami. Najmniejszym grafem sześciennym z 5 skrzyżowaniami jest graf Pappusa z 18 wierzchołkami. Najmniejszym grafem sześciennym z 6 skrzyżowaniami jest graf Desarguesa z 20 wierzchołkami. Żaden z czterech 7-przecinających się grafów sześciennych z 22 wierzchołkami nie jest dobrze znany. Najmniejsze grafy sześcienne z 8 przecięciami obejmują graf Nauru i graf McGee lub graf (3,7)-klatkowy , z 24 wierzchołkami. Najmniejsze 11-przecinające się grafy sześcienne obejmują graf Coxetera z 28 wierzchołkami.

W 2009 roku Pegg i Exoo przypuszczali, że najmniejszym grafem sześciennym z przecięciem numer 13 jest wykres Tutte-Coxeter , a najmniejszym wykresem sześciennym z przecięciem numer 170 jest 12-klatka Tutte .

Złożoność i przybliżenie

Ogólnie rzecz biorąc, określenie liczby przecięć wykresu jest trudne; Garey i Johnson wykazali w 1983 roku, że jest to problem NP-trudny . W rzeczywistości problem pozostaje NP-trudny, nawet jeśli jest ograniczony do grafów sześciennych i prawie planarnych (wykresów, które stają się planarne po usunięciu pojedynczej krawędzi). Ściśle powiązany problem, wyznaczanie liczby przejść prostoliniowych, jest kompletny dla egzystencjalnej teorii liczb rzeczywistych .

Z drugiej strony istnieją wydajne algorytmy określające, czy liczba przejść jest mniejsza niż ustalona stała $k$ . Innymi słowy, problem jest wykonalny z ustalonymi parametrami . Pozostaje to trudne dla większych $k$ , takich jak $k = | V |/2$ . Istnieją również wydajne algorytmy aproksymacji cr $(G)$ na wykresach o ograniczonym stopniu. W praktyce heurystyczne , takie jak prosty algorytm, który rozpoczyna się bez krawędzi i stale dodaje każdą nową krawędź w sposób, który generuje jak najmniej dodatkowych skrzyżowań. Algorytmy te są wykorzystywane w przetwarzania rozproszonego Rectilinear Crossing Number .

Przecinająca się nierówność liczbowa

Dla nieskierowanego grafu prostego $G$ z $n$ wierzchołkami i $e$ krawędziami takimi, że $e > 7 n$ liczba przecięć wynosi zawsze co najmniej

{\ Displaystyle \ nazwa operatora {cr} (G) \ geq {\ Frac {e ^ {3}} {29n ^ {2}}}.}

Ta zależność między krawędziami, wierzchołkami i liczbą skrzyżowań została odkryta niezależnie przez Ajtai , Chvátal , Newborn i Szemerédi oraz przez Leightona . Jest to znane jako przecinająca się nierówność liczbowa lub lemat przecinający.

Stała $29$ jest jak dotąd najlepiej znaną i pochodzi od Ackermana. Stałą $7$ można obniżyć do $4$ , ale kosztem zastąpienia $29$ gorszą stałą $64$ .

Motywacją Leightona do studiowania liczb krzyżujących się były zastosowania do projektowania VLSI w informatyce teoretycznej. Później Székely zdał sobie również sprawę, że ta nierówność dała bardzo proste dowody niektórych ważnych twierdzeń w geometrii incydentów , takich jak twierdzenie Becka i twierdzenie Szemerédi-Trottera , a Tamal Dey użył jej do udowodnienia górnych granic geometrycznych k -zbiorów .

Wariacje

Jeśli wymagane jest, aby krawędzie były rysowane jako segmenty linii prostych, a nie dowolne krzywe, niektóre wykresy wymagają większej liczby skrzyżowań. Liczba przecięć prostoliniowych jest zdefiniowana jako minimalna liczba przecięć rysunku tego typu. Jest zawsze co najmniej tak duża, jak liczba przecięcia, aw przypadku niektórych wykresów jest większa. Wiadomo, że na ogół liczba skrzyżowań prostoliniowych nie może być ograniczona funkcją liczby skrzyżowań. Prostoliniowe liczby skrzyżowań dla $K 5$ do $K 12$ to $1, 3, 9, 19, 36, 62, 102, 153$ , ( A014540 ) i znane są wartości do $K 27 , przy czym$ $K 28$ wymaga 7233 lub 7234 skrzyżowań. Dalsze wartości są zbierane w ramach projektu Rectilinear Crossing Number.

Graf ma lokalną liczbę przecięć $k$ , jeśli można go narysować z co najwyżej $k$ przecięciami na krawędź, ale nie mniej. Grafy, które można narysować z maksymalnie $k$ przecięciami na krawędź, są również nazywane $k$ -planarnymi.

Inne warianty liczby skrzyżowań obejmują liczbę skrzyżowań parami (minimalna liczba par krawędzi, które przecinają się na dowolnym rysunku) i nieparzystą liczbę skrzyżowań (liczba par krawędzi, które przecinają się nieparzystą liczbę razy na dowolnym rysunku). Nieparzysta liczba skrzyżowań jest co najwyżej równa liczbie skrzyżowań parami, która jest co najwyżej równa liczbie skrzyżowań. Jednak zgodnie z twierdzeniem Hananiego – Tutte'a , ilekroć jedna z tych liczb jest równa zeru, wszystkie są. Schaefer ( 2014 , 2018 ) analizuje wiele takich wariantów.

Zobacz też

Planaryzacja , graf planarny utworzony przez zastąpienie każdego przecięcia nowym wierzchołkiem
Problem z trzema narzędziami , łamigłówka, która pyta, czy $K 3,3$ można narysować z 0 skrzyżowaniami