GRAFURI

GRAFURI

Notiunea de graf

Fie X o multime nevida si multimea perechilor de elemente din X. Daca x ≠ y atunci perechea este identica cu perechea . De asemenea, este un element al multimii P₂(X). Fie E o submultime nevida a multimii P₂(X), E =

Un graf este un cuplu G = (X,E) in care:

• X este o multime nevida ale carei elemente se numesc noduri sau varfuri ale grafului;
• E este o multime ale carei elemente se numesc muchii;
• intre cele doua multimii exista urmatoarea legatura: Fiecarei muchii eE ii sunt asociate doua noduri numite extremitatile muchiei e.

Elementele sunt denumite noduri (sau varfuri) ale grafului G iar elementele multimii E sunt denumite muchii. Doua muchii avand aceleasi extremitati sunt numite paralele. O muchie e= cu extremitatile identice este o bucla. Un graf care nu are nici bucle nici muchii paralele se numeste graf simplu. Numarul elementelor multimii X, notat | X |, este ordinul grafului G iar numarul elementelor multimii E, notat | E |, dimensiunea grafului G. Daca | X | = n si | E |= m atunci graful G = (X, E) este un (n, m) - graf. Graful G = (X, E) se numeste graf finit daca multimile X si E sunt finite.

Reprezentare grafica. Elementele esentiale ale unui graf - nodurile si muchiile - se pot vizualiza printr-un desen in care nodurile sunt reprezentate prin puncte (cercuri) arbitrar plasate in plan iar muchiile prin linii (drepte sau curbe) care unesc punctele corespunzatoare extremitatilor x si y. Distributia nodurilor in plan este conventionala, urmarindu-se doar buna vizualizare a desenului, lungimea muchiilor si unghiurile dintre ele neavand nici o semnificatie practica.

Pentru evitarea confuziilor vom nota, in continuare, o muchie ce uneste nodurile cu etichetele x si y prin [x, y] avand semnificatia unui segment (din geometrie). Muchia [x, y] este identica cu [y, x].

Exemplu: Fie G = (X, E) un graf cu si . Multimea Xeste reprezentata prin sase puncte in plan, corespunzatoare nodurilor x₁, x₂, x₃, x₄, x₅, x₆ incadrate in cercuri. Relatia intre noduri este data de muchiile din E. Fiecarei muchii i se asociaza o pereche de noduri: e₁ = [x₁ ,x₂], e₂ = [x₁, x₃], e₃ = [x₂, x₄], e₄ = [x₃, x₄], e₅ = [x₄, x₆], e₆ = [x₆,x₆]. Muchiile sunt trasate prin segmente de dreapta (sau printr-o curba in cazul unei bucle).

Figura 1.2

