...
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
 ███████████████
    /        ██████████████████████████

Träd

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

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.

...
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.

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 total 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

    Simon Rybrand (Moderator)

    Hej, Tack för din kommentar, vi ändrar i den uppgiften.


Endast Premium-användare kan kommentera.

e-uppgifter (2)

  • 1. Premium

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

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

    Rättar...
  • 2. Premium

    Rapportera fel
    (1/0/0)
    ECA
    B
    P1
    PL
    M
    R
    K

    Vilket är det minimalt uppspännade trädets totala vikt i grafen?

    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