Ändra språk

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Logga in på Mathigon

eller

Nytt konto     Återställ lösenord     

Grafer och nätverk
Introduktion
Königsbergs broar
Handskakningar och dejting
Plana diagram
Kartläggning
Det resande säljaren problemet
Schemaläggningsproblem
Grafer i vardagen

Dela med sig

Återställ framsteg

Detta tar bort dina framsteg och chattdata för alla kapitel i den här kursen och kan inte ångras!

Ordlista

Välj ett av nyckelorden till vänster ...

Grafer och nätverkKönigsbergs broar

Lästid: ~20 min

Leonhard Euler var en av de första matematikerna som tänkte på grafer och nätverk. Euler blev fascinerad av ett gammalt problem beträffande staden Königsberg nära Östersjön.

Floden Pregel delar upp Königsberg i fyra separata delar som är förbundna med sju broar. Är det möjligt att gå runt staden som korsar alla broar exakt en gång - men inte mer än en gång? (Du kan börja och avsluta var som helst, inte nödvändigtvis på samma plats.)

Försök hitta en giltig rutt genom att rita på dessa kartor:

Map 1

Map 2

Map 3

Map 4

När det gäller Königsberg verkar det vara omöjligt att hitta en giltig rutt, men några av de andra städerna fungerar. Euler lyckades hitta en enkel regel som kan tillämpas på vilken stad som helst utan att behöva prova många möjligheter - med grafteori.

Först måste vi konvertera stadskartorna till diagram med kanter och vertikaler. Varje ö eller landskap representeras av och varje bro som förbinder två regioner representeras av en motsvarande .

Nu har problemet med att "turnera en stad medan du korsar varje bro exakt en gång" blivit ett problem med "ritning av en graf med ett kontinuerligt slag medan du spårar varje kant exakt en gång".

Ta fram några olika grafer på papper och försök sedan ta reda på vilka som kan ritas med ett enda, kontinuerligt slag.

Precis som för stadskartan förut hittar vi att vissa grafer är möjliga medan andra inte är det. För att hjälpa oss förstå varför, låt oss märka varje toppunkt med dess grad . Då kan vi färga topparna på olika sätt och försöka avslöja ett mönster:

Value
Size
Prime Numbers
Even and Odd

These graphs are possible:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

These graphs are not possible:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

Jämförs dessa siffror med grafer som är möjliga och de som inte är möjliga verkar det som om ett diagram kan ritas om det inte . Detta tillstånd kan förklaras om vi bara tittar på ett enda toppunkt i grafen:

Here you can see a single, magnified vertex in a graph.
If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.
Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.
And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.
Notice that, either way, there always is an even number of edges meeting at the vertex.
The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

Om du bläddrar tillbaka till kartan över Königsberg, kommer du att upptäcka att det finns mer än två öar med ett udda antal broar. Därför är en rutt som korsar varje bro exakt en gång verkligen omöjlig - och det är vad Leonard Euler upptäckte.

Eulers upptäckt kanske inte verkar särskilt användbar i verkligheten, men diagram är grunden till många andra geografiska problem, till exempel att hitta vägbeskrivningar mellan två platser. Vi kommer att upptäcka fler av dessa applikationer senare.

Archie