Eddler
Kurser Alla kurser Min kurs Min sida Min sida Provbank Mina prov Läromedel Blogg Hjälp & Guider Om oss Kontakt Nationella prov Gamla högskoleprov Screening Priser läromedel
Sök Mitt konto Logga ut Elev/lärare
-registrering
Logga in Köp Premium Köp Premium Prova gratis
Genom att använda den här sidan godkänner du våra användarvillkor, vår integritetspolicy och att vi använder cookies.
EXEMPEL I VIDEON
Lägg till som läxa
Lägg till som stjärnmärkt
  Lektionsrapport Repetera   Hjälp

Frågor hjälpmarkerade!

Alla markeringar försvinner.

Ta bort markeringar Avbryt
Kopiera länk Facebook X (Twitter) Repetera Rapportera Ändra status
KURSER  / 
Matematik 5
 /   Grafteori

Grafteori och problemlösning

Endast Premium- användare kan rösta.
  • Författare:Simon Rybrand
    Rapportera fel Redigera lektion Redigera text Redigera övning Redigera video Skapa thumbnails
    Så hjälper Eddler dig:
    Videor som är lätta att förstå Övningar & prov med förklaringar
    Allt du behöver för att klara av provet
    Så hjälper Eddler dig:
    Videor som är lätta att förstå Övningar & prov med förklaringar
    Allt du behöver för att klara av provet
    Din skolas prenumeration har gått ut!
    Påminn din lärare om att förnya eller fortsätt plugga med Eddler på egen hand.
    Så funkar det för:
    Elever/Studenter Lärare Föräldrar
    Din skolas prenumeration har gått ut!
    Förnya er prenumeration. Kontakta oss på: info@eddler.se

    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

    Viktor Malmkvist

    Precis samma tanke här.

    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.

    ██████████████████████████
    ████████████████████████████████████████████████████

    Vi hjälper dig att repetera om du behöver

    {[{ prereqFeedback.title }]} {[{ prereqFeedback.body }]}
    RESULTAT
    Du har det som behövs
    Är du säker?
    REPETERAR
    Du ser första minuten av genomgången. Prova gratis i 14 dagar Se hela med Eddler Premium
    Få tillgång till hela Eddler
    • Alla videor i alla kurser
    • Övningar med förklaringar på rätt nivå
    • Allt inför NP och HP
    • Gjort av legitimerade mattelärare
    Prova gratis i 14 dagar Köp Premium
    Sedan 99 kr/mån. Ingen bindningstid.
    Din skolas prenumeration har gått ut

    Påminn din lärare om att förnya, eller fortsätt plugga med Eddler på egen hand.

    Köp Premium
    Sedan 99 kr/mån. Ingen bindningstid.
    Er prenumeration har gått ut

    Kontakta oss på info@eddler.se för att förnya.

    Repetera mer i lektionen

    e-uppgifter (2)

    • 1. Premium

      Redigera uppgift Rapportera fel Ändra till korrekt
      (1/0/0)
      E C A
      B 1
      P
      PL
      M
      R
      K
      EXIT NP INGÅR EJ Uppgift från prov

      Går det att rita en Eulerkrets i grafen?

      Bedöm ditt svarBedömningsanvisningar/Manuell rättning
      Jämför med rätt svar ovan och kryssa i det du har fått med.
      Klicka i rutorna och bedöm ditt svar.
      • Rättad
      • +1
      • Rättad
      Dela med lärare
      Rättar...
    • 2. Premium

      Redigera uppgift Rapportera fel Ändra till korrekt
      (2/0/0)
      E C A
      B
      P
      PL 2
      M
      R
      K
      EXIT NP INGÅR EJ Uppgift från prov

      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öm ditt svarBedömningsanvisningar/Manuell rättning
      Jämför med rätt svar ovan och kryssa i det du har fått med.
      Klicka i rutorna och bedöm ditt svar.
      • Rättad
      • +1
      • Rättad
      Dela med lärare
      Rättar...
    Så hjälper Eddler dig:
    Videor som är lätta att förstå Övningar & prov med förklaringar
    Allt du behöver för att klara av provet
    Så hjälper Eddler dig:
    Videor som är lätta att förstå Övningar & prov med förklaringar
    Allt du behöver för att klara av provet
    Din skolas prenumeration har gått ut!
    Påminn din lärare om att förnya eller fortsätt plugga med Eddler på egen hand.
    Så funkar det för:
    Elever/Studenter Lärare Föräldrar
    Din skolas prenumeration har gått ut!
    Förnya er prenumeration. Kontakta oss på: info@eddler.se