Arbori
1. Arborele liber
Definiție: Se numește arbore liber A un graf neorientat conex și fără cicluri.
Definiție: Se numește arbore liber A un graf neorientat conex și fără cicluri.
Teoremă
Următoarele afirmații sunt echivalente pentru un graf G cu n noduri și m muchii:
(1) G este un arbore.
(2) G este un graf aciclic cu n-1 muchii.
(3) G este un graf conex cu n-1 muchii.
(4) G este un graf fără cicluri maximal.
(5) G este graf conex minimal.
Orice pereche de noduri este legată printr-un lanț și numai unul.
Propoziție. Orice arbore cu n noduri are n-1 muchii.
Următoarele afirmații sunt echivalente pentru un graf G cu n noduri și m muchii:
(1) G este un arbore.
(2) G este un graf aciclic cu n-1 muchii.
(3) G este un graf conex cu n-1 muchii.
(4) G este un graf fără cicluri maximal.
(5) G este graf conex minimal.
Orice pereche de noduri este legată printr-un lanț și numai unul.
Propoziție. Orice arbore cu n noduri are n-1 muchii.
2. Arborele parțial
Teoremă. Un graf G conține un arbore parțial dacă și numai dacă este un graf conex.
Aplicație: Verificați dacă un graf conține un arbore parțial.
Pentru un graf G=(V,U), fiecare arbore H=(V,T) cu T⊆U este numit carcasă sau arbore parțial de acoperire.
Algoritmii de parcurgere permit construirea concomitent a unei carcase.
Algoritm recursiv care formează carcasa pe baza listei muchiilor grafului G
Aplicație: Verificați dacă un graf conține un arbore parțial.
Pentru un graf G=(V,U), fiecare arbore H=(V,T) cu T⊆U este numit carcasă sau arbore parțial de acoperire.
Algoritmii de parcurgere permit construirea concomitent a unei carcase.
Algoritm recursiv care formează carcasa pe baza listei muchiilor grafului G
3. Arbori parțiali de cost minim
Definiție. Costul grafului este suma costurilor muchiilor grafului.
Definiție. Se numește graf parțial de cost minim al unui graf G conex, cu funcția de cost c, un graf parțial conex H care are costul minim.
Teoremă. Graful parțial de cost minim al unui graf conex G, cu funcția de cost c, este un arbore.
Definiție. Costul grafului este suma costurilor muchiilor grafului.
Definiție. Se numește graf parțial de cost minim al unui graf G conex, cu funcția de cost c, un graf parțial conex H care are costul minim.
Teoremă. Graful parțial de cost minim al unui graf conex G, cu funcția de cost c, este un arbore.
4. Algoritmi pentru determinarea arborelui parțial de cost minim.
Algoritmii pentru determinarea arborelui parțial de cost minim folosesc strategia greedy.
Determinarea arborelui parțial de cost minim se poate face prin:
a) Algoritmul lui Kruskal.
b) Algoritmul lui Prim.
Cei doi algoritmi diferă prin :
→ Modul în care se alege subarborele de la care se pornește;
→ Modul în care este găsită muchia sigură.
Determinarea arborelui parțial de cost minim se poate face prin:
a) Algoritmul lui Kruskal.
b) Algoritmul lui Prim.
Cei doi algoritmi diferă prin :
→ Modul în care se alege subarborele de la care se pornește;
→ Modul în care este găsită muchia sigură.
4.1. Algoritmul lui Kruskal
Complexitatea algoritmului lui Kruskal -> O(n)+ O(m2)+ O(nxm)
4.2. Algoritmul lui Prim
Pornește cu subarborele inițial Hinit format dintr-un singur nod,și crește până când va conține toate nodurile grafului.
Nodurile sunt memorate într-o coadă de priorități Q.
Nodurile sunt memorate într-o coadă de priorități Q.
Complexitatea algoritmului lui Prim -> O(n2).
5. Aplicații practice.
1. Ce se întamplă dacă rulăm algoritmul
i) Kruskal,
ii) Prim pe un graf neconex?
Algoritmul Kruskal construiește APM pentru fiecare componentă conexă iar costul rezultat este suma costurilor APM-urilor din fiecare componentă conexă.
1. Ce se întamplă dacă rulăm algoritmul
i) Kruskal,
ii) Prim pe un graf neconex?
Algoritmul Kruskal construiește APM pentru fiecare componentă conexă iar costul rezultat este suma costurilor APM-urilor din fiecare componentă conexă.
Algoritmul lui Prim a găsit APM pentru componenta conexă care conține nodul de pornire și costul acestuia: