Arbori de acoperire

Se numeste arbore de acoperire al unui graf neorientat conex, un arbore care contine toate nodurile grafului respectiv. Trecerea de la graf la arbore se face eliminand unele dintre muchiile grafului, astfel incat arborele rezultat sa nu contina circuite. Este evident ca, in general, pentru acelasi graf se pot obtine mai multi arbori de acoperire, care difera prin muchiile care au fost retinute. In figurile 1 si 2 se dau doua variante de arbori de acoperire pentru acelasi graf. Muchiile care fac parte din arbore sunt trasate cu rosu, iar cele eliminate sunt trasate cu negru.


- Figura 1 -


- Figura 2 -

S-au obtinut astfel arbori liberi. Alegand in fiecare din ei un nod oarecare drept radacina si rearanjand celelalte noduri pe nivele, se obtin arbori obisnuiti.

Daca graful nu este conex, se poate construi cate un arbore de acoperire pentru fiecare subgraf conex al sau.

Conceptul de arbore de acoperire poate fi cu usurinta extins si la grafurile orientate.
 

Generarea arborelui de acoperire pentru un graf conex

Generarea arborelui de acoperire se face asemanator cu explorarea grafului. Se porneste de la un varf al grafului, care se considera drept radacina a arborelui. Se face apoi explorarea in latime sau in adancime. Fiecare nod vizitat se pune in arborele de acoperire, ca fiu al nodului prin care este legat direct (in a carui lista de adiacente se gaseste). La fel ca in cazul explorarii grafurilor, la generarea arborelui de acoperire prin explorare in latime se folosesc ca structuri auxiliare o coada a varfurilor de explorat si o multime a varfurilor parcurse, iar in cazul explorarii in adancime coada se inlocuieste printr-o stiva.

In cazul arborilor de acoperire construit prin explorarea grafului in latime, calea de la varful initial la oricare din celelalte varfuri se realizeaza prin parcurgerea unui numar minim de arce. Aceasta proprietate rezulta din insasi tehnica folosita la construirea arborelui. In consecinta, arborele de acoperire obtinut prin explorare in latime are cea mai mica inaltime dintre toti arborii de acoperire care pornesc din acelasi varf al grafului.
 

Generarea arborelui de acoperire prin explorarea grafului in latime

Generarea arborelui de acoperire cu explorare a grafului in latime, pornind dintr-un varf initial dat  se face astfel:
   - se creeaza un arbore vid;
   - se creeaza coada varfurilor de vizitat si multimea varfurilor parcurse (initial ambele sunt vide);
   - se pune varful initial in multime;
   - se pune in coada un element (varfInitial, null), care contine o referinta la varful initial si o referinta nula (catre "parintele" varfului initial);
   - se intra intr-un ciclu in care, cat timp coada nu este vida:
       * se scoate din capul cozii elementul curent (varfCurent, parinte);
       * se ataseaza nodului parinte al arborelui un nou nod, care contine o referinta la varfCurent; daca referinta la parinte este nula, varfCurent devine radacina arborelui;
       * pentru fiecare varf adiacent al lui varfCurent, care nu este in multime, se pune aest varfAdiacent in multime si sepune in coada un element de forma (varfAdiacent, varfCurent), in care varfCurent este pe pozitia de parinte al lui varfAdiacent.
    Generarea arborelui de acoperire se incheie cand coada este vida.

Ca exemplu, in clasa Graf.java exista metoda
  public Arbore arboreAcoperireLatime(
          Graf graf, String etichetaVarfPornire)
In aceasta metoda se aplica tehnica de generare a arborelui de acoperire prin explorarea grafului in latime descrisa mai sus. Arborele creat este o instanta a clasei Arbore din fisierul Arbore.java. Clasele Arbore si Graf au fost prezentate anterior. Testarea acestei metode se face in aplicatia din fisierul TestGraf1.java,  in care se construiesc mai multi arbori de acoperire pentru graful orientat din figura 3.


- Figura 3 -

Observatie: La executarea aplicatiei TestGraf1 trebuie sa aveti in acelasi fisier codurile de octeti ale claselor TestGraf1, Graf1, Graf si Arbore.

Generarea arborelui de acoperire prin explorarea grafului in adancime

Generarea arborelui de acoperire prin explorarea grafului in adancime, pornind de la un varfInitial dat, se face astfel:
   - se creeaza multimea varfurilor parcurse si stiva varfurilor deExplorat; initial acestea sunt vide;
   - se pune varfInitial in multimea varfurilor parcurse;
   - se creeaza un arbore care contine ca radacina un nodArbore, avand ca informatie eticheta lui varfInitial;
   - se pune in stiva varfurilor deExplorat un element de forma
        (nodArbore, iteratorFii)
unde iteratorFii este un iterator al listei fiilor lui varfInitial.

   - se intra intr-un ciclu in care, cat timp stiva nu este vida:
      * se ia drept elementCurent cel situat in elementul din varful stivei, fara a-l scoate;
      * pentru elementCurent.iteratorFii :
          # se cauta primul element care contine un varfAdiacent al grafului care nu exista in multimea varfurilor parcurse;
          # daca un astfel de varfAdiacent exista, 
             % se creeaza un nou nodArbore care contine eticheta lui varfAdiacent;
             % se pune varfAdiacent in multimea varfurilor parcurse;
             % se pune nodArbore ca fiu al elementCurent.nodArbore;
          # altfel se scoate din stiva elementCurent.

Generarea arborelui de acoperire se incheie cand stiva devine vida.

In locul utilizarii explicite a stivei, in modul descris mai sus, generarea arborelui de acoperire pentru explorarea grafului in adancime se poate face utilizand o metoda recursiva. In acest caz, se utilizeaza explicit numai multimea varfurilor parcurse, iar drept stiva se foloseste in mod implicit cea folosita de sistem pentru realizarea recursiei. In clasa Graf1, din fisierul Graf.java, generarea unui astfel de arbore se face prin metoda 
  public Arbore arboreAcoperireAdancime(Graf graf, 
               String etichetaVarfInitial)
care invoca metoda privata recursiva
  private void adaugaNoduriAdancime(Arbore.Nod nodCurent, 
     Iterator iteratorArce, TreeSet parcurse)
In aceasta metoda, nodCurent este nodul de arbore caruia i se adauga fii, iar iteratorArce este ineratorul arcelor acestui nodCurent, ambele fiind construite inainte de invocarea metodei. Al treilea argument este multimea varfurilor de graf parcurse, care se construieste inainte de a pune in arbore primul nod. Se observa ca, imediat ce se gaseste in lista de arce a nodului curent un varf adiacent care nu exista in multimea varfurilor parcurse, se pune varful respectiv in aceasta multime si se construieste un nou nod de arbore, care este pus ca fiu al nodului nodCurent. Se creeaza apoi un iterator al listei fiilor acestui varf adiacent invoca pentru el in mod recursiv metoda de punere a fiilor.

Aceasta posibilitate a abordarii recursive constituie un avantaj al arborilor de acoperire obtinuti prin explorarea grafului in adancime. Desavantajul unor astfel de arbori (indiferent ca au fost obtinuti recursiv sau folosind stiva in mod explicit) este ca au, de regula, inaltime mai mare ca cei obtinuti prin explorare in latime.

Testarea pentru graful din figura 3 este facuta in aplicatia din fisierul TestGraf1.java.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati