Üleulatuv puu ja minimaalne haarav puu

Selles õpetuses saate näiteid ja jooniseid kasutades teada puude laiendamise puudest ja minimaalsest laiuspuust.

Enne puude laiendamise kohta õppimist peame mõistma kahte graafikut: suunamata graafe ja ühendatud graafikuid.

Graa s on graafik, kus servad ei viita üheski suunas (st. Servad on kahesuunaline).

Suunamata graafik

Sidus graaf on graaf, kus on alati tee tipust muid tipu.

Ühendatud graafik

Üleulatuv puu

Läbiv puu on suunamata ühendatud graafi alamgraaf, mis sisaldab kõiki graafi tippe minimaalse võimaliku servade arvuga. Kui tipp jääb vahele, siis pole see laiuv puu.

Servadele võib olla määratud kaal või mitte.

Tervikgraafikult nloodavate tippudega ulatuvate puude koguarv on võrdne .n(n-2)

Kui meil on n = 4, on maksimaalne võimalike laiuvate puude arv võrdne . Seega saab 4 tipuga tervikgraafikust moodustada 16 laiuvat puud.44-2 = 16

Näide haaravast puust

Mõistame laienevat puud allpool toodud näidetega:

Olgu algne graafik järgmine:

Tavaline graafik

Mõned ülaltoodud graafikult loodavad võimalikud puud:

Üleulatuv puu Üleulatuv puu Üleulatuv puu Üleulatuv puu Üleulatuv puu Üleulatuv puu

Minimaalne laiuspuu

Minimaalne sirutuspuu on haarav puu, milles servade kaalu summa on võimalikult minimaalne.

Näide haaravast puust

Mõistame ülaltoodud määratlust allpool toodud näite abil.

Esialgne graafik on:

Kaalutud graafik

Ülaltoodud graafikult on võimalikud ulatuslikud puud:

Minimaalne laiuspuu - 1 Minimaalne laiuspuu - 2 Minimaalne sirutuspuu - 3 Minimaalne laiuspuu - 4

Minimaalne ülalnimetatud laiuvate puude laiuspuu on:

Minimaalne sirutuspuu

Graafiku minimaalne haarav puu leitakse järgmiste algoritmide abil:

1. Primi algoritm
2. Kruskali algoritm

Puu rakenduste laiendamine

• Arvutivõrgu marsruutimisprotokoll
• Klastri analüüs
• Tsiviilvõrgu planeerimine

Minimaalsed laienduspuu rakendused

• Kaardilt radade leidmiseks
• Projekteerida selliseid võrke nagu telekommunikatsioonivõrgud, veevarustusvõrgud ja elektrivõrgud.