Stier og kretser

Skrevet av Mike Naylor, 1. juni 2015

Artige oppgaver fra grafteori

stierikon

Grafteori og topologi er to områder i matematikken som handler om hvordan punkter i rommet er relatert til hverandre. Mange av ideene fra disse områdene er tilgjengelige for elever - og ikke bare er de temaene morsomme og spennende, men de bygger også romforståelse, logisk resonnement og problemløsningsferdigheter.

En oppgave jeg husker godt fra min barndom er å tegne dette bildet av en konvolutt med en strek – uten å løfte blyanten fra papiret og uten å krysse streken.

 konvolutt

Denne klassiske oppgave har utfordret folk i generasjoner. Du vil ikke kunne tegne den med mindre du velger det rette stedet å starte.

Hvor skal vi starte? Legg merke til at når du møter et kryss, eller "node", bruker du opp to stier fra den noden. Hvis en node har et oddetall antall kanter som kobler seg til det, må det enten være en start- eller sluttpunkt. Når vi teller antall koblinger til hver node i konvolutten finner vi at de tre øverste nodene har 4 sammenhengende kanter hver, de to nederste har 3. Derfor starter og slutter stien på de nederste hjørnene.

Konvolutt analyse

 

Her er flere oppgaver som du og elevene kan prøve. Hvilke har stier som starter og slutter på det samme stedet? Hvilke har stier som starter og slutter på ulike steder? Hvilke har ingen løsning? Du kan tipse elevene om at antall koblinger til krysspunkter har noe å si. Kan elevene finne forholdet?

Sti oppgaver

Broene i Königsburg

Dette er et berømt historisk problem. Gi elevene kopier av kartet som vises her. Fortell dem at det er et kart over broene i Königsburg, Preussen (nå Kaliningrad, Russland). Folk likte å gå på tur og å forsøke å krysse hver bro en gang og bare én gang.

Bruer oppgave

Kan elevene finne en vei som krysser alle broene gang og bare én gang uten å svømme over elva? Oppgaven er umulig, det ble påvist av den berømte matematikeren Leonard Euler på 1700-tallet. Hvis du tenker på hver øy som et veikryss og alle mulige utganger som kanter, kan du endre problemet til en graf slik:

Bruer analyse


Nå er oppgaven lik dem vi har nettopp gjort! Siden det er 4 noder, hver med et odde antall koblinger, er det fire steder som må være enten start- eller sluttpunkt. Dermed er det umulig med en enkelt sti.

Leonard Eulers artikkel på dette problemet startet hele feltet av grafteori! Euler skrev så mange matematiske papirer at de kunne fylle 75 bøker. Han har også en tall oppkalt etter seg, kalt "Eulers tall" som er skrevet som "e" som er omtrent 2,7 og det er et av de viktigste og mest interessante tall i matematikken.

Tips en venn


Postadresse:
Matematikksenteret, NTNU
7491 Trondheim
Besøksadresse:
Gløshaugen,
Realfagbygget, A4
Telefon og epost:
73 55 11 42
ms@matematikksenteret.no
Kjernetid:
09.00-15.00

Personvernerklæring