Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Minimale spenntrær, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Et delsett av kantene som kobler sammen alle noder uten å lage en sykel. Har alltid kanter.
Et spenntre med minst mulig total kantvekt i en vektet, sammenhengende graf.
En partisjonering av nodene i to mengder. En kant krysser snittet om endene ligger på hver sin side.
En kant vi kan legge til den delvise løsningen og fortsatt utvide til et MST — typisk den letteste over et snitt.
Bygger MST ved å legge til kantene i økende vekt så lenge de ikke lager en sykel.
Bygger MST ved å vokse ett tre fra en startnode og alltid legge til den letteste kanten ut av treet.
En struktur som holder rede på hvilke noder som er koblet sammen, med raske Find- og Union-operasjoner.
En optimalisering i Union-Find der noder pekes direkte til rota under Find, slik at senere oppslag blir raskere.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Et spenntre har V-1 kanter
Et spenntre er sammenhengende og uten sykler. Enhver slik graf over noder har nøyaktig kanter.
Trygg kant (snitt-egenskapen)
Hvis ingen kant i delløsningen krysser et gitt snitt, kan vi trygt legge til den letteste kanten over snittet uten å ødelegge muligheten for et MST.
Kruskal
Sorter kantene etter vekt og legg til hver kant som ikke lager en sykel, sjekket med en disjunkt-mengde-struktur. Sorteringen dominerer kjøretiden.
Prim med binærhaug
Vokser ett tre fra en startnode og velger gjentatt den letteste kanten ut av treet, effektivt med en prioritetskø over nodene.
Disjunkte mengder (Union-Find)
Med rang-union og stikomprimering blir den amortiserte kostnaden per Find/Union nesten konstant — er den inverse Ackermann-funksjonen.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare hvorfor et spenntre over V noder har nøyaktig V-1 kanter og ingen sykler
- 02Bruke snitt-egenskapen til å begrunne at den letteste kanten over et snitt er trygg
- 03Kjøre Kruskal og Prim manuelt på en liten vektet graf og forklare hvilken kant som velges når
- 04Beskrive hvordan en union-find med rang-union og stikomprimering gjør Kruskals sykelsjekk nesten gratis