Graful din figura 1.2 este un graf etichetat; nodurile sunt notate prin etichetele x₁, x₂, x₃, x₄, x₅, x₆. Evident G este un (6, 6) - graf. Nodul x₅ este un nod izolat nefiind legat de celelalte noduri prin nici o muchie. Muchia [x₆, x₆ este o bucla si este reprezentata printr-o linie curba.

Adiacenta si incidenta. Fie G = (X, E) un graf si x_i xj ε X. Nodurile x_i si xj sunt noduri adiacente daca sunt extremitatile unei muchii a grafului. Doua muchii se vor numi adiacente daca au o extremitate in comun.

Subgraf. Un graf H = (Y, F) este un subgraf al grafului G = (X, E) daca Y X, F E si orice muchie din F are acelasi extremitati in G si H. Subgraful H se obtine din graful G prin eliminarea a cel putin un nod si/sau stergerea unor muchii si a tuturor muchiilor care au macar o extremitate in nodurile eliminate.

Graful este un instrument util in studiul unor colectii de entitati intre care exista anumite legaturi.

Exemple:

retele de transport in care entitatile sunt localitati, fabrici, depozite iar legaturile sunt drumuri auto, feroviare, aeriene sau navale pe care se pot face deplasari de la un punct la altul;

retele de comunicatie audio, video, calculator prin care se conecteaza localitati, locuinte, institutii, birouri;

actiuni complexe compuse dintr-un mare numar de activitati intre care exista relatii de precedenta in ceea ce priveste executia;

structuri organizationale compuse din elemente - persoane fizice, departamente, birouri - intre care exista relatii de subordonare;

retele genealogice, retele electrice etc.

1.2 Lanturi si cicluri

Fie G = (X, E) un graf se numeste un lant in graful G o succesiune de muchii

cu proprietatea ca fiecare muchie e_i are o extremitate comuna cu muchia precedenta si cealalta extremitate in comun cu muchia urmatoare. Numarul p al muchiilor din sirul (1.4) se numeste lungimea lantului .

Un lant poate de lungime 1 este o muchie iar un lant de lungime 2 este constituit din doua muchii adiacente.

Daca pentru lantul din (1.4) este nevoie sa se puna in evidenta si extremitatile muchiilor alcatuitoare se va folosi si notatia alternativa:

(1.5)

in care x_i-1 si x_i sunt extremitatile muchiei e_i.

Nodurile x_o si x_pse numesc extremitatile lantului ; celelalte, adica x_i,, x_p-1 se numesc noduri intermediare.

Se numeste ciclu un lant ale carui extremitati coincid.

Daca notatia (1.5) nodurile x_o si x_p coincid, adica este un ciclu, convenim ca si x_o sa fie socotit nod intermediar. Notatia (1.5) pune in evidenta succesiunea de noduri:

(x₀, x₁, x₂,,x_p-1, x_p) 

Despre ele vom spune ca sunt nodurile lantului sau ca sunt nodurile prin care trece lantul X

Succesiunea (1.6) NU determina complet lantul decat in cazul in care graful G este simplu.

Lantul , dat prin notatia (1.5) se numeste:

lant simplu daca muchiile e₁, e₂,, e_p sunt diferite;

lant elementar daca nodurile x_o, x₁, x₂,, x_p-1, x_p sunt diferite cu exceptia, eventual, a extremitatilor x₀ si x_p care pot coincide cand este ciclu.

Evident, un lant elementar este si simplu dar reciproca nu este in general valabila.

Consideram doua lanturi:

= (e₁,e₂,,e_p)si μ = (f₁, f₂,, f_q)

Vom spune ca lantul este inclus in lantul si notam daca muchiile e₁, e₂,, e_p se gasesc printre muchiile f₁, f₂,, f_q,

Sa presupunem ca extremitatile lantului sunt nodurile x si y, iar extremitatile lantului sunt nodurile y si z, astfel:

=(x, e₁, e₂,, e_p, y) si = (y, f₁, f₂ f_q, z)

Atunci succesiunea de muchii:

(e₁, e₂,, e_p, f₁, f₂,., f_q)

este un lant cu extremitatile x si z, notat . Despre lantul vom spune ca a rezultat din concatenarea lungimilor lanturilor si

Orice lant contine un unic lant elementar cu aceleasi extremitati.

1.3 Grafuri conexe

Sa consideram urmatoarea relatie binara intre nodurile unui graf G = (X, E): x ~ y (x este in legatura cu y) sau x ≡y sau x ≠ y daca si numai daca exista cel putin un lant de muchii cu extremitatile x si y.

Relatia introdusa este: - reflexiva: x ~ x,

- simetrica: x ~ y => y ~ x; - tranzitiva: x~ysiy~z=>x~z.

este deci o relatie de echivalenta in multimea X a nodurilor grafului G. Ea imparte X intr-un numar de submultimi nevide si disjuncte:

cu proprietatile:

oricare doua noduri diferite apartinand aceleasi submultimi V_i, sunt extremitatile unui lant de muchii;

nu exista muchii avand o extremitate intr-o submultime Vi si cealata extremitate intr-o alta submultime Vj cu j≠i.

Daca notam cu E(V_i) multimea muchiilor avand ambele extremitati in submultimea de noduri V_i rezulta ca:

Subgrafurile

se numesc componentele conexe ale grafului G. Graful G se numeste conex daca are o singura componenta conexa.

Un graf este conex daca si numai daca oricare doua noduri distincte ale sale sunt extremitatile unui lant de muchii.

1.4 Cateva clase importante de grafuri

Graf complet. Graful G = (X, E) este complet daca oricare doua noduri x,y e X ale sale sunt extremitatile unei singure muchii. Graful complet cu n noduri se noteaza cu Gn si are muchii;

a)

b)

c)

d)

Figura 1.3

Graf bipartit. Un graf este bipartit daca multimea nodurilor sale este partitionata in doua submultimi disjuncte S si T astfel incat orice muchie are extremitatea a in S si extremitatea b in T. Un graf bipartit se noteaza . intr-un graf bipartit, doua noduri din aceeasi submultime S sau T nu pot fi adiacente.

a b

Figura 1.4

In figura 1.4 sunt reprezentate grafuri bipartite.

Un graf bipartit este complet daca pentru orice nod si orice nod exista o muchie [x, y]. Graful din figura 1.4 a nu este complet dar graful din figura 1.4 b este complet.

Un graf simplu este bipartit daca si numai daca NU contine cicluri de lungime impara.

Arbori. Un graf se numeste arbore daca este conex si fara cicluri

Urmatoarele proprietati sunt echivalente si caracterizeaza calitatea unui graf H de a fi arbore:

• oricare doua noduri diferite din H sunt extremitatile unui unic lant de muchii;
• H este un graf simplu si daca are n noduri atunci are n-1 muchii;
• H este un graf fara cicluri si daca se adauga o muchie se creeaza un ciclu;
• H este un graf conex si daca se scoate o muchie, subgraful ramas nu mai este
  conex.

