Arbori de acoperire

Se numește arbore de acoperire al unui graf neorientat conex, un arbore care conține toate nodurile grafului respectiv. Trecerea de la graf la arbore se face eliminând unele dintre muchiile grafului, astfel încât arborele rezultat să nu conțină circuite. Este evident că, în general, pentru același graf se pot obține mai mulți arbori de acoperire, care diferă prin muchiile care au fost reținute. În figurile 1 și 2 se dau două variante de arbori de acoperire pentru același graf. Muchiile care fac parte din arbore sunt trasate cu roșu, iar cele eliminate sunt trasate cu negru.


- Figura 1 -


- Figura 2 -

S-au obținut astfel arbori liberi. Alegând în fiecare din ei un nod oarecare drept rădăcină și rearanjând celelalte noduri pe niveluri, se obțin arbori obisnuiți.

Dacă graful nu este conex, se poate construi câte un arbore de acoperire pentru fiecare subgraf conex al său.

Conceptul de arbore de acoperire poate fi cu usurință extins și la grafurile orientate.
 

Generarea arborelui de acoperire pentru un graf conex

Generarea arborelui de acoperire se face asemănător cu explorarea grafului. Se pornește de la un vârf al grafului, care se consideră drept rădăcină a arborelui. Se face apoi explorarea în lățime sau în adâncime. Fiecare nod vizitat se pune în arborele de acoperire, ca fiu al nodului prin care este legat direct (în a cărui listă de adiacențe se găsește). La fel ca în cazul explorării grafurilor, la generarea arborelui de acoperire prin explorare în lățime se folosesc ca structuri auxiliare o coadă a vârfurilor de explorat și o mulțime a vârfurilor parcurse, iar in cazul explorării în adâncime coada se înlocuiește printr-o stivă.

În cazul arborilor de acoperire construiți prin explorarea grafului în lățime, calea de la vârful inițial la oricare din celelalte vârfuri se realizează prin parcurgerea unui număr minim de arce. Această proprietate rezultă din însăși tehnica folosită la construirea arborelui. În consecință, arborele de acoperire obținut prin explorare în lățime are cea mai mică înălțime dintre toți arborii de acoperire care pornesc din același vârf al grafului.
 

Generarea arborelui de acoperire prin explorarea grafului în lățime

Generarea arborelui de acoperire cu explorare a grafului în lățime, pornind dintr-un vârf inițial dat  se face astfel:
   - se creează un arbore vid;
   - se creează coada vârfurilor de vizitat și mulțimea vârfurilor parcurse (inițial ambele sunt vide);
   - se pune vârful inițial în mulțime;
   - se pune în coadă un element de forma (varfInitial, null), care conține o referință la vârful inițial și o referință nulă (către "părintele" vârfului inițial);
   - se intră într-un ciclu în care, cât timp coada nu este vidă:
       * se scoate din capul cozii elementul curent (varfCurent, parinte);
       * se ataseaza nodului parinte al arborelui un nou nod, care conține o referință la varfCurent; daca referința la părinte este nulă, varfCurent devine rădăcina arborelui;
       * pentru fiecare vârf adiacent al lui varfCurent, care nu este în mulțime sau în coada, se pune aest varfAdiacent în mulțime și se pune în coada un element de forma (varfAdiacent, varfCurent), în care varfCurent este pe poziția de părinte al lui varfAdiacent.
    Generarea arborelui de acoperire se încheie când coada este vidă.

Ca exemplu, în clasa Graf.java există metoda
  public Arbore arboreAcoperireLatime( Graf graf, String etichetaVarfPornire)
În această metodă se aplică tehnica de generare a arborelui de acoperire prin explorarea grafului în lățime descrisă mai sus. Arborele creat este o instanță a clasei Arbore din fisierul Arbore.java. Clasele Arbore și Graf au fost prezentate anterior. Testarea acestei metode se face în aplicația din fișierul TestGraf1.java,  în care se construiesc mai mulți arbori de acoperire pentru graful orientat din figura 3.


- Figura 3 -

Observatie: La executarea aplicației TestGraf1 trebuie să avem în acelasi director codurile de octeți ale claselor TestGraf1, Graf1, Graf și Arbore.

Generarea arborelui de acoperire prin explorarea grafului în adâncime

Generarea arborelui de acoperire prin explorarea grafului în adâncime, pornind de la un varfInitial dat, se face astfel:
   - se creează mulțimea vârfurilor parcurse și stiva vârfurilor deExplorat; inițial acestea sunt vide;
   - se pune varfInitial în mulțimea vârfurilor parcurse;
   - se creează un arbore care conține ca rădăcină un nodArbore, având ca informație eticheta nodului varfInitial;
   - se pune în stiva vârfurilor deExplorat un element de forma
        (nodArbore, iteratorFii)
unde iteratorFii este un iterator al listei fiilor lui varfInitial.

   - se intră într-un ciclu în care, cât timp stiva nu este vidă:
      * se ia drept elementCurent cel situat în elementul din vârful stivei, fără a-l scoate din stivă;
      * folosind elementCurent.iteratorFii :
          # se caută primul element care conține un varfAdiacent al grafului care nu există în mulțimea vârfurilor parcurse;
          # dacă un astfel de varfAdiacent există, 
             % se creează un nou nodArbore care conține eticheta lui varfAdiacent;
             % se pune varfAdiacent în mulțimea vârfurilor parcurse;
             % se pune nodArbore ca fiu al elementCurent.nodArbore;
          # altfel se scoate din stivă elementCurent.

Generarea arborelui de acoperire se încheie cănd stiva devine vidă.

În locul utilizarii explicite a stivei în modul descris mai sus, generarea arborelui de acoperire pentru explorarea grafului în adancime se poate face utilizand o metodă recursivă. În acest caz, se utilizează explicit numai mulțimea vârfurilor parcurse, iar drept stivă se folosește în mod implicit cea folosită de sistem pentru realizarea recursiei. În clasa Graf1, din fișierul Graf.java, generarea unui astfel de arbore se face prin metoda 
  public Arbore arboreAcoperireAdancime(Graf graf, 
               String etichetaVarfInitial)
care invocă metoda privată recursivă
  private void adaugaNoduriAdancime(Arbore.Nod nodCurent, 
     Iterator iteratorArce, TreeSet parcurse)
În aceasta metodă, nodCurent este nodul de arbore căruia i se adaugă fii, iar iteratorArce este iteratorul arcelor acestui nodCurent, ambele fiind construite înainte de invocarea metodei. Al treilea argument este mulțimea vârfurilor de graf parcurse, care se construiește inainte de a pune în arbore primul nod. Se observă că, imediat ce se găsește în lista de arce a nodului curent un vârf adiacent care nu există în mulțimea vârfurilor parcurse, se pune vârful respectiv în această mulțime și se construieste un nou nod de arbore, care este pus ca fiu al nodului nodCurent. Se creează apoi un iterator al listei fiilor acestui vârf adiacent, invocând pentru el în mod recursiv metoda de punere a fiilor.

Această posibilitate a abordării recursive constituie un avantaj al arborilor de acoperire obtinuți prin explorarea grafului în adâncime. Desavantajul unor astfel de arbori (indiferent că au fost obtinuți recursiv sau folosind stiva în mod explicit) este că au, de regulă, înălțimea mai mare ca cei obtinuți prin explorare în lățime.

Testarea pentru graful din figura 3 este făcută în aplicația din fișierul TestGraf1.java.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați