Problem cegielni Turána - Turán's brick factory problem
 |
Nierozwiązany problem w matematyce : Czy można narysować kompletny wykres dwudzielny z mniejszą liczbą przecięć niż liczba podana przez Zarankiewicza?
(więcej nierozwiązanych problemów matematycznych)
|
W matematyce na wykresie rysunku , problemem cegielni Turan za pyta o minimalnej liczby przejazdów w rysunku graf pełny dwustronny . Nazwa problemu pochodzi od nazwiska Pála Turána , który sformułował go, będąc zmuszonym do pracy w cegielni podczas II wojny światowej.
Metoda rysunkowa znaleziona przez Kazimierza Zarankiewicza została przypuszczona, aby dać poprawną odpowiedź dla każdego pełnego wykresu dwudzielnego, a stwierdzenie, że to prawda, stało się znane jako hipoteza o liczbie skrzyżowania Zarankiewicza . Przypuszczenie pozostaje otwarte, rozwiązano tylko niektóre szczególne przypadki.
Pochodzenie i receptura
Podczas II wojny światowej węgierski matematyk Pál Turán został zmuszony do pracy w cegielni, przepychając wagonami cegły z pieców do składowisk. Fabryka miała tory z każdego pieca do każdego miejsca składowania, a wagony trudniej było pchać w miejscach, w których tory się krzyżowały. Turán zainspirował się tą sytuacją i zapytał, jak można przeprojektować fabrykę, aby zminimalizować liczbę skrzyżowań między tymi torami.
Matematycznie, problem ten może być sformalizowane jako prosząc o rysunku wykres z kompletną graf dwudzielny , którego wierzchołki stanowią piece i składowisk, i których krawędzie reprezentują utwory z każdego pieca do każdego składowiska. Wykres należy narysować w płaszczyźnie, w której każdy wierzchołek jest punktem, każda krawędź jest krzywą łączącą jego dwa punkty końcowe, a żaden wierzchołek nie powinien być umieszczony na krawędzi, do której nie jest przypadkowy. Przecięcie jest liczone zawsze, gdy dwie rozłączne krawędzie na wykresie mają niepuste przecięcie na płaszczyźnie. Powstaje zatem pytanie, jaka jest minimalna liczba skrzyżowań na takim rysunku?
Sformułowanie tego problemu przez Turána jest często uznawane za jedno z pierwszych badań dotyczących krzyżujących się liczb grafów . (Inne niezależne sformułowanie tej samej koncepcji pojawiło się w socjologii, w metodach rysowania socjogramów , a znacznie starsza układanka, problem trzech mediów , może być postrzegana jako szczególny przypadek problemu cegielni z trzema piecami i trzema magazynami). Od tego czasu liczby przecinające się zyskały na znaczeniu, jako główny przedmiot badań w rysowaniu wykresów oraz jako ważne narzędzie w projektowaniu VLSI i geometrii dyskretnej .
Górna granica
Zarówno Zarankiewicz, jak i Kazimierz Urbanik widzieli, jak Turán mówił o problemie cegielni podczas różnych rozmów w Polsce w 1952 roku i niezależnie opublikowali próby rozwiązania tego problemu, z równoważnymi wzorami na liczbę przejazdów. Jak obaj wykazali, zawsze można narysować pełny wykres dwudzielny K m, n (graf z m wierzchołkami po jednej stronie, n wierzchołkami po drugiej stronie i mn krawędziami łączącymi oba boki) z pewną liczbą skrzyżowań równy
Konstrukcja jest prosta: umieść m wierzchołków na osi x płaszczyzny, unikając początku , z równą lub prawie równą liczbą punktów po lewej i prawej stronie osi y . Podobnie umieść n wierzchołków na osi y płaszczyzny, unikając początku, z równą lub prawie równą liczbą punktów powyżej i poniżej osi x . Następnie połącz każdy punkt na osi x prostym odcinkiem z każdym punktem na osi y .
Jednak ich dowody na to, że ten wzór jest optymalny, to znaczy, że nie może być rysunków z mniejszą liczbą skrzyżowań, były błędne. Luka została odkryta dopiero jedenaście lat po publikacji, prawie jednocześnie przez Gerharda Ringela i Paula Kainena . Niemniej jednak przypuszcza się, że formuła Zarankiewicza i Urbanika jest optymalna. Stało się to znane jako domniemanie liczby skrzyżowania Zarankiewicza. Chociaż wiadomo, że pewne szczególne przypadki są prawdziwe, sprawa ogólna pozostaje otwarta.
Dolne granice
Ponieważ K m, n i K n, m są izomorficzne, wystarczy rozważyć przypadek, w którym m ≤ n . Dodatkowo dla m ≤ 2 konstrukcja Zarankiewicza nie daje żadnych skrzyżowań, których oczywiście nie da się pokonać. Zatem jedynymi nietrywialnymi przypadkami są te, w których oba m i n są ≥ 3 .
Podjęta przez Zarankiewicza próba udowodnienia hipotezy, choć nieważna dla ogólnego przypadku K m , n , działa dla przypadku m = 3 . Od tego czasu została rozszerzona na inne małe wartości m , a hipoteza Zarankiewicza jest znana jako prawdziwa dla pełnych dwudzielnych grafów K m, n przy m ≤ 6 . Przypuszczenie to jest również prawdziwe dla K 7,7 , K 7,8 i K 7,9 . Jeśli istnieje kontrprzykład, to jest graf K m, n wymagający mniej skrzyżowań niż granica Zarankiewicza, to w najmniejszym kontrprzykładzie zarówno m, jak i n muszą być nieparzyste.
Dla każdego ustalonego wyboru m , prawdziwość przypuszczenia dla wszystkich K m, n może być zweryfikowana przez testowanie tylko skończonej liczby wyborów n . Mówiąc bardziej ogólnie, udowodniono, że każdy pełny wykres dwudzielny wymaga pewnej liczby przecięć, czyli (dla grafów dostatecznie dużych) co najmniej 83% liczby podanej przez granicę Zarankiewicza. Zamknięcie luki między tą dolną a górną granicą pozostaje otwartym problemem.
Liczby przecinające się prostoliniowo
Jeśli krawędzie mają być narysowane jako odcinki linii prostych, a nie jako dowolne krzywe, to niektóre wykresy wymagają więcej skrzyżowań niż w przypadku rysowania z zakrzywionymi krawędziami. Jednak górną granicę ustaloną przez Zarankiewicza dla przecinających się liczb pełnych grafów dwudzielnych można osiągnąć używając tylko prostych krawędzi. Dlatego też, jeśli przypuszczenie Zarankiewicza jest poprawne, to pełne wykresy dwudzielne mają prostoliniowe liczby przecinające równe ich liczbom przecinającym.