Träd – Matematikvideo

LOGGA IN

VIA

OBS! Inget publiceras i ditt flöde utan ditt medgivande.

VIA E-POST

E-post/användarnamn

Lösenord

Glömt lösenordet?
eller
Matematik 5

Träd

Video

Video, text & övningsfrågor av: Simon Rybrand

I den här videon går vi igenom hur träd är uppbyggda som sammanhängande grafer utan cykler. Vi går även igenom vad ett minimalt uppspännande träd är och Kruskals algoritm för att minimera den totala vikten för ett träd i en graf.

Är du ny här? Så här funkar Matematikvideo PREMIUM


  • 500+ pedagogiska videolektioner till hela gymnasiet och högstadiets matte.
  • 3500+ typiska övningsfrågor med tips och fullständiga förklaringar.
  • Heltäckande för din kurs, slipp leta efter videos själv på Youtube.
  • Träning inför nationella prov och högskoleprovets matematik.
PROVA FÖR 9 KR
Prova i 7 dagar för 9 kr, sedan endast 89 kr/mån.
Ingen bindningstid, avsluta prenumerationen när du vill.
3 votes, average: 5,00 out of 53 votes, average: 5,00 out of 53 votes, average: 5,00 out of 53 votes, average: 5,00 out of 53 votes, average: 5,00 out of 5
3
Du måste vara inloggad för att rösta.
Loading...

Övning

2
FRÅGOR

TESTA DIG SJÄLV

Alla övningar har fullständiga förklaringar och pedagogisk feedback som hjälper dig att förstå.
ANTAL FÖRSÖK
0
POÄNG
DINA
0
 
 
  • 1
  • 2
MEDELPOÄNG
ALLA
1

Text

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.

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

Kommentarer

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

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

      Simon Rybrand

Kommentarer är inaktiverade. Logga in för att felrapportera.

Prova Premium i 7 dagar för 9 kr

Därefter 89 kr per månad.
Avsluta prenumerationen när du vill.
SKAFFA PREMIUM
Nej tack. Inte just nu.

Vad är detta?
Här hittar du matematiska symboler som kan användas när du ställer frågor på forumet eller kommenterar. När du klickar på symbolen markeras denna, kopiera genom klicka med höger musknapp eller använda kortkommandot Ctrl-C (PC) / cmd-C (Mac)
Förhandsvisning Latex:
Latexkod: