Teoria grafurilor - problema arborelui de valoare optima - demonstratie

ARBORI. Problema arborelui de valoare optima

In acest subcapitol grafurile vor fi considerate neorientate.

1. Notiunea de arbore

Un arbore este un graf neorientat, finit, conex si fara cicluri. Grafurile din figura sunt:

Studiul arborilor este justificat de existenta in practica a unui numar mare de probleme care pot fi modelate prin arbori. Dintre acestea amintim:

1. construirea unor retele de aprovizionare cu apa potabila (sau cu energie electrica sau termica etc) a unor puncte de consum, de la un punct central;

2. construirea unor cai de acces intre mai multe puncte izolate;

3. desfasurarea unui joc strategic;

4. luarea deciziilor in mai multe etape (arbori decizionali);

evolutii posibile ale unui sistem pornind de la o stare initiala;

6. construirea unei retele telefonice radiale, a unei retele de relee electrice;

7. legarea intr-o retea a unui numar mare de calculatoare;

8. organigramele intreprinderilor;

9. studiul circuitelor electrice in electrotehnica (grafe de fluenta etc);

10. schemele bloc ale programelor pentru calculatoare etc.

In toate problemele de mai sus se doreste ca, dintre muchiile unui graf neorientat, sa se extraga arborele optim din multimea tuturor arborilor care pot fi extrasi din graful dat.

Deoarece definitia arborelui este dificil de aplicat pentru deciderea faptului ca un graf este arbore sau nu (si in special sunt greu de verificat conexitatea si mai ales existenta ciclurilor) exista mai multe caracterizari posibile ale unui arbore, acestea fiind date de teorema de mai jos:

Teorema. Daca H este un graf neorientat finit, atunci urmatoarele afirmatii sunt echivalente:

1) H este arbore;

2) H nu contine cicluri si, daca se unesc printr-o muchie doua noduri neadiacente, se formeaza un ciclu (si numai unul). Arborele este, deci, pentru o multime de noduri data, graful cu numarul maxim de arce astfel incat sa se pastreze proprietatea ca nu are cicluri);

3) H este conex si daca i se suprima o muchie se creeaza doua componente conexe (arborele este graful conex cu numarul minim de arce);

4) H este conex si are n-1 muchii;

5) H este fara cicluri si are n-1 muchii;

6) Orice pereche de noduri este legata printr-un lant si numai unul.

Demonstratie

1)=>2). intre cele doua noduri adiacente noii muchii introduse exista deja un drum in fostul graf. Acest drum, impreuna cu noul arc va forma evident un ciclu si afirmatia 2) a fost demonstrata.

2)=>3). Pentru oricare doua varfuri neunite printr-o muchie, adaugand muchia dintre cele doua varfuri s-ar crea, conform ipotezei, un ciclu care contine aceasta muchie, deci doua drumuri intre cele doua noduri, din care unul nu contine noua muchie, adica in graful initial exista un drum intre cele doua noduri. Daca nu exista cicluri inseamna ca intre oricare doua noduri exista un singur drum. Pentru doua noduri unite printr-o muchie, aceasta este chiar drumul corespunzator celor doua noduri. Daca suprimam aceasta muchie intre cele doua noduri nu va mai exista nici un drum, formandu-se doua componente conexe.

3)=>4). Demonstratia se face prin inductie dupa n = numarul de noduri ale grafului. Pentru n=2 este evident. Presupunem afirmatia adevarata pentru toate grafurile cu cel mult n noduri. Daca graful are n+1 noduri, prin suprimarea unei muchii se formeaza doua componente conexe fiecare avand cel mult n noduri (n₁ n, n₂ n si n₁ + n₂ = n+1) si deci au n₁ - 1 respectiv n₂ - 1 muchii. In concluzie graful initial a avut (n₁ - 1) + (n₂ - 1) +1 = n₁ + n₂ - 1= (n+1)-1 muchii, ceea ce era de demonstrat.

4)=>5). Daca ar avea un ciclu atunci prin suprimarea unui arc al acestuia ar ramane de asemenea conex. Eliminam acest arc apoi repetam procedeul pentru graful partial ramas si tot asa pana cand nu mai ramane nici un ciclu. In acest moment graful ramas este conex si nu are cicluri deci este arbore si deci are n-1 arce, in contradictie cu faptul ca el avea n-1 arce inainte de a incepe suprimarea arcelor;

