Königsbergs broar

link: http://www.efgh.com/math/koenigsberg.htm

Philip J. Erdelsky
9 juni 2015

Ett av de klassiska problemen i matematiken är broarna i Königsberg, som löstes av den schweiziska matematikern Leonhard Euler på artonhundratalet. Det är lätt att säga och ganska lätt att lösa.

En flod passerar genom staden Königsberg (nu Kalingrad). I floden finns två öar. Sju broar förbinder öarna och bankerna, som visas på den här gamla kartan:
koenigsbergmap

De två flodkanalerna kommer ihop någonstans utanför höger sida av kartan.

Många försökte gå runt Königsberg, korsa varje bro en gång och en gång, men ingen kunde göra det. Euler visade att uppgiften är omöjlig. Hans bevis kräver endast en del grundläggande kunskaper om aritmetik och egenskaperna hos jämn och udda tal.

Eulers briljanta insikt, om du kan kalla det så, var att räkna antalet broar ENDS anslutna till varje del av landet:

  • 3 på norra stranden
  • 3 på södra stranden
  • 5 på ön i mitten av kartan
  • 3 på ön på höger sida av kartan

En promenad som korsar varje brygga en gång och en gång kallas lämpligen, en Euler promenad (eller en Euler-väg).

Om en Euler-promenad inte börjar eller slutar på ett visst land måste det finnas en ÄVEN antal broar kopplade till den, eftersom en Euler-walker som kommer in i området med en bro måste lämna den av en annan. Om en Euler-promenad börjar eller slutar på en viss mark, måste antalet broar som är anslutna till det vara ODD.

Eftersom var och en av de fyra delarna har ett udda antal broar kopplade till det är det uppenbart att en Euler promenad är omöjlig.

Königsbergs broar är ett exempel på en allmän matematisk struktur som kallas en graf .

En graf består av ett begränsat antal vertikaler (även kallade noder), som motsvarar marken i Königsbergs broar och ett ändligt antal kanter (även kallade linjer) som motsvarar broarna. Vi fortsätter att kalla dem broar. För att undvika svårigheter med obefintliga promenader kräver vi att det måste finnas minst ett toppunkt.

Här är en mer abstrakt representation av Königsberg-grafen:
koenigsberggraph

En graf kan vara mer generell än Königsbergs broar. Till exempel kan en bro ansluta ett vertex till sig själv, och spetsarna behöver inte begränsas till ett enda plan. Ett isolerat vertex, utan anslutande broar, är också möjligt.

Antalet broar som förbinder ett visst vertex kallas sin grad (eller valens).

Eulers argument visade att en Euler-promenad endast är möjlig om antingen (1) alla hörn är i jämn grad, i vilket fall gången börjar och slutar i samma vertex, eller (2) två vertikaler, där gången börjar och slutar, är Av udda grad och alla andra hörn är av jämn grad.

Två egenskaper av Euler promenader är uppenbara. Omvänden av en Euler-promenad är en Euler-promenad, och om en Euler-promenad börjar och slutar vid samma toppunkt, kan det också påbörjas och slutas vid någon annan toppunkt.

Är dessa förutsättningar också tillräckliga? Uppenbarligen inte. Grafen måste också vara ansluten, det vill säga det måste finnas en del väg (inte nödvändigtvis en Euler-väg) från varje vertex till alla andra vertex.

Att bevisa förekomsten av en Euler-promenad för en kopplad graf utan några snedställningar av udda grader eller två snedställningar av udda grader är något svårare, men det innebär ingen avancerad matematik.

Först betrakta en kopplad graf där alla hörn är av jämn grad. Börja gå på ett toppunkt och hålla reda på vilka broar du har korsat. Varje gång du anger ett vertex, lämna det med en bro som du inte har korsat tidigare. Om det inte är startpunkten, så kan du alltid lämna den av en annan om du har gått in i en krossad bro. Och efter att du har lämnat har vertexet fortfarande jämnt antal krossade broar.

Vandringen måste sluta när du återvänder till startpunkten och kan inte hitta en krossad bro för att lämna den.

Om du har lyckats korsa varje bro, är promenad färdig.

Om det fortfarande finns minst en krossad bro, måste gången ökas.

Observera dock att varje toppunkt fortfarande har ett jämnt antal krossade broar.

Eftersom grafen är ansluten finns en väg från startpunkten till ett vertex med en krossad bro. Tänk på det första vertexet i den här vägen med en krossad bro. Det måste vara i promenad. Ring det vertex A.

Börja nu vid toppunkt A och gör en andra promenad, korsa bara broar som du inte redan har korsat, antingen i den här promenad eller den första. Som tidigare slutar gårmen endast när du återvänder till vertex A.

Nu kombinerar de två promenaderna till en enda promenad. Det enklaste sättet att göra detta är att starta första gången vid toppunkt A. När du kommer tillbaka till toppunkt A, gör andra gången.

Om det fortfarande finns minst en krossad bro kan du fortsätta denna process tills alla broar har korsats.

Du kanske frågar vad som händer om grafen bara har en toppunkt och minst en bro. Det är lätt att visa att grafen är ansluten, toppunktet har jämn grad, och det finns en Euler-promenad. En graf med endast en toppunkt och inga broar är inte nödvändigtvis ett undantag, även om begreppen anslutning och Euler-promenader är något vakuösa i detta fall.

Detta är det önskade resultatet för ett anslutet diagram där varje vertex är jämn grad. Betrakta nu ett diagram med två snitt B och C i udda grad. Skapa en lite större graf genom att infoga en bro som förbinder spetsarna B och C. Alla hörn i denna graf är jämngraderade, så det har en Euler-promenad. En del av denna promenad innebär att korsa den nya bron från toppunkt B till vertex C eller vice versa.

Det är uppenbart att denna Euler-promenad, utan den nya korsningen mellan spetsarna B och C, är en Euler-promenad på den ursprungliga grafen.