Fie G = (X,E) un graf oarecare se numeste arbore generator al grafului G un subgraf H = (X,A) cu aceleasi noduri ca si G si este de sine statator este un arbore adica un graf conex si fara cicluri.

Graful G are macar un arbore generator daca si numai daca este conex.

Graf planar. Un graf G=(X,E) se numeste planar daca exista o reprezentare grafica a sa cu proprietatea ca oricare doua muchii nu se intersecteaza decat cel mult in extremitati. Grafurile din figurile 1.3 G₄ si 1.4 b sunt planare cel din figura 1.3 G₅ nu este planar.

1.5 Orientare si neorientare in graf

Fie G = (X,E) un graf pe care il presupunem simplu. Aceasta inseamna ca oricare doua noduri diferite sunt extremitatile a cel mult o muchie. Astfel, fiecare muchie identifica cu multimea a extremitatilor sale.

Fie o muchie oarecare din G. Perechile ordonate (x, y) si (y, x) se numesc arce generate de muchia . Despre oricare din aceste arce vom spune ca este opus celuilalt, iar muchia este suportul celor doua arce.

Pentru arcul (x, y) nodul x va fi extremitatea initiala iar nodul y va fi extremitatea finala.

A da o orientare pe muchia sau a orienta muchia inseamna a alege unul dintre cele doua arce (x, y) sau (y, x), generat de muchia . Arcul ales se va numi arc permis iar celalalt vom spune ca este blocat.

Daca muchia a fost orientata prin alegerea arcului (x, y) vom zice ca muchia 'poate fi parcursa de la x la y'. Daca muchia nu este orientata vom spune ca ea "poate fi parcursa in ambele sensuri si de x la y si de la y la x'.

A da o orientare in graful G inseamna a da o orientare pe unele din muchiile sale. Graful G = (X, E) este orientat (partial orientat) daca toate muchiile sale (respectiv doar o parte din ele) au fost orientate.

Presupunem ca in graful G = (X,E) s-a dat o orientare oarecare: vida, partiala sau totala. Vom nota cu U multimea arcelor permise.

in contextele in care orientarea muchiilor este necesara, pentru graful G vom folosi notatia G = (X, E, U).

Se numeste drum in graful G = (X, E, U) o succesiune de arce permise

(1.1)

cu proprietatea ca extremitatea finala a arcului U_i coincide cu extremitatea intiala a arcului u_i+1, unde i=1,,p-1. Numarul p al arcelor alcatuite se numeste lungimea drumului μ.

Daca pentru drumul fi este necesar sa se puna in evidenta extremitatile arcelor componente vom folosi notatia alternativ

μ = (x₀, u_i, x_i, u₂, x₂,,u_i-1, u_i, x_i,,x_p-1, u_p,x_p)

unde x_i+1 este extremitatea initiala a arcului u_i iar x_i extremitatea finala. Deoarece graful G este presupus simplu drumul μ din (1) sau (2) este perfect determinat si de succesiunea de noduri:

(x₀, x₁, x₂,, x_p-1, x_p) (1.3)

Nodul x₀ este extremitatea initiala a drumului μ iar xp extremitatea finala.

Celelalte noduri, adica x₁,, x_p se numesc noduri intermediare " prin care trece' drumul μ,

Daca extremitatile x₀ si x_p coincid vom spune despre drumul μ ca este un circuit. Daca este asa socotim si nodul x₀, ca nod intermediar.

