Arborele care se întinde și Arborele minim care se întinde

În acest tutorial, veți afla despre arborele care se întinde și arborele minim care se întinde cu ajutorul exemplelor și figurilor.

Înainte de a învăța despre întinderea copacilor, trebuie să înțelegem două grafice: grafice nedirecționate și grafice conectate.

Un grafic nedirecționat este un grafic în care marginile nu indică nicio direcție (adică marginile sunt bidirecționale).

Grafic nedirectat

Un grafic conectat este un grafic în care există întotdeauna o cale de la un vârf la orice alt vârf.

Grafic conectat

Arborele care se întinde

Un copac întins este un subgraf al unui grafic conectat nedirecționat, care include toate vârfurile graficului cu un număr minim posibil de margini. Dacă un vârf este ratat, atunci acesta nu este un copac întins.

Marginile pot avea sau nu greutăți atribuite.

Numărul total de copaci care se întind cu nvârfuri care pot fi create dintr-un grafic complet este egal cu .n(n-2)

Dacă avem n = 4, numărul maxim de copaci posibili este egal cu . Astfel, 16 arbori care se întind pot fi formați dintr-un grafic complet cu 4 vârfuri.44-2 = 16

Exemplu de arbore care se întinde

Să înțelegem arborele întins cu exemple de mai jos:

Să fie graficul original:

Grafic normal

Unele dintre posibilele arborii care pot fi create din graficul de mai sus sunt:

Un copac care se întinde Un copac care se întinde Un copac care se întinde Un copac care se întinde Un copac care se întinde Un copac care se întinde

Arborele minim care se întinde

Un copac de întindere minim este un copac de întindere în care suma greutății marginilor este cât mai mică posibil.

Exemplu de arbore care se întinde

Să înțelegem definiția de mai sus cu ajutorul exemplului de mai jos.

Graficul inițial este:

Grafic ponderat

Posibilii arbori care se întind din graficul de mai sus sunt:

Copac minim - 1 Copac minim - 2 Copac minim - 3 Copac minim - 4

Arborele minim de întindere din arborii de mai sus este:

Copac minim care se întinde

Arborele minim de întindere dintr-un grafic se găsește utilizând următorii algoritmi:

1. Algoritmul lui Prim
2. Algoritmul lui Kruskal

Aplicații care se întind pe arbore

• Protocol de rutare computerizată a rețelei
• Analiza grupului
• Planificarea rețelei civile

Aplicații minime pentru copac

• Pentru a găsi căi pe hartă
• Pentru a proiecta rețele precum rețele de telecomunicații, rețele de alimentare cu apă și rețele electrice.