Författare:Simon Rybrand
Allt du behöver för att klara av nationella provet
Allt du behöver för att klara av nationella provet
Innehåll
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:
- Markera kanten med lägsta vikten.
- Markera näst lägsta, osv.
- 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
e-uppgifter (2)
1.
(1/0/0)E C A B 1 P PL M R K Vad innebär ett minimalt uppspännande träd?
Bedömningsanvisningar/Manuell rättning- Rättad
Rättar...2.
Rättar...
Allt du behöver för att klara av nationella provet
Allt du behöver för att klara av nationella provet
Eddler
POPULÄRA KURSER
FÖRETAGSINFO
Eddler AB
info@eddler.se
Org.nr: 559029-8195
Kungsladugårdsgatan 86
414 76 Göteborg
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.