Tre verktygsproblem - Three utilities problem

"Vatten, gas och el" omdirigeras här. För verktygen, se Public utility .
De tre verktygen problemet. Kan varje hus anslutas till varje verktyg, utan att anslutningslinjer passerar?
På ett plan behövs en korsning

Det klassiska matematiska pusslet som kallas de tre verktygen problem ; problem med de tre stugorna eller ibland kan vatten, gas och el anges på följande sätt:

Antag att det finns tre stugor på ett plan (eller sfär) och var och en måste anslutas till vatten-, gas- och elföretagen. Utan att använda en tredje dimension eller skicka någon av förbindelserna genom ett annat företag eller stuga, finns det ett sätt att göra alla nio förbindelser utan att någon av linjerna korsar varandra?

Problemet är ett abstrakt matematiskt pussel som medför begränsningar som inte skulle existera i en praktisk ingenjörssituation. Det är en del av det matematiska området topologisk grafteori som studerar inbäddning av grafer på ytor . I mer formella grafteoretiska termer frågar problemet om den fullständiga bipartitgrafen K 3,3 är plan . Denna graf kallas ofta verktygsdiagrammet med hänvisning till problemet. det har också kallats Thomsen-grafen .

Historia

En översikt över historien om de tre verktygsproblemen ges av Kullman (1979) . Han säger att de flesta publicerade referenser till problemet karakteriserar det som "mycket gammalt". I den tidigaste publikationen som hittades av Kullman heter Henry Dudeney  ( 1917 ) den "vatten, gas och elektricitet". Dudeney säger dock att problemet är "lika gammalt som kullarna ... mycket äldre än elektrisk belysning eller till och med gas ". Dudeney publicerade också samma pussel tidigare i The Strand Magazine 1913.

En annan tidig version av problemet handlar om att ansluta tre hus till tre brunnar. Det anges på samma sätt som ett annat (och lösbart) pussel som också involverar tre hus och tre fontäner, där alla tre fontänerna och ett hus rör en rektangulär vägg; pusslet innebär återigen att göra förbindelser utan korsning, men bara mellan tre utsedda par hus och brunnar eller fontäner, som i moderna nummerlänkpussel .

Matematiskt kan problemet formuleras i termer av grafritningar av den fullständiga bipartitgrafen K 3,3 . Denna graf uppträder tidigt i Henneberg (1908) . Den har sex hörn, delad i två delmängder av tre hörn, och nio kanter, en för vart och ett av de nio sätten att para ett toppunkt från en delmängd med ett toppunkt från den andra delmängden. Problemet med de tre verktygen är frågan om denna graf är en plan graf .

Lösning

Verktygsdiagrammet, även känt som Thomsen-grafen eller K 3,3
Bevis utan ord : Ett hus raderas tillfälligt. Linjerna som förbinder de återstående husen med verktygen delar upp planet i tre regioner, skuggade gula, röda och blåa. Oavsett vilken region det raderade huset placeras i, är verktyget med samma färg utanför regionen. Den Jordans Kurvsats anger att en linje som förbinder dem måste skära en av de befintliga linjer.

Som det vanligtvis presenteras (på ett platt tvådimensionellt plan) är lösningen på verktygspusslet "nej": det finns inget sätt att göra alla nio anslutningar utan att någon av linjerna korsar varandra. Med andra ord är grafen K 3,3 inte plan. Kazimierz Kuratowski uppgav 1930 att K 3,3 är icke-plan, varifrån det följer att problemet inte har någon lösning. Kullman säger emellertid att "Intressant nog publicerade Kuratowski inte ett detaljerat bevis för att [ K 3,3 är] icke-plan".

Ett bevis på att det är omöjligt att hitta en plan inbäddning av K 3,3 använder en fallanalys som involverar Jordens kurvsats . I denna lösning undersöker man olika möjligheter för placeringen av hörnpunkterna i förhållande till 4-cyklerna i diagrammet och visar att de alla är oförenliga med en plan inbäddning.

Alternativt är det möjligt att visa att alla brygglösa dubbla plana diagram med V- hörn och E- kanter har E ≤ 2 V - 4 genom att kombinera Euler-formeln V - E + F = 2 (där F är antalet ytor på en plan inbäddning ) med observationen att antalet ansikten är högst hälften av antalet kanter (hörnarna runt varje yta måste växla mellan hus och verktyg, så varje yta har minst fyra kanter, och varje kant tillhör exakt två ansikten). I verktygsdiagrammet är E  = 9 och 2 V  - 4 = 8 , vilket bryter mot denna ojämlikhet, så verktygsdiagrammet kan inte vara plant.

Generaliseringar

K 3,3 dras med endast en korsning.
Lösning på de tre verktygen problem på en torus.

Två viktiga karaktäriseringar av plana grafer, Kuratowskis sats om att de plana graferna är exakt de grafer som varken innehåller K 3,3 eller hela diagrammet K 5 som en indelning, och Wagners sats om att de plana graferna är exakt de grafer som varken innehåller K 3 , 3 eller K 5 som minderårig , använd och generalisera icke-planariteten hos K 3,3 .

K 3,3 är ett toroiddiagram , vilket betyder att det kan bäddas in utan korsningar på en torus . När det gäller de tre stugaproblemen betyder detta att problemet kan lösas genom att stansa två hål genom planet (eller sfären) och ansluta dem med ett rör. Detta ändrar ytans topologiska egenskaper och med användning av röret kan de tre stugorna anslutas utan att korsa linjer. Ett motsvarande uttalande är att grafens släkte i verktygsdiagrammet är ett och därför inte kan inbäddas i en yta av släktet mindre än en. En yta av släkt en motsvarar en torus. En toroidal inbäddning av K 3,3 kan erhållas genom att ersätta korsningen med ett rör, såsom beskrivits ovan, i vilket de två hålen där röret ansluter till planet är placerade längs en av korsningskanterna på vardera sidan om korsningen. Ett annat sätt att ändra pusselreglerna är att låta verktygslinjer passera genom stugorna eller verktygen; denna extra frihet gör att pusslet kan lösas.

Pál Turán 's ' tegelfabrik problemet ' frågar mer generellt för en formel för minsta antalet korsningar i en ritning av den komplett bipartit graf K a , b i termer av antalet vertex a och b på de två sidorna av bidelning . Verktygsdiagrammet K 3,3 kan ritas med endast en korsning, men inte med nollkorsningar, så dess korsningsnummer är ett.

Andra grafteoretiska egenskaper

Verktygsdiagrammet K 3,3 är ett cirkulationsdiagram . Det är (3,4) -buret , den minsta triangelfria kubiska grafen . Liksom alla andra kompletta tvåpartsdiagram är det ett väl täckt diagram , vilket innebär att varje maximal oberoende uppsättning har samma storlek. I den här grafen är de enda två maximala oberoende uppsättningarna två sidor av bipartitionen, och uppenbarligen är de lika. K 3,3 är en av endast sju 3-vanliga 3-anslutna väl täckta grafer.

Det är också ett Laman-diagram , vilket betyder att det bildar ett minimalt styvt system när det är inbäddat (med korsningar) i planet. Det är det minsta exemplet på en icke-plan Laman-graf, eftersom den andra minimala icke-plana grafen, K 5 , inte är minimalt stel.

Referenser

externa länkar