Hus och brunnar

Problemet med tre hus och tre brunnar är ett klassiskt matematiskt pussel : lägg icke-korsande vägar från var och en av de tre brunnarna till vart och ett av de tre husen . Formuleringen av problemet tillskrivs Euler . I modern litteratur finns det ibland i följande form: är det möjligt att lägga rör (hylsor) från tre källor - elförsörjning, gasförsörjning och vattenförsörjning (" vatten, gas, el ") till vart och ett av de tre husen utan korsning på planet .

Pusslet har ingen lösning: topologisk grafteori, som studerar inbäddningen av grafer i ytor , ger ett negativt svar på frågan om möjligheten att avbilda motsvarande graf på ett plan utan att korsa kanter.

En komplett tvådelad graf som representerar problemet kallas " hus och brunnar ", " bruksgraf " , Thomsen- graf [ 1] . $K_{{3,3}}$

Formalisering

När det gäller grafteorin reduceras problemet till frågan om planheten hos en komplett tvådelad graf . Denna graf motsvarar en cirkulerande graf . Kazimir Kuratovsky bevisade 1930 att han är icke-plan, och därför har problemet ingen lösning [2] . $K_{{3,3}}$ $Ci_6(1,3)$ $K_{{3,3}}$

Ett av bevisen på omöjligheten att hitta en platt inbäddning använder en fallstudie, med hjälp av Jordans teorem , överväger olika möjligheter för placeringen av hörn med avseende på cykler av längd 4, och visar att de är oförenliga med planaritetskravet [3] . Det kan också visas att för varje tvådelad plan graf utan broar med hörn och kanter , om vi kombinerar Eulers formel (här antalet ytor i en plan graf) med observationen att antalet ytor inte överstiger hälften av antalet ytor. kanter (eftersom varje yta har minst fyra kanter och varje kant tillhör exakt två sidor). Dessutom, i grafen : och , som bryter mot ojämlikheten, så denna graf kan inte vara plan. $K_{{3,3}}$ $n$ $m$ $m \leqslant 2n - 4$ $n - m + f = 2$ $f$ $K_{{3,3}}$ $m = 9$ $2n - 4 = 8$

Problemets olösbarhet följer direkt av var och en av följande viktiga satser om plana grafer: Kuratowskis sats , enligt vilken plana grafer är exakt de grafer som inte innehåller subgrafer som är homeomorfa till hela grafen , och Wagners sats om att plana grafer är i precision , de grafer som inte innehåller antingen , eller som underordnade , innehåller detta resultat. $K_{{3,3}}$ $K_{5}$ $K_{{3,3}}$ $K_{5}$

Egenskaper K 3,3

Grafen är, som alla andra kompletta tvådelade grafer , väl täckt , vilket innebär att alla de största oberoende uppsättningarna i denna graf är av samma storlek. I den här grafen finns det bara två största oberoende uppsättningar - det här är delarna av den tvådelade grafen, och det är uppenbart att de är lika. är en av de sju 3-regelbundna 3-anslutna vältäckta graferna [4] . $K_{{3,3}}$ $K_{{3,3}}$

Grafen är lamansk , vilket betyder att den bildar den minsta strukturella styvheten när den är inbäddad i ett plan (med skärningar). Detta är ett exempel på en minimal Laman-graf, medan en annan icke-plan graf inte är minimalt stel. $K_{{3,3}}$ $K_{5}$

Variationer och generaliseringar

$K_{{3,3}}$ är ringformad , vilket betyder att den kan bäddas in i en torus . Ett ekvivalent påstående är att släktet för en graf är lika med ett, vilket innebär att det inte kan bäddas in i en yta med släktet mindre än ett. En yta med släktet ett motsvarar en torus . $K_{{3,3}}$
- I synnerhet pusslet om hus och brunnar har en lösning på ytan av muggen (sådana muggar kan till och med ses på rea).

Zarankiewicz-problemet , även känt som Pal Turan- tegelbruksproblemet , ställer en mer allmän fråga - att hitta en formel för det minsta antalet korsningar i en ritning av en komplett tvådelad graf , beroende på siffrornaochtvå delar av grafen. En grafkan ritas med bara en korsning, men inte noll, så antalet korsningar är en. Uppgiften hänger samman med att Turan under kriget arbetade på en tegelfabrik, och en smalspårig järnväg lades från varje ugn till varje lager. Det är svårt att skjuta vagnarna längs korsningarna, därav problemet: hur man gör korsningarna mindre. $K_{{a,b}}$ $a$ $b$ $K_{{3,3}}$

Anteckningar

↑ W. G. Brown. På grafer som inte innehåller en Thomsen-graf // Canadian Mathematical Bulletin. - 1966. - T. 9 . — S. 281–285 . - doi : 10.4153/CMB-1966-036-2 .
↑ Resultatet är en följd av ett mer allmänt faktum som fastställts av Kuratovsky - Kuratovskys teorem ; Ryskspråkig litteratur hävdar att beviset för detta faktum först hittades av Pontryagin 1927, men att det inte publicerades i tid.
↑ Richard J. Trudeau. Introduktion till grafteori. - Korrigerad, förstorad republicering .. - New York: Dover Pub., 1993. - s. 68–70. - ISBN 978-0-486-67870-2 .
↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. En karaktärisering av vältäckta kubikgrafer // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . — S. 193–212 .

Länkar

Weisstein, Eric W. Utility graph (engelska) på Wolfram MathWorlds webbplats .
The Utilities Puzzle // Archimedes-lab.org
3 Utilities Pussel // klippa knuten
Jim Loy. Bevis på att det omöjliga pusslet är omöjligt. Arkiverad från originalet den 20 januari 2007.