5)=>6). Daca intre doua noduri ar exista doua drumuri atunci acestea ar forma la un loc un ciclu. Deci intre 2 noduri este cel mult un drum. Daca intre doua noduri nu ar exista nici un drum ar fi cel putin doua componente conexe in graf, fiecare fiind arbore (pentru ca nu exista cicluri) si deci fiecare ar avea un numar de arce cu 1 mai mic decat numarul de noduri. Facand adunarea, ar rezulta ca in graf sunt strict mai putin de n-1 arce.

6)=>1). Daca H ar avea un ciclu, intre doua noduri ale acestuia ar exista doua lanturi, in contradictie cu ipoteza.

Analiza: Simboluri chimice - element chimic se numeste simbol chimic Referat: Determinarea energiei de activare Arrhenius - reactia tiosulfatul de sodiu cu acidul sulfuric

Presupunem ca avem un graf pentru care am verificat deja daca este conex. Daca nu este atunci acesta, evident, nu are nici un graf partial care sa fie arbore.

Presupunem de asemenea ca fiecarei muchii ii este asociata o valoare reala.

2. Algoritmi pentru gasirea arborelui de valoare optima

Vom da mai jos trei algoritmi pentru determinarea unui graf partial al rafului, care sa fie arbore si pentru care suma valorilor arcelor sale sa fie minima (sau maxima).

Toti algoritmii descrisi in continuare extrag arborele prin colectarea una cate una a muchiilor acestuia.

A. Algoritmul lui Kruskal

Pasul 1. Dintre toate muchiile grafului se alege muchia de valoare minima (maxima). Daca minimul este multiplu se alege la intamplare una din muchiile respective. Deoarece acest 'la intamplare' trebuie cumva tradus in limbajul calculatorului, in cazul implementarii unui program bazat pe acest algoritm, vom perturba din start valorile muchiilor, la k muchii cu aceiasi valoare V adunand respectiv valorile ε, 2ε, , kε, unde e este foarte mic (in orice caz, ke mai mic decat diferenta dintre valoarea acestor arce si valoarea imediat superioara a unui arc), pozitiv.

Pasul 2. Dintre toate muchiile ramase, se alege cea de valoare minima (maxima);

Pasul 3. Dintre toate muchiile ramase, se alege cea de valoare minima (maxima), astfel incat sa nu se formeze cicluri cu cele deja alese;

Pasul 4. Se reia algoritmul de la pasul 3 pana se colecteaza n-1 muchii.

Desi s-a demonstrat ca algoritmul gaseste intotdeauna arborele optim, el are dezavantajul ca este foarte laborios (de fiecare data trebuie calculat minimul unei multimi mari sau foarte mari - exista situatii in practica in care graful are sute de mii de arce) si, in plus, trebuie aplicat un algoritm special ca sa respectam conditia de a nu se forma cicluri, la alegerea unui nou arc.

O metoda posibila este ca, dupa adaugarea fiecarui arc, sa se imparta graful in componente conexe si sa alegem apoi un arc care nu are ambele extremitatile in aceeasi componenta conexa.

De asemenea este clar ca, in cazul existentei arcelor de valori egale, deoarece se alege la intamplare, exista mai multe variante de evolutie a alegerii arcelor. Totusi, cu toate ca pot fi mai multe grafuri la care se poate ajunge prin acest algoritm, ele vor avea toate aceeasi valoare (minima (sau maxima) posibila).

B. Algoritmul lui Sollin

Pasul 1. Pentru fiecare nod se alege muchia adiacenta de valoare minima (maxima).

Pasul 2. Se evidentiaza componentele conexe, existente in graful partial format din arcele alese pana in acest moment.

Pasul 3. Pentru fiecare componenta conexa se alege muchia adiacenta de valoare minima (maxima). Prin muchie adiacenta unei componente conexe intelegem o muchie care are o singura extremitate printre nodurile componentei respective.

Pasul 4. Se reia algoritmul de la pasul 2 pana ramane o singura componenta conexa. Aceasta este arborele optim cautat.

Acest algoritm asigura de asemenea gasirea arborelui optim, necesita mult mai putine calcule (la fiecare alegere se calculeaza minimul doar pentru muchiile adiacente unui singur nod), evita automat formarea ciclurilor, dar, pentru grafuri foarte mari, la un moment dat pot exista atat de multe componente conexe care trebuie memorate succesiv, incat calculul devine greoi sau, pe calculator, depaseste posibilitatile de memorare ale calculatorului.

C. O varianta a algoritmului lui Kruskal

