Zarankevitšin ongelma

Zarankevich -  ongelma on graafiteorian ongelma , joka liittyy leikkauspisteiden minimimäärän löytämiseen kuvattaessa täydellistä kaksiosaista graafia tasossa . [yksi]

Tunnetaan myös Turanin tiilitehtaan ongelmana unkarilaisen matemaatikon Pal Turanin mukaan  , joka muotoili tämän ongelman työskennellessään tiilitehtaassa toisen maailmansodan aikana .

Puolalainen matemaatikko Kazimierz Zarankiewicz ( puolalainen Kazimierz Zarankiewicz ) arveli, että jollakin yksinkertaisella graafikuvalla on minimimäärä leikkauspisteitä, mutta sen optimaalisuus jää kuitenkin erityistapauksia lukuun ottamatta todistamatta [2] .

Alkuperä ja sanamuoto

Toisen maailmansodan aikana unkarilainen matemaatikko Pál Turán joutui työskentelemään tiilitehtaassa, jossa hän kuljetti kärryjä tiiliä uuneista varastoihin. Tehtaalla rautatiekiskot laitettiin minkä tahansa uunin ja varaston väliin , ja vaunua oli vaikeampi työntää näiden raiteiden risteyskohdassa. Tämä inspiroi Turania kysymään, kuinka polut voitaisiin järjestää uudelleen risteysten määrän minimoimiseksi. [yksi]

Matematiikan näkökulmasta tämä on tehtävä graafin esittämisestä tasossa : uunit ja varastot määrittelevät graafin kärjet ja rautatiekiskot sen reunat. Koska kunkin uunin ja varaston välillä on täsmälleen yksi polku, tällainen kaavio on täydellinen kaksiosainen . Jos on p uuneja ja s varastoja, niin tällaista kuvaajaa merkitään . Turanin tehtävänä on järjestää graafin kärjet ja reunat tasossa siten, että yksikään kärki ei ole reunalla, jonka loppu ei ole, ja samalla graafin reunoilla on minimimäärä leikkauspisteitä. muut kuin kärjet. Tässä tapauksessa reunojen ei tarvitse olla suoraviivaisia , vaikka ratkaisussa, jonka oletetaan olevan minimaalinen, näin on. [2]

Turanin ongelmaa pidetään yhtenä ensimmäisistä ongelmista graafien leikkauspisteiden minimimäärässä . [3] Erikoistapaus on klassinen matemaattinen ongelma " Talot ja kaivot ", jossa uunien ja varastojen roolia ovat talot ja kaivot, kukin kolme kappaletta.

Ratkaisuyritykset

Zarankiewicz ja Kazimierz Urbanik ( puola: Kazimierz Urbanik ) osallistuivat Turanin luennoille Puolassa vuonna 1952 [4] ja julkaisivat itsenäisesti yrityksiä ratkaista ongelma. [5]

Molemmissa tapauksissa he ehdottivat täydellisen kaksiosaisen graafin piirtämistä seuraavasti (katso kuva artikkelin alussa): piirrä yhden värin kärjet ("uunit") pystyakselia pitkin, toisen väriset pisteet ("varastot") vaaka-akselia pitkin ja akselien leikkauspiste valitaan siten, että kummallakin puolella on yhtä paljon (jos on tietyn värisiä parillisia kärkipisteitä ) tai melkein yhtä paljon (jos ne ovat parittomia). Tämän seurauksena molemmat saivat seuraavan määrän leikkauspisteitä kaavion reunoilla:

Tämä esimerkki antaa ylärajan leikkauspisteiden lukumäärälle, mutta molemmat todisteet sen minimaalisuudesta, alarajan antamisesta, osoittautuivat virheellisiksi: Gerhard Ringel ja Paul Kainen kumosivat ne  lähes samanaikaisesti, vuonna 1965 [6] .

Vaikka yleisessä tapauksessa kysymys minimaalisuudesta on edelleen olettamus, erikoistapaukset on onnistuneesti todistettu: Zarankevich itse ja myöhemmin . [7] Koska minkä tahansa kahden p, s:n minimaalisuuden todistaminen vaatii äärellisen määrän tarkistuksia, se suoritettiin riittävän pienelle p, s:lle. [8] Todettiin myös, että risteysten vähimmäismäärä on vähintään 83 % Zarankiewiczin arvioista. [9]

Muistiinpanot

  1. ↑ 1 2 Turan, P. (1977), A note of welcome , Journal of Graph Theory osa 1: 7–9 , doi 10.1002/jgt.3190010105  .
  2. ↑ 1 2 Pach, Janos & Sharir, Micha (2009), 5.1 Crossings – the Brick Factory Problem, Combinatorial Geometry and Its Algorithmic Applications: The Alcala Lectures , voi. 152, Mathematical Surveys and Monographs, American Mathematical Society , s. 126-127  .
  3. ↑ Foulds, LR (1992), Graph Theory Applications , Universitex, Springer, s. 71, ISBN 9781461209331 , < https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71 > Arkistoitu 12. heinäkuuta 2022 Wayback Machinessa . 
  4. ↑ Beineke, Lowell & Wilson, Robin (2010), Tiilitehtaan ongelman varhainen historia , The Mathematical Intelligencer osa 32 (2): 41–48 , DOI 10.1007/s00283-009-9120-4  .
  5. ↑ Urbanik, K. (1955), Solution du probleme pose par P. Turan, Colloq. Matematiikka. T. 3: 200-201  . Kuten Szekely, Laszlo A. (2001), Zarankiewicz risteävien lukujen arvelu , julkaisussa Hazewinkel, Michiel, Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4 
  6. ↑ Guy, Richard K. (1969), Zarankiewiczin lauseen heikkeneminen ja lasku, Todistustekniikat graafiteoriassa (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) , Academic Press, New York, s. . 63-69  .
  7. ↑ Kleitman, Daniel J. (1970), The crossing number of K 5, n , Journal of Combinatorial Theory voi. 9: 315–323 , DOI 10.1016/s0021-9800(70)80087-4  .
  8. ↑ Christian, Robin; Richter, R. Bruce & Salazar, Gelasio (2013), Zarankiewiczin olettamus on äärellinen kullekin kiinteälle m :lle , Journal of Combinatorial Theory , Series B osa 103 (2): 237–247 , DOI 10.1016/j.jctb.2012111.  .
  9. ↑ de Klerk, E.; Maharry, J.; Pasechnik, DV & Richter, RB (2006), Parannetut rajat K m,n:n ja Kn : n risteysluvuille , SIAM Journal on Discrete Mathematics , osa 20 (1): 189–202 , DOI 10.1137/S0895480101442  .

Linkit