Pārklājošs koks un minimālais aptverošais koks

Šajā apmācībā, izmantojot piemērus un attēlus, jūs uzzināsiet par koku un minimālo aptverošo koku.

Pirms mēs uzzinām par koku aptveršanu, mums ir jāsaprot divi diagrammas: nenovirzīti un savienoti grafiki.

Undirected diagramma ir diagramma, kurā malas nav norādīt jebkurā virzienā (ti. Malas ir divvirzienu).

Nevirzīts grafiks

Savienots diagramma ir diagramma, kurā vienmēr ir ceļš no virsotnes uz jebkuru citu virsotni.

Savienots grafiks

Pārklājošs koks

Spenējošais koks ir nenovirzīta savienota grafa apakšgrāfs, kurā ir ietvertas visas diagrammas virsotnes ar minimālu iespējamo malu skaitu. Ja virsotne ir garām, tad tā nav aptverošs koks.

Malām var būt piešķirti svari, bet var arī nebūt.

Kopējais aptverošo koku ar nvirsotnēm skaits, ko var izveidot no pilnīga grafika, ir vienāds ar .n(n-2)

Ja mums ir n = 4, maksimālais iespējamo aptverošo koku skaits ir vienāds ar . Tādējādi no pilnīga grafika ar 4 virsotnēm var izveidot 16 aptverošus kokus.44-2 = 16

Spanning Tree piemērs

Sapratīsim aptverošo koku ar tālāk sniegtajiem piemēriem:

Ļaujiet sākotnējam grafikam būt:

Normāls grafiks

Daži no iespējamiem aptverošajiem kokiem, kurus var izveidot no iepriekš minētā grafika, ir:

A spanning tree A spanning tree A spanning tree A spanning tree A spanning tree A spanning tree

Minimālais aptverošais koks

Minimālais aptverošais koks ir aptverošs koks, kurā malu svara summa ir pēc iespējas mazāka.

Spanning Tree piemērs

Sapratīsim iepriekš minēto definīciju, izmantojot tālāk sniegto piemēru.

Sākotnējais grafiks ir:

Svērtais grafiks

Iespējamie aptverošie koki no iepriekš minētā grafika ir:

Minimālais aptverošais koks - 1 Minimālais aptverošais koks - 2 Minimālais aptverošais koks - 3 Minimālais aptverošais koks - 4

Minimālais aptverošais koks no iepriekš minētajiem kokiem ir:

Minimālais aptverošais koks

Minimālais diagrammas aptverošais koks tiek atrasts, izmantojot šādus algoritmus:

  1. Prima algoritms
  2. Kruskaļa algoritms

Spanning Tree lietojumprogrammas

  • Datortīkla maršrutēšanas protokols
  • Klasteru analīze
  • Civilā tīkla plānošana

Minimālais aptverošā koka lietojums

  • Lai kartē atrastu ceļus
  • Projektēt tādus tīklus kā telekomunikāciju tīkli, ūdensapgādes tīkli un elektrotīkli.

Interesanti raksti...