Taloja ja kaivoja

Kolmen talon ja kolmen kaivon ongelma on klassinen matemaattinen pulma : aseta ei-leikkauspolut kustakin kolmesta kaivosta jokaiseen kolmeen taloon . Ongelman muotoilu johtuu Eulerista . Nykyaikaisessa kirjallisuudessa se löytyy joskus seuraavassa muodossa: onko mahdollista laskea putket (holkit) kolmesta lähteestä - sähköntoimituksesta, kaasuntoimituksesta ja vesihuollosta (" vesi, kaasu, sähkö ") jokaiseen kolmeen taloon ilman ylitys lentokoneessa .

Palapelille ei ole ratkaisua: topologinen graafiteoria, joka tutkii graafien upottamista pintoihin , antaa kielteisen vastauksen kysymykseen mahdollisuudesta kuvata vastaava graafi tasossa ilman, että se ylittää reunoja.

Täydellinen kaksiosainen graafi , joka edustaa ongelmaa, on nimeltään " talot ja kaivot ", " hyötykäyrä " ja Thomsen - graafi [1] . $K_{{3,3}}$

Formalisointi

Graafiteorian kannalta ongelma rajoittuu kysymykseen täydellisen kaksiosaisen graafin tasomaisuudesta . Tämä kaavio vastaa kiertokaaviota . Kazimir Kuratovsky osoitti vuonna 1930 , että hän ei ole tasomainen, joten ongelmalla ei ole ratkaisua [2] . $K_{{3,3}}$ $Ci_6(1,3)$ $K_{{3,3}}$

Eräs todiste tasaisen upotuksen löytämisen mahdottomuudesta käyttää tapaustutkimusta Jordanin lauseella , jossa tarkastellaan erilaisia mahdollisuuksia pisteiden sijaintiin suhteessa 4 pituisiin sykleihin ja osoitetaan, että ne eivät ole yhteensopivia tasomaisuusvaatimuksen kanssa [3] . Voidaan myös osoittaa, että mille tahansa kaksiosaiselle tasomaiselle graafille , jossa ei ole siltoja , joissa on kärki ja reuna reunat (koska millä tahansa pinnalla on vähintään neljä reunaa ja jokainen reuna kuuluu täsmälleen kahdelle pinnalle). Lisäksi kaaviossa : ja , joka rikkoo epäyhtälöä, joten tämä graafi ei voi olla tasomainen. $K_{{3,3}}$ $n$ $m$ $m \leqslant 2n - 4$ $n - m + f = 2$ $f$ $K_{{3,3}}$ $m = 9$ $2n - 4 = 8$

Ongelman ratkaisemattomuus seuraa suoraan jokaisesta seuraavista tärkeästä tasograafia koskevasta lauseesta: Kuratowskin lause , jonka mukaan tasograafit ovat juuri niitä graafia, jotka eivät sisällä täydellisen graafin suhteen homeomorfisia osagraafia , ja Wagnerin lauseesta , että tasograafit ovat tarkkoja. , ne kaaviot, jotka eivät sisällä kumpaakaan tai sivuarvona , sisältävät tämän tuloksen. $K_{{3,3}}$ $K_{5}$ $K_{{3,3}}$ $K_{5}$

Ominaisuudet K 3,3

Graafi on, kuten kaikki muut täydelliset kaksiosaiset graafit , hyvin peitetty , mikä tarkoittaa, että kaikki tämän kaavion suurimmat riippumattomat joukot ovat samankokoisia. Tässä kaaviossa on vain kaksi suurinta riippumatonta joukkoa - nämä ovat kaksiosaisen graafin osia, ja on selvää, että ne ovat yhtä suuret. on yksi seitsemästä 3-säännöllisestä 3-liitetystä hyvin peitetystä graafista [4] . $K_{{3,3}}$ $K_{{3,3}}$

Graafi on lamanilainen , mikä tarkoittaa, että se muodostaa rakenteellisen vähimmäisjäykkyyden , kun se on upotettu tasoon (leikkauksilla). Tämä on esimerkki minimaalisesta Laman-graafista, kun taas toinen ei-tasograafi ei ole minimaalisen jäykkä. $K_{{3,3}}$ $K_{5}$

Muunnelmia ja yleistyksiä

$K_{{3,3}}$ on toroidinen , mikä tarkoittaa, että se voidaan upottaa torukseen . Vastaava väite on, että graafin suku on yhtä suuri kuin yksi, mikä tarkoittaa, että sitä ei voida upottaa pintaan, jossa suku on pienempi kuin yksi. Pinta, jolla on ykkönen, vastaa torusta . $K_{{3,3}}$
- Erityisesti taloja ja kaivoja koskevassa palapelissä on ratkaisu mukin pinnalle (sellaisia mukeja voi jopa nähdä myynnissä).

Zarankiewicz-ongelma , joka tunnetaan myös nimellä Pal Turanin tiilitehdas , kysyy yleisemmän kysymyksen - löytää kaava risteysten vähimmäismäärälle täydellisen kaksiosaisen graafin piirustuksessariippuen numeroistajakaavion kahdesta osasta. Kaaviovoidaan piirtää vain yhdellä risteyksellä, mutta ei nollalla, joten sen risteysten määrä on yksi. Tehtävä liittyy siihen, että Turan työskenteli sodan aikana tiilitehtaalla ja jokaisesta uunista jokaiseen varastoon laskettiin kapearaiteinen rautatie. Kärryjä on vaikea työntää risteyksiä pitkin, mistä johtuu ongelma: kuinka risteyksiä pienennetään. $K_{{a,b}}$ $a$ $b$ $K_{{3,3}}$

Muistiinpanot

↑ W. G. Brown. Kaavioista, jotka eivät sisällä Thomsen-graafia // Canadian Mathematical Bulletin. - 1966. - T. 9 . — S. 281–285 . - doi : 10.4153/CMB-1966-036-2 .
↑ Tulos on seurausta yleisemmästä tosiasiasta, joka on vahvistettu Kuratovskin - Kuratovskin lauseella ; Venäjänkielinen kirjallisuus väittää, että Pontryagin löysi todisteen tästä tosiasiasta ensimmäisen kerran vuonna 1927, mutta sitä ei julkaistu ajoissa.
↑ Richard J. Trudeau. Johdatus graafiteoriaan. - Korjattu, suurennettu julkaisu .. - New York: Dover Pub., 1993. - s. 68–70. - ISBN 978-0-486-67870-2 .
↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. Hyvin peitettyjen kuutiokaavioiden luonnehdinta // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . — S. 193–212 .

Linkit

Weisstein, Eric W. Hyödyllisyyskaavio (englanniksi) Wolfram MathWorld -verkkosivustolla .
Utilities Puzzle // Archimedes-lab.org
3 Utilities Puzzle // leikkaa solmu
Jim Loy. Todiste siitä, että mahdoton palapeli on mahdoton. Arkistoitu alkuperäisestä 20. tammikuuta 2007.