Descriere: Arbori – Notiuni introductive
O categorie importanta de grafuri esteaceea in care muchiile sun niste legaturi de tip parinte-fiu.Un astfel de graf se va numi ARBORE.
Definitie:
Se numeste arbore un graf conex si fara cicluri.
Un arbore cu n varfuri are n-1 muchii.
Proprietati caracteristice unui arbore:
• Exista un nod in care nu intra nici un arc numit radacina arborelui.
• Cu exceptia radacinii, fiecare nod are proprietatea ca in el intra un singur arc.
Acesta leaga nodul respectiv de un alt nod numit numit predecesor sau parinte.
• Dintr-un nod pot iesi unul sau mai multe arce.Fiecare astfel de arc,leaga nodul
Respectivd de un alt nod numit Succesor sau fiu al nodului.
* Nodurile sunt organizate pe nivele primul nivel fiind ocupat de nodul radacina.
Nodurile de pe ultim nivel se caracterizeaza prin faptul ca din ele nu mai iese nici un arc ,si se numesc noduri terminale sau frunze.
• Nodurile pot contine o asa informatie utila ,carte poate fi de orice tip.
Exemplu:
Nodul 1 este radacina arborelui.
Frunzele arborelui sunt 3,8,9.
Algoritmul Prim (scris în 1957 si implementat în 1961 de catre Dijkstra) elimina acest neajuns. Se opereaza cu datele din acelasi graf.
Se porneste initial, ca si în algoritmul lui Kruskal cu “n” vârfuri izolati (adica de la cele “n” varfuri, dar fara a fi trasat între aceste vârfuri vre-o muchie), urmând ca pe parcurs aceste vârfuri sa fie legate între ele de arborele cu lungimea minima.
Fie G=(X,U) un graf neorientat si conex cu n varfuri.
Fiecare muchie se caracterizeaza printr-un numar intreg asociat ,numit cost.
Graful este definit prin matricea costurilor, care fiind foarte asemanatoare cu matricea de adiacenta o va inlocui pe aceasta din urma.Notand matricea costurilor cu A , un element
|