Sa consideram acum suporturile e_`, e₂, ,e_p ale arcelor permise u₁,u₂,,u_p ce compun drumul μ . Este clar ca succesiunea de muchii (e₁,e₂, ,e_p) este un lant denumit suportul drumului μ. Atat drumul μ cat si lantul suport au aceleasi extremitati si aceleasi noduri intermediare iar daca μ este un circuit suportul va fi un ciclu.

Consideratiile precedente sugereaza urmatoarea generalizare. Se numeste lant de arce permise o succesiune:

de arce permise cu proprietatea ca succesiunea de muchii in care e_i este suportul arcului v_i este un lant de muchii.

Orice drum este un lant de arce permise dar reciproca nu este adevarata; intuitiv, un lant de arce este un drum numai daca arcele componente 'au aceeasi orientare'.

in mod firesc vom defini extremitatile si nodurile intermediare ale uni lant de arce ca fiind extremitatile si nodurile intermediare ale lantului de muchii suport.

Un ciclu de arce permise va fi un lant de arce permise ale carui extremitati coincid.

Un lant de arce permise (in particular un drum) se va numi simplu (elementar) daca arcele componente sunt diferite (respectiv daca nodurile prin care trece sunt diferite cu exceptia eventual a extremitatilor care pot coincide).

Exemplu: Consideram graful simplu din figura 1.7a) in care s-a dat o orientare pe o parte a muchiilor componente; orientare indicata in figura 1.7b):

este un drum elementar de lungime 3

Succesiunea:

reprezentata mai sugestiv

este un circuit elementar de lungime 3.

Muchia reprezentata sugestiv

nu este orientata si ca urmare ambele arce generate (3,5) si (5,3) reprezentate sugestiv prin sunt considerate permise.

Succesiunile:

si

sunt lanturi elementare de arce premise cu acelasi support si anume:

Ciclul de muchii:

este suportul comun al circuitului:

cat si a ciclului de arce permise:

§ 2. Problema drumului de valoare minima

Fie G = (X,E) un graf finit. Daca este o muchie cu extremitatile x_i, si x_j, atunci aceasta muchie are o orientare permisa prin arcele (x_i, x_j) si (x_j, x_i). In acest mod, un graf neorientat este tratat ca graf orientat G = (X, U). In continuare, ne referim numai la grafuri

orientate finite.

Un arc este valorizat daca i se asociaza o valoare numerica reala pozitiva v(u) ≥ 0, numita valoarea arcului u sau ponderea arcului u. Un graf G = (X, U) este valorizat daca arcele sale sunt valorizate. Daca arcul u este dat prin extremitatile sale , valoarea arcului va fi data si prin notatiile v(x_i x_j), sau v_ij. Daca u este o muchie in graful G = (X, E) atunci v(u) = v(x_i, x_j) =v(x_j, x_i), deci pe ambele directii arcul are aceeasi valoare. Valorile asociate arcelor pot reprezenta distante intre doua localitati, costurile executarii unei lucrari pe tronsoanele respective, costurile trecerii unei linii de fabricate de la un produs la altul, timpii de executie ai unor activitati, masura sigurantei transmisiunii unui semnal etc.

Pentru un drum μ intre nodul si nodul, precizat prin specificarea arcelor componente, se defineste valoarea drumului μ ca fiind suma valorilor arcelor componente:

(2.1)

Un drum este o succesiune de arce permise: cu proprietatea ca pentru orice 1 ≤ i ≤ q-1 extremitatea finala a unui arc u_i coincide cu extremitatea initiala a arcului u_i+1. Numarul arcelor componente defineste lungimea |(μ) a drumului μ.

Drumurile de lungime 1 se identifica cu arcele permise ale grafului. Daca U₁=(x₀, x₁), u₂ = (x₁, x₂),,u_q = (x_q-1,x_q) sunt arcele date prin extremitatile lor, atunci un drum poate fi definit si prin succesiunea de noduri:

Nodul x_o este extremitatea de start a drumului μ iar nodul x_q extremitatea finala. Daca extremitatile sale coincid (x₀ = x_q) atunci drumul μ este un circuit.

Un drum este elementar daca nodurile sale sunt distincte (drumul trece o singura data prin fiecare nod al sau). Un drum este simplu daca arcele sale sunt distincte (drumul trece o singura data prin fiecare arc al sau). Evident, orice drum elementar este si simplu. Reciproca nu este, in general, adevarata. Multimea drumurilor elementare dintr-un graf finit este finita. Un drum μ dintr-un graf G este inclus in drumul daca toate arcele drumului μ sunt arce si ale drumului μ'.

Evident, v(μ) ≤ v(μ').

Daca si sunt doua drumuri din G, acestea sunt concatenabile in ordinea "μ¹ urmat de μ²" daca (extremitatea finala a drumului μ¹ coincide cu extremitatea de start a drumului μ²). Prin concatenare (se obtine drumul:

cu lungimea:

Deci, prin concatenare, orice drum μ intr-un graf G se reprezinta in forma:

unde μ¹, μ²,.., μⁿ sunt drumuri si/sau circuite elementare, nu neaparat distincte. De asemenea, orice drum μ din graful G contine un unic subdrum elementar μ'avand aceleasi extremitati ca si μ .

In graful G din figura 2.1, drumul μ = (1, 3, 5, 4, 3, 2, 4, 5, 6) se descompune in urmatoarele drumuri si circuite elementare:

Figura 2.1

Drumul μ = (1, 3, 2, 4, 5, 6) este un drum elementar avand aceleasi extremitati ca si drumul μ.

O problema extremala intr-un graf orientat G = (X, U) consta in determinarea unui drum elementar (sau a drumurilor elementare), intre doua noduri date, de valoare minima (sau de valoare maxima).

Fie s si t doua noduri oarecare ale grafului G. Notam cu G*(s, t) un subgraf al grafului G format din multimea drumurilor din graful considerat G = (X, U) intre nodurile s si t, in care sunt incluse si drumurile de lungime 1. Problema drumurilor de valoare minima intre nodurile s si t se defineste ca problema determinarii drumului μ* de la nodul s la nodul t in graful G*(s, t), de valoare minima:

(2.2)

Daca se considera drumurile de valoare minima de la un nod s la oricare alt nod al grafului G, multimea acestor drumuri formeaza un graf partial orientat in G, numit graful drumurilor de valoare minima cu originea in nodul s si este notat G*(s) simplu G*.

Problema pusa in acest fel cuprinde si problema determinarii drumurilor de valoare minima de la nodul s la un alt nod oarecare t. intr-adevar, daca in G*(s) figureaza si nodul t, atunci in acest graf vom gasi si drumurile de valoare minima de la s lat

Daca luam in considerare numai drumurile elementare de la s la t, deoarece multimea acestora este finita, atunci exista, intotdeauna, un drum de la s la t de valoare minima. Aceste drumuri elementare sunt identificate greoi, motiv pentru care drumurile de valoare minima se determina considerand, in graf, toate drumurile elementare sau neelementare intre cele doua noduri.

Este posibil ca problema (2.2) sa nu admita solutii optime (de exemplu in cazul existentei circuitelor de valoare negativa). in acest caz, exista o infinitate de drumuri de la s la t a caror multime de valori poate fi nemarginita inferior.

Pentru ca multimea drumurilor elementare este finita minimul acesteia este efectiv atins intr-un element al acesteia si problema are solutii, in sensul ca exista drumuri de valoare minima.

Un circuit in graful G de valoare strict negativa este numit circuit absorbant. Deoarece problemele de determinare a drumurilor de valoare minima intre nodurile date se rezolva considerand toate drumurile posibile, nu numai cele elementare, vom presupune verificata urmatoarea conditie: in graful G nu exista circuite de valoare strict negativa.

Determinarea drumului de valoare minima poate avea loc intr-un graf in care valorile sau ponderile arcelor sunt nenegative. in grafuri in care exista arce cu ponderi negative, sunt necesare eforturi mai mari pentru rezolvare; in acest caz se va presupune indeplinita conditia: nu exista circuite de valoare strict negativa (absorbante).

Daca extremitatea de start a unui drum este un nod sursa s si extremitatea finala un nod destinatie t, problemele extremale pe care le analizam in continuare, se grupeaza in trei categorii:

1. Un singur nod sursa si un singur nod destinatie. Fiind date doua noduri s si t, unul nod sursa si celalalt nod destinatie, se cere determinarea drumului sau drumurilor de valoare minima de la nodul sursa s la nodul destinatie t;
2. Un singur nod sursa. Fiind dat un singur nod sursa s, se cere determinarea drumurilor de valoare minima de la nodul sursa la fiecare nod al grafului;
3. Un singur nod destinatie. Fiind dat un nod destinatie t, se cere
   determinarea drumurilor de valoare minima, de la fiecare nod al grafului la nodul destinatie t.

Problemele din categoria a treia pot fi rezolvate ca problemele din categoria a doua, dar pe graful transpus grafului dat. in graful transpus, nodul t devine sursa si se determina G*(t) si drumul de valoare minima. Dupa rezolvare, se face transpunerea grafului G*(t) si se obtine drumul de valoare minima de la fiecare nod la nodul destinatie t.

Daca μ si μ'sunt drumuri elementare in G avand aceleasi extremitati, atunci drumurile pot fi comparabile: fie v(μ') ≤ v(μ), fie v(μ') ≤ v(μ').

In cazul in care exista drumuri de la s la t, evaluarea si compararea acestora, conform afirmatiei anterioare, se poate limita la drumurile elementare cu aceleasi extremitati. Numarul drumurilor elementare fiind finit unul dintre ele va fi drumul de la s la t de valoare minima.

Daca graful G nu este conex si nodurile s si t nu fac parte din aceeasi componenta conexa sau orientarile pe arce nu permit atingerea nodului t din nodul s, exista posibilitatea ca in graful G sa nu existe drumuri de la s la t.

§ 3. Problema arborelui de cost minim

In optimizarea combinatoriala, problema arborelui de cost minim are numeroase aplicatii practice. Contextul general este urmatorul: un numar de 'puncte' trebuie conectate intre ele pentru facilitarea transmiterii unui anumit serviciu (telefon, TV, calculator). intre puncte exista 'legaturi potentiale' a caror realizare implica un anumit cost.

Problema care apare este aceea de a vedea ce legaturi vor fi efectiv realizate astfel incat:

• oricare doua puncte sa fie conectate - direct sau indirect - in vederea
  utilizarii serviciului;
• suma costurilor legaturilor realizate sa fie minima.

Algoritm de rezolvare a problemei arborelui de cost minim:

Algoritmul lui Kruskal:

Pasul 1 Dintre toate muchiile grafului se alege muchia de valoare minima. Daca minimul este multiplu se alege la intamplare una din muchiile respective;
Pasul 2 Dintre toate muchiile ramase, se alege cea de valoare minima, astfel incat sa nu se formeze cicluri cu cele deja alese;

Pasul 3 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.
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 posibila).

§ 4. Problema comisvoiajorului

Un comisvoiajor are de vizitat un numar de orase, la sfarsitul voiajului el intorcandu-se in localitatea de plecare. Deplasarea dintr-o localitate in alta presupune anumite cheltuieli (sau distante de parcurs sau durate de mers).

In ce ordine trebuiesc vizitate orasele astfel incat costul total al deplasarii (sau lungimea traseului sau durata calatoriei) sa fie minim?

Astfel enuntata, problema comisvoiajorului (notata pe scurt TSP de la Travelling Salesman Problem) este una din cele mai grele probleme de optimizare combinatoriala. Pe langa importanta teoretica, ea are numeroase aplicatii practice. De exemplu, stabilirea celor mai 'economice' trasee turistice intr-un mare oras sau zona istorica (din punctul de vedere al costurilor sau distantelor) este o problema a comisvoiajorului. De asemenea, stabilirea ordinii in care un numar de operatii (joburi) vor fi executate pe un utilaj, astfel incat suma timpilor de pregatire ai utilajului sa fie cat mai mica, este o problema de acelasi tip.

4.1 Modelul matematic al problemei comisvoiajorului

Sa notam cu 0,1,,n orasele problemei, 0 fiind orasul din care comisvoiajorul pleaca si in care revine la terminarea calatoriei. Fie c_ij costul deplasarii din localitatea i in localitatea j≠i; punem c_ij = ∞ daca nu exista legatura directa intre i si j sau in cazul i = j. Un traseu va fi descris cu ajutorul variabilelor bivalente :

1, daca traseul trece direct de la orasul I la orasul j, i≠j;

X_ij= 0, in caz contrar sau daca, i=j;

Urmeaza a fi minimizata functia:

(4.1.1)

Din orice oras i, comisvoiajorul trebuie sa se indrepte catre o alta localitate, astfel ca:

(4.1.2)

in orice oras ar ajunge, comisvoiajorul vine dintr-o localitate anterior vizitata, asa ca:

(4.1.3)

Observam ca ansamblul (4.1.1) - (4.1.3) constituie modelul matematic (PA) al unei probleme generale de afectare. O examinare mai atenta a problemei arata ca restrictiile (4.1.2) si (4.1.3) nu definesc numai trasee ce trec prin toate orasele (o singura data!) ci si 'reuniuni' de circuite disjuncte mai mici! Astfel intr-o problema cu 7 orase 0,1,,6 ansamblul:

x₀₃ = x₃₅ = x_5o = x₂₁ = x₁₄ = x₄₆ = x₆₇ = x₇₂ = 1 , x_ij = 0 in rest

satisface restrictiile (4.1.2) si (4.1.3) dar nu constituie un traseu complet asa cum se vede din figura 4.1

Pentru evitarea acestui neajuns asociem oraselor 1,2,,n , diferite de localitatea de plecare si sosire 0, variabilele y₁,y₂,,y_n si introducem inegalitatile:

y_i - y_j + nx_ij ≤ n-1, i,j = 1,2..n; i ≠ j (4.1.4)

In principiu noile variabile pot lua orice valoare reala. Vom arata ca daca x = (x_ij) determina un traseu complet atunci exista valori numerice y₁, y₂,.. .,y_n care impreuna cu x_ij satisfac relatiile (4.1.4). Intr-adevar, definim y_i ca fiind numarul de ordine al localitatii i in cadrul traseului determinat de x. Pentru i≠j doua situatii sunt posibile:

• localitatea j nu urmeaza imediat dupa localitatea i. Atunci x_ij = 0 si (4.1 .4) devine y_i-y_j ≤ n -1 ceea ce este adevarat avand in vedere semnificatia acordata valorilor y₁, y₂,,y_n.
• localitatea j urmeaza imediat dupa localitatea i. Atunci y_j = y_i + 1 , x_ij = 1si (4.1.4) se verifica cu egalitate.

Sa presupunem acum ca z = (x_ij) defineste o reuniune de 'subtrasee' disjuncte. Alegem unul care nu trece prin localitatea 0 si fie k numarul deplasarilor cel compun. Presupunand ca ar exista valori numerice y₁, y₂,,y_n care sa satisfaca (4.1.4) insumam pe acelea corespunzatoare deplasarilor de la un oras la altul din subtraseul ales. Obtinem nk ≤ (n - l)k ceea ce este evident fals.

In concluzie, ansamblul (4.1.1) - (4,1.4) constituie modelul 'corect' al problemei comisvoiajorului. Este vorba de un program mixt ce utilizeaza atat variabile intregi (bivalente) cat si variabile care pot lua orice valoare. In continuarea unei observatii anterioare, putem spune ca problema comisvoiajorului.(TSP) este o problema de afectare (PA) (ansamblul (4.1.1) - (4.1.3)) cu restrictiile speciale (4.1 .4).

In consideratiile de mai sus costurile c_ij nu sunt 'simetrice' adica este posibil ca c_ij≠c_ij. Problema simetrica a comisvoiajorului se caracterizeaza prin c_ij = c_ji; aceasta se intampla daca , de exemplu, c_ij sunt distante sau timpi de parcurgere.

Un caz particular al problemei simetrice este asa numita problema euclidiana a comisvoiajorului in care distantele c_ij satisfac inegalitatea triunghiului:

4.2 Un algoritm exact de rezolvare a problemei comisvoiajorului

Urmatorul algoritm, de tip B&B, reduce rezolvarea TSP la rezolvarea unei liste de probleme de afectare. El s-a dovedit suficient de robust pentru probleme asimetrice cu un numar moderat de orase. Principalul dezavantaj il reprezinta faptul ca numarul problemelor de afectare de rezolvat este impredictibil si poate fi imens in cazul situatiilor reale. Algoritmul este datorat lui Eastman. Ca orice procedura de tip B&B, el utilizeaza:

• 'locatie' X_CMB care va retine 'cel mai bun' traseu gasit de algoritm pana la un moment dat;
• variabila ZCmb care retine costul traseului memorat in xCmb;
• lista L de probleme de afectare asemanatoare problemei (PA) si care difera de problema (PA) initial prin anumite costuri cy schimbate in 03

La start:

• X_CMB poate fi locatia 'vida' in care caz Z_CMB = ∞ sau retine un traseu arbitrar ales sau general printr-o metoda euristica, X_CMB fiind initializat cu costul aferent acestui traseu;
• lista L cuprinde numai problema (PA) initiala, determinata de
  (4.1.1)-(4.1.3);

Pasul 1. Daca lista L este vida stop. Altminteri, selecteaza o problema din lista L Problema aleasa se sterge din L . Se trece la:

Pasul 2. Se rezolva problema selectata. Daca valoarea functiei obiectiv este ≥ Z_CMB se revine la pasul 1. Altminteri, se trece la:

Pasul 3. Daca solutia optima este un traseu complet se actualizeaza X_CMB si Z_CMB dupa care se revine la pasul 1. Altminteri se trece la:

Pasul 4. (Solutia optima nu este un traseu ci o reuniune de 'subtrasee mai mici'). Din solutia optima se selecteaza circuitul cu cel mai mic numar de arce. Pentru fiecare arc (i,j) din circuitul ales (pentru care x_ij = 1) se adauga la lista L problema obtinuta din cea rezolvata punand c_ij = ∞. Se revine la pasul 1.

Observatii:

Ratiunea pasului 4 este clara: daca i→j→k→.→l→i este circuitul selectat este clar ca in traseul optim vom avea:

x_ij = 0 sau k_jk = 0 sau sau x_li = 0.

In consecinta, vom cauta traseul optimal printre cele in care x_ij = 0 si daca nu este acolo printre cele in care x_jk = 0 s.a.m.d. Limitarea la traseele in care x_ij = 0 se face efectuand schimbarea c_ij = ∞.

La pasul 4, in lista L vor aparea atatea probleme cate arce are circuitul selectat; de aceea se alege circuitul cu cel mai mic numar de arce!

In raport cu termenii generali ai unei metode B&B, ramificarea are loc la pasul 4 in timp ce marginirea se efectueaza la pasul 2.

Exemplu: Se considera problema asimetrica a comisvoiajorului cu cinci orase, definita de urmatoarea matrice a costurilor:

Start: Se pleaca de la traseul0→1→2→3→4→0, care se retine in X_CMB si al carui cost este Z_CMB = 10+10 +20+15+10 = 65. Lista L a problemelor de afectare ce urmeaza a fi rezolvate coprinde numai problema initiala (PA).

Iteratia 1: Se sterge (PA) din lista L si se rezolva. Se obtine solutia optima:

X₀₄ = x₄₀ = x₁₂ = x₂₃ = x₃₁ = 1 , X_ij = 0 in rest ce corespunde reuniunii urmatoarelor subtrasee:

0→4→0 si 1→2→3→1

Selectam subtraseul 0→4→0 si adaugam la L problemele PA₁ si PA₂ derivate din PA inlocuind C₀₄ respectiv C4₀ cu ∞.

Iteratia 2: Selectam problema PA₁ si o rezolvam. Lista L va cuprinde mai departe numai problema PA₂. Pentru PA₁ se gaseste solutia optima:

x₀₃ = x₁₂ = x₂₄ = x₃₁= x₄₀ = 1 , x_ij= 0 in rest

care corespunde traseului complet 0→3→1→2→4→0. Costul sau este Z_CMB = 65.Nu am gasit deci un traseu mai bun decat cel pe care il avem in X_CMB.

Iteratia 3: Rezolvam problema PA₂, singura ramasa in L. Se obtine solutia optima:

x₀₄ = x₁₂ = x₂₃ = x₃₀ = x₄₁ = 1 ,  xy = 0 in rest

care corespunde traseului 0→4→1→2→3→0. Costul noului traseu este Z_CMB> 62, drept care il retinem in X_CMB si actualizam Z_CMB = 62.

Deoarece lista este acum vida traseul retinut in X_CMB este optim.

4.3 Metode euristice de rezolvare aproximativa a problemei comisvoiajoruiui

De obicei, solutia optima a unei TSP este foarte greu de gasit (daca nu chiar imposibil de gasit) atunci cand numarul oraselor de vizitat este mare (peste 50). Pentru determinarea unei solutii macar acceptabile au fost elaborate mai multe procedee euristice. Aceste procedee merita atentie din doua puncte de vedere:

se poate da un 'certificat de garantie' pentru solutia   obtinuta in sensul ca este posibila evaluarea 'departarii' maxime de solutia optima;

solutia aproximativa este gasita cu un efort de calcul relativ moderat si intr-un timp rezonabil, aceasta insemnand ca cei doi parametric depind polinomial de dimensiunea problemei (adica numarul de orase);

In multe situatii practice, procedeele euristice au condus chiar la solutia optima dar acest lucru a fost confirmat numai prin aplicarea unui algoritm exact.

In principiu, o metoda euristica construieste o solutie prin tatonare, din aproape in aproape, facand la fiecare pas cea mai buna alegere posibila. Din nefericire, aceasta 'schema' nu conduce, de regula, la cea mai, buna alegere globala.

In continuare, vom prezenta mai multe euristici pentru rezolvarea problemei euclidiene a comisvoiajoruiui adica a problemei in care C_ij sunt distante ce satisfac:

conditia de simetrie: c_ij = c_ji;

inegalitatea triunghiului c_ik ≤c_ij + c_jk;

Euristica E₁ (mergi la cel mai apropiat vecin)

se pleaca din localitatea 0 catre localitatea cea mai apropiata;

din ultima localitate vizitata se pleaca catre cea mai apropiata localitate nevizitata; in caz ca nu mai exista localitati nevizitate se revine in locul de plecare;

Euristica E₂ (Ajustare locala)

se pleaca de la un traseu complet, determinat fie "la intamplare' fie printr-o alta euristica;

se cauta doua arce (u,v) si (x,y) ale traseului care nu sunt consecutive si se compara distante c_uv + c_xy cu c_ux + c_vy. Daca c_uv+ c_xy > c_ux + c_uy se inlocuiesc arcele (u,v) si (x,y) cu (u,x) si (v,y) obtinandu-se un traseu de lungime mai mica ;

procedura se opreste in momentul in care nu mai exista situatii similare cu cea descrisa;

Euristica E₃

• se determina un arbore H de lungime minima (aceasta este o
  problema 'usoara rezolvabila de exemplu cu algoritmul lui Kruskal);
• fiecare muchie a arborelui H se inlocuieste cu doua muchii de aceeasi lungime. Se obtine un multigraf H' in care fiecare nod are grad par.Conform teoremei lui Euler in H' exista un ciclu eulerian; cu alte cuvinte, este posibil sa se viziteze orasele astfel incat fiecare muchie a muftigrafului H' sa fie parcursa o singura data.

Fie:

0→x→ y→ →u→v → 0 (4.3.1)

succesiunea in care muchiile multigrafului H' au fost parcurse. Lungimea acestui 'traseu' este de doua ori mai mare decat lungimea arborelui minimal H. In aceasta secventa, unul sau mai multe orase apar de mai multe ori. Vom proceda atunci la urmatoarea operatie de scurtcircuitare:

in succesiunea (4.3.1) se determina prima tripleta de orase succesiv vizitate

i→j → k cu proprietatea ca orasul j 'din mijloc' mai apare ulterior in succesiune. Se inlocuieste secventa i→j→k cu arcul i → k. Prin aceasta scurtcircuitare:

fiecare oras continua sa fie vizitat cel putin o data;

noul traseu este mai scurt pentru ca c_ij+c_jk≥c_ik;

Operatia de scurtcircuit se repeta pana cand in secventa (4.3.1.) "actualizata" fiecare oras, cu exceptia localitatii 0 apare o singura data.

Se poate demonstra ca lungimea traseului obtinut prin aceasta euristica este cel mult de doua ori mai mare decat lungimea traseului optim (in practica lucrurile stau insa mai bine.)

Euristica E₄

Aceasta procedura, datorata lui Cristofides, este o rafinare a euristicii precedente. Deoarece suma gradelor nodurilor din arborele H este para, numarul nodurilor de grad impar este par! Folosind numai aceste noduri si muchiile dintre ele vom determina cuplajul C de pondere minima, ponderile muchiilor luate in calcul fiind distantele dintre extremitati.

Fie H' graful rezultat din H prin adaugarea muchiilor cuplajului C, cu mentiunea ca daca intre doua noduri avem o muchie in H si o alta in C, graful H' va avgea intre nodurile respective doua muchii. Prin constructie, in H' fiecare nod are grad par, astfel ca H' are un ciclu eulerian. Plecand de aici si utilizand de aici si utilizand tehnica scurtcircuitarii se ajunge la un traseu complet.

Se poate arata ca lungimea acestui traseu nu depaseste 3/2 din lungimea traseului optim.