Problém továrny na výrobu cihel Turáns - Turáns brick factory problem - Wikipedia

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Lze nakreslit jakýkoli úplný bipartitní graf s menším počtem přechodů, než kolik uvádí Zarankiewicz?
(více nevyřešených úloh z matematiky)
Optimální kresba K.4,7, s 18 kříženími (červené tečky)

V matematika z kreslení grafu, Turánův problém v cihelně žádá o minimální počet přejezdů ve výkresu a kompletní bipartitní graf. Problém je pojmenován po Pál Turán, který jej formuloval, když byl během druhé světové války nucen pracovat v cihelně.[1]

Metoda kreslení nalezená uživatelem Kazimierz Zarankiewicz se předpokládá, že poskytne správnou odpověď pro každý úplný bipartitní graf, a tvrzení, že je to pravda, se stalo známým jako Domankiewiczův křížový dohad. Domněnka zůstává otevřená a vyřešeny jsou pouze některé speciální případy.[2]

Původ a formulace

V době druhá světová válka, Maďarský matematik Pál Turán byl nucen pracovat v cihelně a tlačil vagónový náklad cihel z pecí na skladiště. Továrna měla stopy z každé pece do každého skladiště a vozy se těžší tlačily v místech, kde se stopy navzájem protínaly. Turán se touto situací nechal inspirovat, aby se zeptal, jak by mohla být továrna přepracována, aby se minimalizoval počet přejezdů mezi těmito tratěmi.[1]

Matematicky lze tento problém formalizovat jako požadavek na a kreslení grafu a kompletní bipartitní graf, jehož vrcholy představují pece a úložiště a jejichž hrany představují stopy z každé pece do každého úložiště. Graf by měl být nakreslen v rovině s každým vrcholem jako bodem, každý okraj jako křivka spojující jeho dva koncové body a ne vrchol umístěný na hraně, se kterou není incident. Křížení se počítá vždy, když dvě hrany, které jsou v grafu disjunktní, mají v rovině neprázdný průnik. Otázkou tedy je, jaký je minimální počet přechodů v takovém výkresu?[2][3]

Turánova formulace tohoto problému je často považována za jednu z prvních studií křížení čísel grafů.[4](Další samostatná formulace stejného konceptu se objevila v sociologii, v metodách kreslení sociogramy,[5] a mnohem starší puzzle, problém tří nástrojů, lze považovat za zvláštní případ problému cihelny se třemi pecemi a třemi skladovacími zařízeními.[6]) Křížení čísel od té doby získalo větší význam jako ústřední předmět studia v kreslení grafu[7]a jako důležitý nástroj v VLSI design[8]a diskrétní geometrie.[9]

Horní hranice

Zarankiewicz i Kazimierz Urbanik viděl Turána hovořit o problému cihelny na různých rozhovorech v Polsku v roce 1952,[3]a nezávisle publikovaná pokusná řešení problému s ekvivalentními vzorci pro počet přechodů.[10][11]Jak oba ukázali, je vždy možné nakreslit kompletní bipartitní graf K.m, n (graf s m vrcholy na jedné straně, n vrcholy na druhé straně a mn hrany spojující obě strany) s počtem křížení rovným

Konstrukce je jednoduchá: místo m vrcholy na X- osa letadla, vyhýbání se původ, se stejným nebo téměř stejným počtem bodů nalevo a napravo od y-osice. Podobně, místo n vrcholy na y- osa roviny, vyhýbající se počátku, se stejným nebo téměř stejným počtem bodů nad a pod X-osa. Potom připojte každý bod na X- osa přímým segmentem do každého bodu na y-osa.[3]

Avšak jejich důkazy o tom, že tento vzorec je optimální, to znamená, že nemohou existovat žádné kresby s menším počtem přechodů, byly chybné. Mezera byla objevena až jedenáct let po zveřejnění, téměř současně Gerhard Ringel a Paul Kainen.[12]Předpokládá se však, že Zarankiewiczův a Urbanikův vzorec jsou optimální. Toto začalo být známé jako dohad o čísle Zarankiewicze. Ačkoli je známo, že některé jeho speciální případy jsou pravdivé, obecný případ zůstává otevřený.[2]

Dolní hranice

Od té doby K.m, n a K.n, m jsou izomorfní, stačí zvážit případ, kdy m ≤ n. Kromě toho pro m ≤ 2 Zarankiewiczova konstrukce nedává žádné přechody, což samozřejmě nelze překonat. Jediné netriviální případy jsou tedy případy, pro které m a n jsou oba ≥ 3.

Zarankiewiczův pokus o důkaz domněnky, i když pro obecný případ neplatný K.m,n, pracuje pro případ m = 3Od té doby byla rozšířena na další malé hodnoty mJe známo, že Zarankiewiczova domněnka platí pro celé bipartitní grafy K.m, n s m ≤ 6.[13]Je také známo, že domněnka platí K.7,7, K.7,8, a K.7,9.[14]Pokud existuje protipříklad, tj. Graf K.m, n vyžadující méně přejezdů, než kolik vázal Zarankiewicz, pak v nejmenším protipříkladu obojí m a n musí být liché.[13]

