LOGGA IN

VIA

OBS! Inget publiceras i ditt flöde utan ditt medgivande.

VIA E-POST

E-post/användarnamn

Lösenord

Glömt lösenordet?
eller

Köningsbergs 7 broar och grafteori

2014-02-10 Av Simon Rybrand 0 kommentarer

För några veckor sedan släppte vi kursen till Matte 5 här på MatematikVideo och denna har nu även fått sin första påfyllning av videos på området grafteori. Jag tänkte därför blogga lite om just detta område och då särskilt de broar som till viss del har varit orsaken till att grafteorin har skapats.

Köningsbergs 7 broar och Euler

Det klassiska problem som i mångt och mycket gav upphov till grafteorin kallas för Köningsbergs 7 broar. Det var nämligen så att man i staden Köningsberg (nuvarande Kaliningrad) funderade på följande fråga i staden:

”GÃ¥r det att passera alla broar som binder samman de tvÃ¥ öarna med fastlandet utan att passera varje bro mer än en gÃ¥ng?”

Ingen hade under sin söndagspromenad över broarna hittat ett sätt att genomföra denna typ av vandring genom staden.

När Leonard Euler (Schweizisk matematiker) fick höra talas om problemet bestämde han sig för att försöka undersöka om detta var möjligt. Det han då gjorde var att rita en slags schematisk bild över broarna (det som kom att kallas grafer) för att på detta vis få en bra överblick över hur dessa kopplades samman. Det var inte bara smart ur bekvämlighetsperspektiv (han slapp vandra fram och tillbaka) utan gjorde också att han kunde bevisa att denna promenad faktiskt var omöjlig.

Det han visade var att om det finns två eller flera noder som har ett ojämnt antal kanter så är det omöjligt att genomföra en sådan vandring.

Numera är faktiskt denna vandring möjlig men inte för att Eulers bevis inte stämde. Istället raderade andra världskriget två av broarna och en ny bro byggdes vilket möjliggjorde vandringen.

Eulerväg, Eulerkrets och grafteori

En väg som beskriver en vandring enligt problemet ovan kallas för en Eulerväg. Om vandringen också skall starta och sluta i samma hörn (kallas också för nod) så kallas denna vandring istället för en Eulerkrets. Detta är alltså det man inom grafteorin kallar för en sluten vandring då man startar och slutar i samma hörn.

Detta problem är alltså en av orsakerna till att vi idag jobbar med området grafteori i kursen matematik 5. Man kan tycka att det faktiskt inte verkar vara så stor praktisk nytta med att förstå detta område. Men grafteorin innehåller numera en rad andra tillämpningar som faktiskt kan komma till användning. Exempelvis kan man med grafteori bygga upp metoder för att hitta kortaste vägar mellan orter eller för att minimera kostnader.

Läs mer om matematik och kända problem

 

Gör som 1100+ matematiklärare, fysiklärare och skolpersonal och följ de senaste nyheterna i vårt nyhetsbrev.

Kommentera

Din e-postadress kommer inte publiceras.

*

Prova Premium gratis i 14 dagar

Därefter 99 kr per månad.
Avsluta prenumerationen när du vill.
SKAFFA PREMIUM
Nej tack. Inte just nu.

Vad är detta?
Här hittar du matematiska symboler som kan användas när du ställer frågor på forumet eller kommenterar. När du klickar på symbolen markeras denna, kopiera genom klicka med höger musknapp eller använda kortkommandot Ctrl-C (PC) / cmd-C (Mac)
Förhandsvisning Latex:
Latexkod: