Huse og brønde

Problemet med tre huse og tre brønde er et klassisk matematisk puslespil : læg ikke-krydsende stier fra hver af de tre brønde til hvert af de tre huse . Formuleringen af problemet tilskrives Euler . I moderne litteratur findes det nogle gange i følgende form: er det muligt at lægge rør (muffer) fra tre kilder - elforsyning, gasforsyning og vandforsyning (" vand, gas, elektricitet ") til hvert af de tre huse uden krydsning på flyet .

Puslespillet har ingen løsning: topologisk grafteori, som studerer indlejring af grafer i overflader , giver et negativt svar på spørgsmålet om muligheden for at afbilde den tilsvarende graf på et plan uden at krydse kanter.

En komplet todelt graf, der repræsenterer problemet, kaldes " huse og brønde ", " brugsgraf " , Thomsen graf [ 1] . $K_{{3,3}}$

Formalisering

Med hensyn til grafteori reducerer problemet sig til spørgsmålet om planheden af en komplet todelt graf . Denne graf svarer til en cirkulerende graf . Kazimir Kuratovsky i 1930 beviste, at han er ikke-plan, og derfor har problemet ingen løsning [2] . $K_{{3,3}}$ $Ci_6(1,3)$ $K_{{3,3}}$

Et af beviserne på umuligheden af at finde en flad indlejring bruger et casestudie, ved hjælp af Jordans sætning , overvejer forskellige muligheder for placeringen af toppunkter med hensyn til cyklusser af længde 4, og viser, at de er uforenelige med planaritetskravet [3] . Det kan også vises, at for enhver todelt plan graf uden broer med toppunkter og kanter , hvis vi kombinerer Eulers formel (her antallet af flader på en plan graf) med den observation, at antallet af flader ikke overstiger halvdelen af antallet af flader. kanter (da ethvert ansigt har mindst fire kanter, og hver kant tilhører præcis to flader). Desuden i grafen : og , som overtræder uligheden, så denne graf kan ikke være plan. $K_{{3,3}}$ $n$ $m$ $m \leqslant 2n - 4$ $n - m + f = 2$ $f$ $K_{{3,3}}$ $m = 9$ $2n - 4 = 8$

Problemets uløselighed følger direkte af hver af følgende vigtige sætninger om plane grafer: Kuratowskis sætning , ifølge hvilken plane grafer er præcis de grafer, der ikke indeholder subgrafer, der er homøomorfe i forhold til hele grafen , og Wagners sætning om, at plane grafer er i præcision , de grafer, der ikke indeholder enten , eller som underordnede , indeholder dette resultat. $K_{{3,3}}$ $K_{5}$ $K_{{3,3}}$ $K_{5}$

Egenskaber K 3,3

Grafen er, som alle andre komplette todelte grafer , godt dækket , hvilket betyder, at alle de største uafhængige sæt i denne graf er af samme størrelse. I denne graf er der kun to største uafhængige sæt - det er delene af den todelte graf, og det er tydeligt, at de er ens. er en af de syv 3-regulære 3-forbundne godt dækkede grafer [4] . $K_{{3,3}}$ $K_{{3,3}}$

Grafen er lamansk , hvilket betyder, at den danner den minimale strukturelle stivhed , når den er indlejret i et plan (med skæringspunkter). Dette er et eksempel på en minimal Laman-graf, mens en anden ikke-plan graf ikke er minimalt stiv. $K_{{3,3}}$ $K_{5}$

Variationer og generaliseringer

$K_{{3,3}}$ er toroidformet , hvilket betyder, at den kan indlejres i en torus . Et tilsvarende udsagn er, at slægten af en graf er lig med én, hvilket betyder, at den ikke kan indlejres i en overflade med slægten mindre end én. En overflade med slægt et svarer til en torus . $K_{{3,3}}$
- Især puslespillet om huse og brønde har en løsning på krusets overflade (sådanne krus kan endda ses på udsalg).

Zarankiewicz-problemet , også kendt som Pal Turan - teglværksproblemet , stiller et mere generelt spørgsmål - at finde en formel for minimumsantallet af krydsninger i en tegning af en komplet todelt graf , afhængigt af talleneogto dele af grafen. En grafkan tegnes med kun én krydsning, men ikke nul, så dens antal krydsninger er én. Opgaven hænger sammen med, at Turan under krigen arbejdede på en murstensfabrik, og der blev anlagt en smalsporet jernbane fra hver ovn til hvert lager. Det er svært at skubbe vognene langs krydsene, deraf problemet: hvordan man kan gøre krydsene mindre. $K_{{a,b}}$ $-en$ $b$ $K_{{3,3}}$

Noter

↑ W. G. Brown. På grafer, der ikke indeholder en Thomsen-graf // Canadian Mathematical Bulletin. - 1966. - T. 9 . — S. 281–285 . - doi : 10.4153/CMB-1966-036-2 .
↑ Resultatet er en konsekvens af en mere generel kendsgerning etableret af Kuratovsky - Kuratovskys teorem ; Russisksproget litteratur hævder, at beviset for dette faktum først blev fundet af Pontryagin i 1927, men ikke blev offentliggjort i tide.
↑ Richard J. Trudeau. Introduktion til grafteori. - Rettet, forstørret udgivelse .. - New York: Dover Pub., 1993. - s. 68–70. - ISBN 978-0-486-67870-2 .
↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. En karakterisering af godt dækkede kubiske grafer // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . — S. 193–212 .

Huse og brønde

Formalisering

Egenskaber K 3,3

Variationer og generaliseringer

Noter

Links