Grafteori och problemlösning – Matematikvideo

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
Matematik 5

Grafteori och problemlösning

Video

Video, text & övningsfrågor av: Simon Rybrand

I den här genomgången tar vi ett antal olika problem på området grafteori. I genomgången nämns lite ny teori kring det som kallas för närmaste granne metoden.

Är du ny här? Så här funkar Matematikvideo PREMIUM


  • 500+ pedagogiska videolektioner till hela gymnasiet och högstadiets matte.
  • 3500+ typiska övningsfrågor med tips och fullständiga förklaringar.
  • Heltäckande för din kurs, slipp leta efter videos själv på Youtube.
  • Träning inför nationella prov och högskoleprovets matematik.
PROVA FÖR 9 KR
Prova i 7 dagar för 9 kr, sedan endast 89 kr/mån.
Ingen bindningstid, avsluta prenumerationen när du vill.
1 vote, average: 4,00 out of 51 vote, average: 4,00 out of 51 vote, average: 4,00 out of 51 vote, average: 4,00 out of 51 vote, average: 4,00 out of 5
1
Du måste vara inloggad för att rösta.
Loading...

Övning

2
FRÅGOR

TESTA DIG SJÄLV

Alla övningar har fullständiga förklaringar och pedagogisk feedback som hjälper dig att förstå.
ANTAL FÖRSÖK
0
POÄNG
DINA
0
 
 
  • 1
  • 2
MEDELPOÄNG
ALLA
1

Text

Exempel i videon

  • Karl-Gustaf skall planera sin rutt för att åka och hämta mjölk hos 5 bönder. Han börjar i punkt A och skall även sluta i punkt A. Kanternas vikter beskriver avståndet mellan bönderna i kilometer. Bestäm en så effektiv väg som du kan för Karl-Gustaf.
  • Undersök om det är möjligt att rita en Eulerkrets och/eller en Hamiltoncykel i grafen.
  • Rita ett minimalt uppspännande träd i så att alla hörn är sammanhängande.

Formler och begrepp som används i video och övningar

Hörn

De ”punkter” i grafen som binds ihop på olika vis. Ibland nämns också hörnets grad vilket innebär antalet kanter som går ut/in från varje hörn.

Kant

De ”vägar” som binder ihop hörnen.

Ögla

En kant som börjar och slutar i samma hörn.

Väg

Är inte sluten och går genom kanterna som passeras endast en gång.

Krets

Är sluten och går genom kantrerna som passeras endast en gång.

Stig

En väg som bara passerar hörnen en gång.

Cykel

En stig som är sluten.

Eulerväg

En Eulerväg är en vandring där du på grafen går genom alla kanter en gång. Det är här inte viktigt att du börjar och slutar i samma hörn, dvs vandringen är inte sluten.

Eulerkrets

En Eulerkrets är en vandring som påbörjas och avslutas i samma hörn. Här skall man passera alla kanter exakt en gång för att det skall vara en Eulerkrets.

Hamiltoncykel

I en Hamiltoncykel skall alla hörn passeras och vandringen skall vara sluten.

Träd

Ett träd är en graf som inte innehåller några cykler. Man brukar kalla ett träd för ett uppspännande träd om alla hörn ingår i trädet, dvs de är sammankopplade med kanter.

Närmaste granne metoden

Närmaste granne metoden är ett sätt att hitta en kort väg när ett antal olika sammanhängande hörn skall kopplas ihop. Metoden förutsätter att kanterna har tilldelats vikter. Här väljer man hela tiden dennärmaste grannen tills alla hörn passerats och du är tillbaka i startpunkten.

Viktigt att nämna kring metoden är att den inte behöver hitta den kortaste vägen. Den hittar endast en kort väg, inte nödvändigtvis den som är kortast. Det är mycket svårt att hitta en metod som alltid hittar den kortaste vägen men närmaste granne metoden ger ett sätt att angripa ett liknande problem.

Kommentarer

  1. Fråga nummer 2 får jag inte svaret att stämma. Varför är kanten 7 med? Då skapas det ju en cykel mellan A-C-D.

    Sandra Grantelius
  2. Precis samma tanke här.

    Viktor Malmkvist
    1. Vi korrigerar denna uppgift, 7:an skall inte vara med i lösningen.

      Simon Rybrand

Kommentarer är inaktiverade. Logga in för att felrapportera.

Prova Premium i 7 dagar för 9 kr

Därefter 89 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: