Minimaal opspannende boom

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
De minimaal opspannende boom van een planaire graaf. Elke kant heeft een gewicht, in dit geval is het (vrijwel) gelijk aan de lengte van de kant.

De minimaal opspannende boom van een verbonden, gewogen graaf is de verbonden subgraaf daarvan met het kleinste totale gewicht. Deze kleinste subgraaf is altijd een boom, dat wil zeggen een graaf zonder cycli.

Een algoritme om de minimaal opspannende boom te vinden is het algoritme van Prim:

  • kies een willekeurige knoop (1e bezochte knoop)
  • kies de kant met de laagste waarde verbonden met deze knoop
  • neem de knoop aan de andere zijde van de kant op in je verzameling met bezochte knopen
  • kies de kant met de laagste waarde vanuit je verzameling bezochte knopen naar een knoop die nog niet bezocht werd, en voeg deze kant aan de minimaal opspannende boom toe
  • neem de nieuwe bereikte knoop op in je verzameling
  • ga door tot alle knopen van de graaf bezocht zijn.

Andere algoritmes voor dit probleem zijn Kruskals algoritme, het Reverse-Delete-algoritme en Borůvka's algoritme.

Deze figuur illustreert dat een graaf meerdere minimaal opspannende bomen kan hebben. De twee bomen onder de graaf zijn beide minimaal.

In het algemeen kan een gegeven graaf meerdere minimaal opspannende bomen hebben. Enkel wanneer alle zijden van de graaf een verschillend gewicht hebben is er slechts één, unieke, minimaal opspannende boom.

Stelling van Frieze[bewerken]

In 1985 bewees Alan Frieze dat de verwachte waarde \mathbb{E}(L_n) van het gewicht van de minimaal opspannende boom van een volledige graaf K_n met n knopen, waarin het gewicht van elke kant een onafhankelijk willekeurig gekozen getal uit het eenheidsinterval [0,1] is (volgens een uniforme verdeling), naar een constante waarde neigt wanneer het aantal knopen n naar oneindig gaat. Deze constante is de waarde van de Riemann-zèta-functie van 3:[1][2]

\lim_{n \to \infty} {\mathbb{E}(L_n)} = \zeta(3) = \sum_{k=1}^\infty \frac{1}{k^3} = 1,202 \dots

Dit is een opmerkelijk resultaat aangezien elke opspannende boom van K_n, (n-1) kanten heeft en de verwachte waarde van een willekeurige opspannende boom in dit geval gelijk is aan  (n-1)/2, die naar oneindig gaat als het aantal knopen naar oneindig gaat.

Zie ook[bewerken]

Bronnen, noten en/of referenties
  1. Theorem of the Day: Frieze's Theorem on Expected Minimum Tree Lengths
  2. A. M. Frieze, "On the value of a random minimum spanning tree problem". Discrete Applied Mathematics 1985, vol. 10 nr. 1, blz. 47–56. DOI:10.1016/0166-218X(85)90058-7