...
Testa premium Kurser Alla kurser Min sida Provbank Mina prov Min skola Läromedel Förälder Blogg Om oss Kontakt Läxhjälp matemtaik Hjälp & guider
Sök Mitt konto Logga ut Elev/lärar-registrering Logga in
EXEMPEL I VIDEON   Lektionsrapport   Hjälp Kopiera länk Facebook Twitter Repetera Rapportera Ändra status
 ███████████████
    /        ██████████████████████████

Grafteori och problemlösning

Endast Premium- användare kan rösta.
Författare:Simon Rybrand
Rapportera fel Redigera lektion Redigera text Redigera övning

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.

...
Ny här?
Så funkar Premium
  • 600+ videolektioner till gymnasiet och högstadiets matte.
  • 4000+ övningsfrågor med fullständiga förklaringar.
  • Heltäckande för din kursplan. Allt på ett ställe.
  • Träning inför nationella prov och högskoleprovet.
Ingen bindningstid. Avsluta när du vill.

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.

    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.

e-uppgifter (2)

  • 1. Premium

    Rapportera fel
    (1/0/0)
    ECA
    B1
    P
    PL
    M
    R
    K

    Går det att rita en Eulerkrets i grafen?

    Rättar...
  • 2. Premium

    Rapportera fel
    (2/0/0)
    ECA
    B
    P
    PL2
    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):

    Rättar...
...
Upptäck ett bättre
sätt att lära sig
Gör som 100.000+ andra och nå dina mål
med Matematikvideo Premium.
Så funkar det för:
Elever/Studenter Lärare Föräldrar