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

Träd

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.

    Vad är ett träd

    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.

    Ett träds kanter kan tilldelas vikter. Dessa vikter kan liknas vid avstånd mellan orter eller kostnader för att koppla samman hörnen.

    Det minimalt uppspännande trädet

    Ett minimalt uppspännande träd är det sammanhängande träd i en graf vars totala vikt är så liten som möjligt. Dvs om du söker det minimalt uppspännande trädet i en graf vill du hitta det träd som binder samman alla hörn och där kanternas totala vikt är mindre än alla andra möjliga träd i grafen som också binder samman alla hörn.

    Kruskals algoritm

    En metod att hitta det minimalt uppspännande trädet i en graf är Kruskals algoritm som fungerar på följande vis:

    1. Markera kanten med lägsta vikten.
    2. Markera näst lägsta, osv.
    3. Fortsätt tills alla hörn är sammanhängande.

    Exempel i videon

    • Exempel på ett träd och hur ett träds kanter kan tilldelas vikter.
    • Exempel på minimalt uppspännande träd.
    • Nätverksteknikern José skall binda samman 4 rum med nätverksutrustning. Han har ritat en graf där han bundit samman alla rum och markerat kostnaderna (i tusen kronor) för att binda ihop dessa rum. Hjälp José att koppla ihop rummen till minimal kostnad.

    Kommentarer

    andreas

    det är fel svar på 2:an ty det där är inte ett träd ty har en cykel


    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

      Vad innebär ett minimalt uppspännande träd?

      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
      Liknande uppgifter: Grafteori Matematik 5 Träd
      Dela med lärare
      Rättar...
    • 2. Premium

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

      Vilket är det minimalt uppspännade trädets totala vikt 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
      Liknande uppgifter: Grafteori Matematik 5 Träd
      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