Tarpinis medis ir minimalus apimantis medis

Šioje pamokoje su pavyzdžių ir paveikslų pagalba sužinosite apie pločio medį ir minimalų pločio medį.

Prieš sužinodami apie besidriekiančius medžius, turime suprasti du grafikus: nenukreiptus ir sujungtus.

Bezkierunkowy grafiškai yra diagrama, kurioje kraštai nenukreipkite bet kuria kryptimi (ty. Kraštai yra dvikryptis).

Nenukreiptas grafikas

Prijungtas grafiškai yra diagrama, kurioje visada yra kelias iš viršūnių į bet kurią kitą viršūnių.

Prijungtas grafikas

Platus medis

Tempiantis medis yra nenukreipto sujungto grafiko poskyris, apimantis visas grafiko viršūnes su kuo mažesniu kraštų skaičiumi. Jei viršūnė praleista, tai nėra medis.

Briaunose gali būti priskirti svoriai, jų gali nebūti.

Bendras medžių su nviršūnėmis, kuriuos galima sukurti iš viso grafiko, skaičius yra lygus .n(n-2)

Jei turime n = 4, maksimalus galimų medžių skaičius yra lygus . Taigi iš viso grafiko su 4 viršūnėmis galima suformuoti 16 besidriekiančių medžių.44-2 = 16

Tarpo medžio pavyzdys

Supraskime besiplečiantį medį su toliau pateiktais pavyzdžiais:

Tegul originalus grafikas yra:

Normalus grafikas

Kai kurie galimi medžiai, kuriuos galima sukurti iš aukščiau pateikto grafiko, yra šie:

Tįsiantis medis Tęsiantis medis Tęsiantis medis Tęsiantis medis Tęsiantis medis Tęsiantis medis

Minimalus apimantis medis

Minimalus platus medis yra tai, kad briaunų svorio suma yra kuo mažesnė.

Tarpo medžio pavyzdys

Supraskime aukščiau pateiktą apibrėžimą naudodamiesi toliau pateiktu pavyzdžiu.

Pradinis grafikas yra:

Svertinis grafikas

Iš aukščiau pateikto grafiko galimi medžiai yra:

Minimalus aptempimo medis - 1 Minimalus aptempimo medis - 2 Minimalus aptempimo medis - 3 Minimalus aptempimo medis - 4

Minimalus aptinkamas medis iš aukščiau nurodytų medžių yra:

Mažiausias platus medis

Mažiausias diagramos apimamasis medis randamas naudojant šiuos algoritmus:

1. Primos algoritmas
2. Kruskalio algoritmas

„Spanning Tree“ programos

• Kompiuterinio tinklo maršruto protokolas
• Klasterių analizė
• Civilinio tinklo planavimas

Minimalios taikymo srities medžio programos

• Norėdami rasti kelius žemėlapyje
• Suprojektuoti tokius tinklus kaip telekomunikacijų tinklai, vandens tiekimo tinklai ir elektros tinklai.