Unelte utilizator
Bara de navigare
laboratoare:laborator-06
Aceasta e o versiune anterioară a paginii.
Cuprins
Laborator 06: Arbori minimi de acoperire
1. Obiective laborator
- Înțelegerea conceptului de arbore minim de acoperire
- Înțelegerea implementării algoritmilor care determină acest arbore
- Înțelegere aplicațiilor practice în:
- rețele de calculatoare: obținerea unui cost redus la interconectarea mai multor stații (ex: protocolul STP folosit în LAN-uri)
- prelucrarea de imagine: segmentarea cadrelor (ex: folosită în analiza medicală)
- în clustere: determinarea unei topologii de comunicare, în cazul în care topologia nu era una regulată(arbore, inel)
2. Introducere
2.1 Conexitate în grafuri
Componentă conexă
O componentă conexă a unui graf neorientat este un subgraf cu următoarele proprietăţi:
- oricare două noduri din acest subgraf sunt conectate(există un lanţ între ele)
- orice nod din acest subgraf NU este conectat cu niciun nod din afara subgrafului(nodurile din componentă fac muchii numai cu alte noduri din componentă)
Orice graf neorientat are cel puţin o componentă conexă.
Graf neorientat conex
Un graf neorientat este numit conex dacă are o singură componentă conexă.
Putem explora toate nodurile dintr-un graf neorientat conex dintr-o singură parcurgere a grafului(DFS sau BFS).
Graf orientat slab conex
Fie graful neorientat asociat unui graf orientat obţinut prin înlocuirea tuturor arcelor cu muchii. Atunci un graf orientat este slab conex dacă graful neorientat asociat acestuia este conex.
Graf orientat tare conex
Un graf orientat este tare conex dacă există drum între oricare două noduri, atât într-un sens, cât şi în celelalt.
Se pot defini similar componentele slab conexă şi tare conexă.
2.2 Arborele văzut ca graf
2.3 Arbore vs. pădure de acoperire de cost minim
3. Algoritmul lui Kruskal
4. Algoritmul lui Prim
5. Exerciții de laborator
6. Referințe
laboratoare/laborator-06.1490054322.txt.gz · Ultima modificare: 2017/03/21 01:58 de către mihai.iacov
Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