Pasul 1. Dintre toate muchiile grafului se alege cea de valoare minima (maxima);

Pasul 2. Dintre toate muchiile adiacente componentei conexe formata din arcele alese pana in acest moment, se alege cea de valoare minima (maxima);

Pasul 3. Se reia pasul 2 pana se colectioneaza n-1 muchii.

Algoritmul are toate avantajele algoritmului lui Sollin si, in plus, lucreaza cu o singura componenta conexa, fiind mult mai usor de implementat pe calculator si mult mai rapid in executie.

Exemplu Administratia unei localitati montane a hotarat construirea unor linii de teleferic care sa lege orasul de cele 8 puncte turistice importante din jurul acestuia. In urma unui studiu au fost puse in evidenta toate posibilitatile si costurile de conectare a obiectivele turistice intre ele si cu orasul, acestea fiind prezentate in figura.

Se cere gasirea variantei de constructie de cost minim, care sa asigure accesul din oras la oricare din obiectivele turistice.

Rezolvare

Conditia de cost minim implica doua obiective:

1. Sa se construiasca minimul de arce necesare;

2. Sa se construiasca cele mai ieftine legaturi.

Referitor la numarul de arce necesar, facem observatia ca, daca din oras se va putea ajunge la orice obiectiv turistic, atunci se va putea ajunge si de la orice statiune la oricare alta (trecand prin oras), deci trebuie ca arcele alese pentru constructie sa formeze la un loc un graf conex.

In concluzie, cautam un graf partial conex cu un numar minim de arce, adica un arbore. In plus, suma costurilor arcelor sale trebuie sa fie minima. Vom aplica pe rand cei trei algoritmi pentru gasirea acestuia:

A. Kruskal

La primul pas poate fi ales unul din arcele OP3 sau OP7, ele avand valoarea minima 2. Putem alege oricum primul arc dintre cele doua pentru ca la al doilea pas va fi ales celalalt.

La pasul trei poate fi ales unul din arcele OP₅, OP₆ sau P₁P₆ care au valoarea minima 3. Nici in acest caz nu are vre-o importanta ordinea alegerii, deoarece pot fi alese succesiv toate trei fara a se forma nici un ciclu.

Al saselea arc poate fi ales dintre arcele P₄P₅ si P₁P₂, care au valoarea minima 4. Nici in acest caz nu are vre-o importanta ordinea alegerii, deoarece pot fi alese succesiv ambele, fara a se forma nici un ciclu.

Urmatoarea valoare disponibila a unui arc este 5, dar arcul opt nu poate fi ales dintre arcele OP₁, P₆P₇, desi au valoarea minima  Arcul OP₁ nu poate fi ales deoarece s-ar forma ciclul OP₁P₆, iar P₆P₇ ar duce la ciclul OP₆P₇. Urmatoarea valoare minima este 6, pentru arcul P₅P₇ dar nu poate fi ales deoarece se formeaza ciclul OP₅P₇.

Valoarea urmatoare, 7, o au arcele OP₄, P₂P₃ si P₅P₈. OP₄ nu poate fi ales deoarece s-ar forma ciclul OP₅P₄. Arcul P₂P₃ nu poate fi ales deoarece s-ar forma ciclul OP₆P₁P₂P₃. Arcul P5P8 nu formeaza nici un ciclu si el va fi al optulea arc ales. In acest caz, deoarece s-au adunat 8 arce intr-un graf cu 9 noduri, am obtinut graful cautat.

Acest arbore este reprezentat in figura.

B. Sollin

Vom alege:   pentru nodul O arcul OP₃

pentru nodul P₁ arcul P₁P₆

pentru nodul P₂ arcul P₁P₂

pentru nodul P₃ arcul OP₃

pentru nodul P₄ arcul P₄P₅

pentru nodul P₅ arcul OP₅

pentru nodul P₆ arcul P₁P₆

pentru nodul P₇ arcul OP₇

pentru nodul P₈ arcul P₅P₈

Rezulta graful partial:

Dupa cum se vede, s-au format doua componente conexe:

C₁ =

C₂ = .

Vom alege:   pentru C₁ → arcul OP₆

pentru C₂ → arcul OP₆

si obtinem o singura componenta conexa, care este arborele cautat.

C. Varianta algoritmului lui Kruskal

Succesiunea alegerii arcelor va fi:

OP₃

OP₇

OP₆

OP₅

P₁P₆

P₁P₂

P₄P₅

P₅P₈