Författare:
Simon Rybrand
Allt du behöver för att klara av nationella provet
Allt du behöver för att klara av nationella provet
Innehåll
Denna lektion ingår ej för dig som läser med de nya ämnesplanerna i Matematik 5 from HT21. Läser du med GY11 kursplanerna ingår den i Ma 5.
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.
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.
Kommentarer
e-uppgifter (2)
1.
(1/0/0)E C A B 1 P PL M R K Går det att rita en Eulerkrets i grafen?
Bedömningsanvisningar/Manuell rättning- Rättad
Rättar...2.
(2/0/0)E C A B P PL 2 M R K En elektriker skall installera nya elledningar mellan 5 fristående hus. Elektrikern vill förstås minimera materialkostnaden. Varje meter elledning kostar 475 kr. Vilket är den minsta kostnaden för att binda samman husen med elledning? Enligt markritningen ligger husen A-E på följande avstånd (i meter):
Bedömningsanvisningar/Manuell rättning- Rättad
Rättar...
Allt du behöver för att klara av nationella provet
Allt du behöver för att klara av nationella provet
Eddler
POPULÄRA KURSER
FÖRETAGSINFO
Eddler AB
info@eddler.se
Org.nr: 559029-8195
Kungsladugårdsgatan 86
414 76 Göteborg
Viktor Malmkvist
Precis samma tanke här.
Simon Rybrand (Moderator)
Vi korrigerar denna uppgift, 7:an skall inte vara med i lösningen.
Sandra Grantelius
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.
Endast Premium-användare kan kommentera.