Pro každou pevnou volbu m, pravdivost domněnky pro všechny K.m, n lze ověřit testováním pouze konečného počtu možností n.[15]Obecněji se ukázalo, že každý úplný bipartitní graf vyžaduje řadu křížení, která je (pro dostatečně velké grafy) alespoň 83% počtu uvedeného vázaným Zarankiewiczem. Překlenutí mezery mezi tím dolní mez a horní hranice zůstává otevřeným problémem.[16]

Přímočará čísla křížení

Pokud je potřeba nakreslit hrany jako úsečkové segmenty, spíše než jako libovolné křivky, pak některé grafy potřebují více křížení, než kdyby byly nakresleny se zakřivenými hranami. Horní mez stanovená Zarankiewiczem pro čísla křížení úplných bipartitních grafů však může být dosaženo pouze s použitím přímých hran. Pokud je tedy Zarankiewiczova domněnka správná, pak mají celé bipartitní grafy přímé čísla křížení rovnající se jejich číslům křížení.[17]

Reference

  1. ^ A b Turán, P. (1977), „Uvítání“, Journal of Graph Theory, 1: 7–9, doi:10,1002 / jgt.3190010105.
  2. ^ A b C Pach, János; Sharir, Micha (2009), „5.1 Crossings - the Brick Factory Problem“, Kombinatorická geometrie a její algoritmické aplikace: Alcalá přednáškyMatematické průzkumy a monografie 152, Americká matematická společnost, str. 126–127.
  3. ^ A b C Beineke, Lowell; Wilson, Robin (2010), „Raná historie problému cihelny“, Matematický zpravodaj, 32 (2): 41–48, doi:10.1007 / s00283-009-9120-4, PAN  2657999.
  4. ^ Foulds, L. R. (1992), Teorie grafů Universitext, Springer, str. 71, ISBN  9781461209331.
  5. ^ Bronfenbrenner, Urie (1944), „Grafická prezentace sociometrických údajů“, Sociometrie, 7 (3): 283–289, doi:10.2307/2785096, JSTOR  2785096, Uspořádání subjektů na diagramu, i když je zčásti nahodilé, je určováno převážně metodou pokusů a omylů s cílem minimalizovat počet protínajících se čar.
  6. ^ Bóna, Miklós (2011), Procházka kombinatorikou: Úvod do výčtu a teorie grafů, World Scientific, str. 275–277, ISBN  9789814335232. Bóna představuje hlavolam (ve formě tří domů, které mají být spojeny se třemi studnami) na str. 275 a píše na str. 277, že „je ekvivalentní problému kreslení K.3,3 na rovném povrchu bez křížení ".
  7. ^ Schaefer, Marcus (2014), „Číslo křížení grafů a jeho varianty: průzkum“, Electronic Journal of Combinatorics: # DS21CS1 maint: ref = harv (odkaz)
  8. ^ Leighton, T. (1983), Problémy se složitostí ve VLSI„Foundations of Computing Series, Cambridge, MA: MIT Press
  9. ^ Székely, L. A. (1997), „Křížení čísel a těžké Erdőovy problémy v diskrétní geometrii“, Kombinatorika, pravděpodobnost a výpočet, 6 (3): 353–358, doi:10.1017 / S0963548397002976, PAN  1464571
  10. ^ Zarankiewicz, K. (1954), „K problému P. Turana ohledně grafů“, Fundamenta Mathematicae, 41: 137–145, PAN  0063641.
  11. ^ Urbaník, K. (1955), „Solution du problème posé par P. Turán“, Colloq. Matematika., 3: 200–201. Jak uvádí Székely, László A. (2001) [1994], „Dohad o čísle křížení Zarankiewicze“, Encyclopedia of Mathematics, Stiskněte EMS
  12. ^ Guy, Richard K. (1969), „Úpadek a pád Zarankiewiczovy věty“, Důkazní techniky v teorii grafů (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, str. 63–69, PAN  0253931.
  13. ^ A b Kleitman, Daniel J. (1970), „Crossing number of K.5,n", Journal of Combinatorial Theory, 9: 315–323, doi:10.1016 / s0021-9800 (70) 80087-4, PAN  0280403.
  14. ^ Woodall, D. R. (1993), „Grafy cyklického řádu a domněnka o křížovém čísle Zarankiewicze“, Journal of Graph Theory, 17 (6): 657–671, doi:10,1002 / jgt.3190170602, PAN  1244681.
  15. ^ Christian, Robin; Richter, R. Bruce; Salazar, Gelasio (2013), „Zarankiewiczova domněnka je pro každou fixní konečná m", Journal of Combinatorial Theory, Řada B, 103 (2): 237–247, doi:10.1016 / j.jctb.2012.11.001, PAN  3018068.
  16. ^ de Klerk, E .; Maharry, J .; Pasechnik, D. V .; Richter, R. B .; Salazar, G. (2006), „Vylepšené hranice pro čísla křížení K.m, n a K.n", SIAM Journal on Discrete Mathematics, 20 (1): 189–202, arXiv:matematika / 0404142, doi:10.1137 / S0895480104442741, PAN  2257255.
  17. ^ Kainen, Paul C. (1968), „K problému P. Erdőse“, Journal of Combinatorial Theory, 5: 374–377, doi:10.1016 / s0021-9800 (68) 80013-4, PAN  0231744

externí odkazy