Rezolvarea Unor Probleme Relative la Drumuri de Valoare Optima

Politehnica

Rezolvarea Unor Probleme Relative la Drumuri de Valoare Optima

Byadmin ianuarie 1, 2024

Cuprins

Introducere

Capitolul I

Graf

1. 1. Grafuri orientate – Noțiuni de bază

1. 2. Matrici atașate unui graf

Capitolul II

Algoritmi pentru rezolvarea unor probleme relative la grafuri

2. 1. Algoritmul lui Yu Chen pentru aflarea matricei drumurilor

2. 2. Algoritmi pentru precizarea existenței circuitelor într-un graf

2. 3. Algoritmi pentru aflarea componentelor tare conexe ale unui graf

2. 4. Drumuri și circuite hamiltoniene

Capitolul III

Rezolvarea unor probleme relative la drumuri de valoare optimă

3. 1. Grafuri valorizate. Principiul optimalității.

3. 2. Drumuri optime într-un graf. Algoritmi de găsire a drumului optim

3. 2. 1. Algoritmul lui Bellman – Kalaba

3. 2. 2. Algoritmul lui Ford simplificat

3. 2. 3. Algoritmul lui Dijkstra

Concluzii

Anexa

Anexa 1

Obtinerea arborelui partial de cost minim folosind algoritmul lui Kruskal

Anexa 1.1

Cod sursa Algoritm Kruskal

Introducere

În această scurtă introducere este prezentat pe scurt conținutul lucrări numită: “Algoritmi combinatoriali”.

În prima parte avem o descriere despre grafuri orientate cu noțiuni de bază: ce este un graf, din ce este alcătuit graful (din mulțimi de vârfuri, numite și noduri, și mulțimi de muchii,numite și arce), ordinul unui graf (este egal cu numărul de noduri ale grafului), ce este un graf parțial altui graf (graful parțial se obține din graful căruia îi este parțial prin suprimarea anumitor arce),ce este un subgraf (este graful însăși sau se obține din acel graf prin suprimarea anumitor vârfuri și a tuturor arcelor incidente cu acestea), lanțul unui graf (un traseu care unește prin arce două noduri numite extremități), drumul uni graf (coincide în mare parte cu lanțul uini graf,orice drum este și lanț), noțiunea de conexitate.

Despre matricile atașate uni graf: matricea conexiunilor directe(o matrice pătratică de ordin n), valorile matricei conexiunilor directe(se poate considera ca o valoare booleana), matricea conexiunilor totale,matrice latină.

În a doua parte sunt prezentați câțiva algoritmi pentru rezolvarea unor probleme relative la grafuri: algoritmul lui Yu Chen pentru aflarea matrici drumurilor(pași prin care se realizează acest algoritm,un scurt exemplu), algoritmi petru precizarea existenței circuitelor într-un graf(algoritmul notării-cu pași pentru realizarea acestui algoritm si exemplificat, algoritmul matricei drumurilor ),o scurtă prezentare despre algoritmi pentru alfarea tare conexe ale unui graf, drumuri și circuite hamiltoniene(despre problema comis voiajerului,o reprezentare a reginunii aprovizionate, problema poștașului,problema adunarii deșeurilor, aplicarea algoritmului Chen pentru determinarea drumurilor hamiltoniene în grafuri fara circuite,algoritmul Chen pentru grafuri cu circuite).

În a treia parte sunt prezentate grafuri pentru rezolvarea unor probleme relative la drumuri de valoare optimă: grafuri valorizate(valoarea arcului, valoarea drumului), drumuri optime într-un graf(algoritmul lui Bellman-Kalabe care găsește drumul de valoare minimă de la toate nodurile grafului la un nod oarecare fixat, algoritmul lui Ford simplificat-se aplică la grafuri care nu admit circuite și este folosit pentru găsirea drumului de valoare optimă intre două noduri fixate, algoritmul lui Dijkstra care este o completare a algoritmului Ford deoarece păstrează, la fiecare iterație, mulțimea minimă de noduri, pe oate cele care formează efectiv drumul optim).

La fiecare algoritm sunt prezentați pașii de realizare a algoritmului, un exemplu și unele demonstratii aferente algoritmilor.

Capitolul I

Graf

1. 1. Grafuri orientate – Noțiuni de bază

Definiția 1. 1. 1. Numim graf o pereche ordonată de mulțimi, notată G=(X, U), unde X este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U este o mulțime de perechi (neordonate sau ordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numește neorientat, altfel acesta este orientat.

Observația 1. 1. 1. Conform definiției 1. 1. 1., un graf orientat G este format dintr-o pereche ordonată de mulțimi G = (X, U), ca și în cazul grafurilor neorientate, X este mulțimea vârfurilor sau nodurilor grafului. Mulțimea U este formată din perechi ordonate de elemente distincte din X, numite arce. Orice arc uU va fi notat prin u = (x, y) cu x, yX.

Spunem ca vârful x este extremitatea inițială a arcului u, iar vârful y este extremitatea finală a arcului u. Spre deosebire de cazul grafurilor neorientate, notațiile (x,y) și (y,x) vor desemna două arce diferite.

Daca graful G conține arcul (x, y) vom spune ca vârfurile x și y sunt adiacente în G și amândouă sunt incidente cu arcul (x, y). Deci, un graf orientat G poate fi imaginat ca o mulțime de vârfuri, dintre care unele sunt unite două câte două prin arce. Un graf orientat poate fi desenat în plan reprezentând vârfurile sale prin puncte și arcele prin săgeți care sunt orientate de la extremitatea inițială catre extremitatea finală a fiecarui arc, vezi exemplul 1. 1. 1.

Exemplul 1. 1. 1. În graful din figura 1. 1. 1. mulțimea nodurilor este X = {1, 2, 3, 4, 5, 6, 7} și mulțimea arcelor este U={u1, u2, u3, u4, u5, u6, u7, u8, u9, u10}={(1, 2), (2, 3), (3, 4), (4, 1), (3, 5), (5, 3), (5, 6), (6, 7), (7, 6), (7, 5)}.

Definiția 1. 1. 2. Numim ordinul unui graf, numărul de noduri al grafului, deci cardinalul mulțimii X și Notăm această valoare cu | G |. Numărul de muchii se notează cu.

Observația 1. 1. 2. Graful vid este graful și se notează cu. Spunem că un

graf G este trivial dacă acesta are ordinul 0 sau 1.

Fie un graf și un vârf.

Definiția 1. 1. 3. Mulțimile și se

numesc mulțimea succesorilor, respectiv mulțimea predecesorilor lui x. Mulțimea se numește mulțimea vârfurilor adiacente lui x sau vecinătatea lui x.

Definiția 1. 1. 4. Cardinalul mulțimii se notează cu și se numește semigradul exterior al lui x, iar cardinalul mulțimii se notează cu și se numește semigradul interior al lui x. Gradul vârfului x, notat , este .

Exemplul 1. 1. 2. Pentru graful din exemplul 1. 1. 1. avem:

, , .

, .

Observația 1. 1. 3. Dacă adunăm gradele tuturor nodurilor din graful G, obținem de două ori numărul de muchii, adică:

Definiția 1. 1. 5. Un graf parțial al unui graf orientat G = (X, U) este un graf

Observația 1. 1. 4. Un graf parțial G al grafului G se obține din graful G prin suprimarea anumitor arce.

Exemplul 1. 1. 3. Porninid de la graful G = (X, U) dat de exemplul 1. 1. 1. se pot construi grafurile parțiale unde și

Definiția 1. 1. 6. Un subgraf al lui G este un graf H = (Y, V), unde YX, iar arcele din V sunt toate arcele din U care au ambele extremițați în mulțimea de vârfuri Y.

Observația 1. 1. 5. Deci un subgraf H al unui graf orientat G, este graful G însuși, sau se obține din G, prin suprimarea anumitor vârfuri și a tuturor arcelor incidente cu acestea.Vom spune ca subgraful H este indus sau generat de mulțimea de vârfuri Y.

Exemplul 1. 1. 4. Porninid de la graful G = (X, U) dat de exemplul 1. 1. 1. se poate construi subgraful , unde Y={1, 2, 3, 4, 5} și V={(1, 2), (2, 3), (3, 4), (4, 1), (3, 5), (5, 3)}={ }, vezi figura 1. 1. 2.

Definiția 1. 1. 7. Un graf orientat este complet dacă oricare două vârfuri sunt adiacente.

Definiția 1. 1. 8. Un lanț al unui graf orientat se definește ca un șir de arce L = [u1, u2, . . . , up], cu proprietatea că oricare arc din acest șir are comună o extremitate cu , iar cealaltă extremitate este comună cu pentru orice i = 2, . . . , p-1.

Observația 1. 1. 6. Altfel spus, un lanț este un traseu care unește prin arce două noduri numite extremitățile lanțului, fără a ține cont de orientarea arcelor componente.

Definiția 1. 1. 9. Un drum într-un graf orientat G = (X, U), este un șir de vârfuri notat :

D = (x0, x1, . . . , xr), cu proprietatea că (x0, x1), (x1, x2), . . . , (xr-1, xr)U, deci sunt arce ale grafului. Vârfurile x0 si xr se numesc extremitățile drumului D. Dacă vârfurile x0, x1, . . . , xr sunt distincte două câte două, drumul D se numește elementar.

Observația 1. 1. 7. Din aceste definiții rezultă ca orice drum este și lanț, dacă îl privim ca pe un șir de arce. Dacă toate arcele lanțului L au aceeași orientare, care este dată de sensul deplasării de la x0 către xr, lanțul L este un drum. Un drum D = (x0, … ,xr) poate fi interpretat ca fiind traseul unei deplasări, pe arcele grafului, în ordinea (x0, x1), (x1, x2), . . . , (xr-1, xr).

Definiția 1. 1. 10. Fie drumul D = (x0, x1, . . . , xr), dacă x0 = xr și toate arcele (x0, x1), (x1, x2), . . . ,(xr-1, xr) sunt distincte două câte două, drumul D se numește circuit. Dacă toate vârfurile circuitului, cu excepția primului și a ultimului vârf, sunt distincte două câte două, circuitul se numește elementar.

Exemplul 1. 1. 5. L = [u1, u2, ] este lanț în graful din exemplul 1. 1. 1.

este drum în graful din exemplul 1. 1. 1.

este drum elementar în graful din exemplul 1. 1. 1.

este circuit în graful din exemplul 1. 1. 1.

este circuit elementar în graful din exemplul 1. 1. 1.

Noțiunile de conexitate și de componentă conexă a unui graf orientat sunt similare cu cele de la grafurile neorientate, utilizând noțiunea de lanț din cazul grafurilor orientate.

Definiția 1. 1. 11. Un graf este conex, dacă oricare ar fi două vârfuri ale sale, există un lanț care le leagă.

Exemplul 1. 1. 6. Graful din figura 1. 1. 3. este conex, pentru că oricum am lua două noduri putem ajunge de la unul la celalalt pe un traseu de tip lanț.

Exemplul 1. 1. 7. Graful din figura 1. 1. 4. nu este conex, pentru că de la vârful 2 la vârful 6, nu putem ajunge pe un traseu de tip lanț.

Definiția 1. 1. 12. O componentă conexă C, a unui graf orientat G, se definește ca fiind un subgraf conex maximal al lui G, deci nu există nici un lanț care să unească un vârf din C cu un vârf care nu aparține lui C.

Exemplul 1. 1. 8. În graful din figura 1. 1. 4. distingem două componente conexe:G1 = (X1,U1), unde X1={1, 2, 3}, U1={u1, u2, u3} și G2 = (X2, U2), unde X2={4,5,6}, U2={u4, u5}.

Definiția 1. 1. 13. Un graf orientat G = (X, U) este tare conex dacă pentru oricare două noduri x și y care aparțin lui X, există un drum de la x la y precum și un drum de la y la x.

Exemplul 1. 1. 9. Graful cu n =3 din figura 1. 1. 5. este tare conex.

Pentru a demonstra acest lucru, formăm toate perechile posibile de noduri distincte (x, y) cu x, y Є{1, 2, 3} și pentru fiecare astfel de pereche, căutăm un drum de la x la y și un drum de la y la x.

x =1, y = 2

De la 1 la 2 – drumul (1, 3, 2), pe arcele (1, 3) și (3, 2);

De la 2 la 1 – drumul (2, 3, 1), pe arcele (2, 3) și (3, 1).

x =1, y =3

De la 1 la 3 – drumul (1, 2, 3), pe arcele (1, 2) și (2, 3);

De la 3 la 1 – drumul (3, 2, 1), pe arcele (3, 2) și (2, 1).

x =2, y =3

De la 2 la 3 – drumul (2, 1, 3), pe arcele (2, 1) și (1, 3);

De la 3 la 2 – drumul (3, 1, 2), pe arcele (3, 1) și (1, 2).

Observația 1. 1. 8. Pentru grafurile orientate, conexitatea tare implică conexitatea simplă, adică orice graf tare conex este și conex.

Definiția 1. 1. 14. Se numește componentă tare conexă a grafului , un subgraf al lui G, care este tare conex și este maximal în raport cu incluziunea față de această proprietate, adică subgraful lui G, generat de , nu este tare conex.

Exemplul 1. 1. 10. În graful din figura 1. 1. 4. distingem o componentă tare conexă: G1 = (X1, U1), unde X1={1, 2, 3}, U1={u1, u2, u3}.

Fie un graf orientat și relația binară definită pe X astfel: sau există un drum de la x la y și un drum de la y la x.

Propoziția 1. 1. 1. În codițiile de mai sus are loc:

Relația binară definită mai sus este relație de echivalență;

Clasele de echivalență sunt componente tare conexe ale grafului G.

Demonstrație. a) deoarece de unde avem ca relația binară ~ este reflexivă (1), se mai observă ca dacă atunci sau există un drum de la x la y și un drum de la y la x de unde avem că deci relația binară ~ este simee graf tare conex este și conex.

Definiția 1. 1. 14. Se numește componentă tare conexă a grafului , un subgraf al lui G, care este tare conex și este maximal în raport cu incluziunea față de această proprietate, adică subgraful lui G, generat de , nu este tare conex.

Exemplul 1. 1. 10. În graful din figura 1. 1. 4. distingem o componentă tare conexă: G1 = (X1, U1), unde X1={1, 2, 3}, U1={u1, u2, u3}.

Fie un graf orientat și relația binară definită pe X astfel: sau există un drum de la x la y și un drum de la y la x.

Propoziția 1. 1. 1. În codițiile de mai sus are loc:

Relația binară definită mai sus este relație de echivalență;

Clasele de echivalență sunt componente tare conexe ale grafului G.

Demonstrație. a) deoarece de unde avem ca relația binară ~ este reflexivă (1), se mai observă ca dacă atunci sau există un drum de la x la y și un drum de la y la x de unde avem că deci relația binară ~ este simetrică (2). Fie acum și deducem că sau există un drum de la x la z și un drum de la z la x, adică și deci relația binară ~ este tranzitivă (3). Din (1), (2) și (3) avem că relația binară ~ este o relație de echivalență pe X.

b) Dacă Notăm cu clasa de echivalență a vârfului x în raport cu relația de echivalență ~ , observăm fără dificultate ca graful indus de mulțimea verifică definiția componentei tare conexe a unui graf.

1. 2. Matrici atașate unui graf

Fie G = ( X, U) un graf orientat, finit cu mulțimea vârfurilor X={x, x, . . . , x}.

Definiția 1. 2. 1. Se numește matricea conexiunilor directe (matricea arcelor, matricea de adiacență) asociată grafului G o matrice pătratică de ordin n, notată: , unde:

Observația 1. 2. 1. Valorile matricei conexiunilor directe se pot considera ca valorile booleene și deci elementul precizează dacă perechea de vârfuri este sau nu arc (muchie) în graful reprezentat prin matricea de adiacență A.

Exemplul 1. 2. 1. Fie G = ( X, U) graful din figura 1. 2. 1.

Matricea booleană atașată grafului este:

Definiția 1. 2. 2. Se numește matricea conexiunilor totale (matricea drumurilor) asociată grafului G o matrice notată: , unde:

Exemplul 1. 2. 2. Pentru graful din figura 1. 2. 1. matricea drumurilor este:

Observația 1. 2. 2. Dacă două grafuri au aceeași mulțime de vârfuri și aceeași matrice a arcelor, atunci cele două grafuri coincid.

Dacă două grafuri au aceeași mulțime de vârfuri și aceeași matrice a drumurilor, nu rezultă că cele două grafuri coincid (nu este obligatoriu să aibă și aceleași arce).

Definiția 1. 2. 3. Se numește matricea latină asociată grafului G o matrice pătratică de ordin n, notată: , unde:

Exemplul 1. 2. 3. Pentru graful din figura 1. 2. 1. matricea latină este:

Capitolul II

Algoritmi pentru rezolvarea unor probleme relative la grafuri

2. 1. Algoritmul lui Yu Chen pentru aflarea matricei drumurilor

În asigurarea unor algoritmi relativi la probleme de teoria grafurilor avem nevoie de operațiile de adunare booleană și înmulțire booleană , definite după cum urmează:

Algoritmul lui Yu Chen, are următorii pași:

Etapa 1. Se scrie matricea booleană A a grafului G = (X, U);

Etapa 2. Se adună boolean la prima linie toate liniile corespunzătoare la vârfurile care au cifra 1 pe prima linie. Noile cifre de 1 care apar se notează cu o *.

Etapa 3. Se adună boolean la linia întâi toate liniile corespunzătoare vârfurilor care au cifra 1 pe prima linie. Noile cifre de 1 care apar Se notează cu **. Acest pas se continuă până când nu mai apar cifre noi de 1 pe linia întâi.

Etapa 4. Se aplică pașii 2 și 3 la fiecare din liniile matricei booleene. În final, se obține matricea D a drumurilor. Justificarea algoritmilor este imediată.

Exemplul 2. 1. 1. Pentru graful din figura 1. 2. 1. să aflăm matricea drumurilor, folosind algoritmul lui Yu Chen. Scriem matricea booleană atașată grafului:

Aplicând pașii algoritmului obținem:

care este tocmai matricea găsită la exemplul 1. 2. 2.

2. 2. Algoritmi pentru precizarea existenței circuitelor într-un graf

Vom prezenta doi algoritmi.

Algoritmul notării cu “*”. Pașii acestui algoritm sunt:

Etapa 1. Se notează cu ”*” toate vârfurile fără succesori;

Etapa 2. Notăm cu ”*” toate vârfurile ale căror succesori au fost notați;

Etapa 3. Se continuă procesul de la Etapa 2 pânâ când nu mai putem face notări.

Dacă toate vârfurile au fost notate, atunci graful este fără circuite. În caz că a rămas cel puțin un vârf care nu a fost notat, graful dat are circuite.

Exemplul 2. 2. 1. Să cercetăm dacă graful din figura 2. 1. 1. are circuite.

La Etapa întâi putem nota doar vârful , fiind singurul fără succesori. La Etapa 2 putem nota vârful deoarece succesorul său a fost notat. Nu mai putem face notare de vârfuri deoarece vârfurile râmase au succesori care nu au fost notați. Așadar, graful dat are circuite.

Algoritmul matricei drumurilor. Cum un circuit este un drum ce începe și se termină în același vârf, rezultă că un graf va avea circuite dacă în matricea drumurilor apare cifra 1 pe diagonala principală. Rezultă că, pentru a cerceta dacă un graf are sau nu circuite, este suficient să găsim matricea drumurilor.

Exemplul 2. 2. 2. Să aplicăm acest algoritm la graful din figura 2. 2. 1. Scriem matricea booleană A:

Aplicând algoritmul Yu Chen pentru aflarea matricei drumurilor, obținem:

Având în D de trei ori cifra 1 pe diagonala principală, conchidem că graful are trei circuite.

2. 3. Algoritmi pentru aflarea componentelor tare conexe ale unui graf

Aflarea componentelor tare conexe ale unui graf este importantă pentru practică deoarece se obține o partiție a grafului în subgrafele tare conexe. Proprietatea unui graf de a fi tare conex este foarte importantă, de exemplu, în rețele de comunicații, în cadrul cărora trebuie să se ajungă în orice moment între două puncte ale rețelei.

Algoritmul notării cu ””.

Etapa 1. Se notează cu ”” un vârf în care intră și iese cel puțin câte un arc.

Etapa 2. Se notează cu ”+” vârfurile care sunt extremități finale pentru arce care pleacă dintr-un vârf notat cu ”+” și se notează cu ”–” vârfurile inițiale pentru arce ale căror vârfuri finale sunt notate cu ”–”.

Etapa 3. Se aplică repetat Etapa 2, până nu se mai pot face notări. Dacă toate vârfurile au fost notate cu ””, atunci graful este tare conex, având o sigură componentă tare conexă. Dacă există vârfuri care nu au fost notate cu ””, atunci se consideră mulțimea Cformată din toate vârfurile notate cu ””. Cformează o primă componentă tare conexă.

Etapa 4. În graful dat se elimină vârfurile din componenta Cși toate arcele aferente acestora. Noului graf (de fapt, subgraf al grafului inițial) i se aplică pașii 2–3 până se găsesc toate componentele tare conexe ale grafului.

Pentru a evidenția geometric (intuitiv) descompunerea grafului dat în componente tare conexe se aranjează vârfurile pe componente și se trasează arcele din graful inițial.

Exemplul 2. 3. 1. Să considerăm graful din figura 2. 3. 1.

Deoarece în vârful iese și intră cel puțin câte un arc îl notăm cu ””. Apoi notăm cu ”+” vârfurile și și cu ”–” vârful . Acum notăm cu ”–” vârful și cu ”+” vârfurile , și . Procesul de notare nu mai poate continua, rămânând vârfuri care nu sunt notate cu ””.

Prima componentă tare conexă a grafului este

Suprimăm vârfurile și arcele adiacente lor și obținem graful din figura 2. 3.2.

Imediat se marcheaza cu ”” numai vârfurile și , obținând cea de-a doua componentă tare conexă. Vârful formează cea de-a treia componentă tare conexă, adică .

În figura 2. 3. 3. prezentăm graful cu vârfurile sale împărțite în componente tare conexe.

Algoritmul lui Yu Chen. Acest algoritm pentru aflarea componentelor tare conexe folosește ideea de lucru de la algoritmul lui Chen pentru determinarea matricei drumurilor.

Fie G = ( X, U) un graf orientat, , un vârf fixat al grafului. Notăm cu mulțimea vârfurilor atinse de la și mulțimea vârfurilor care ating pe , adică:

Propoziție 2. 3. 1. Mulțimea de vârfuri este componenta tare conexă care conține vârful .

Demonstrație. Dacă , atunci .

Dacă , atunci fie și , adica există drum de la la și există drum de la la , de unde și sunt mutual atinse, de unde putem deduce că există un drum de la x la y și un drum de la y la x, adică este tare conexă. Trebuie să mai demonstrăm că este maximal, relativ la proprietatea de tare conexiune (dacă mai adăugăm un vârf componentei se pierde această proprietate). Presupunem că nu este maximală. Prin inserarea unui vârf la componenta se pierde proprietatea de tare conexitate. Într-adevăr, vârfurile și nu pot fi mutual atinse, deoarece, în acest caz, vârful s-ar afla deja în componenta . Așadar, este maximală.

Algoritmul lui Yu Chen are următorii pași:

Etapa 1. Se scrie matricea booleană A a grafului G = (X, U).

Etapa 2. Se determină toate drumurile care pleacă din spre alte vârfuri, procedând ca la pașii 2 și 3 de la algoritmul Yu Chen pentru determinarea matricei drumurilor, adică se introduc prin adunare booleană toate cifrele de pe linia întâi. Notăm cu mulțimea vârfurilor care au cifra 1 pe linia întâi astfel obținută.

Etapa 3. Ca la Etapa 2 procedăm pe coloana întâi, determinând toate vârfurile care sunt legate prin drumuri cu . Notăm cu mulțimea vârfurilor care au cifra 1 pe coloana întâi astfel obținută.

Etapa 4. Determinăm prima componentă tare conexă, luând .

Etapa 5. În matricea A se elimină liniile și coloanele care au vârfurile în.

La matricea obținută se aplică, din nou pașii 2–5. Se aplică algoritmul până se epuizează vârfurile grafului.

Observație 2. 3. 1. Mulțimea vârfurilor este pusă în evidență de pozițiile egale cu 1 de pe prima linie a matricei D, iar mulțimea se determină cu ajutorul pozițiilor egale cu 1 de pe prima linie a matricei sau echivalent, de pe prima coloană a matricei D.

Exemplul 2. 3. 2. Să considerăm graful din figura 2. 3. 4. Să-i aflăm componentele tare conexe

Scriem matricea booleană atașată grafului

Determinăm toate legăturile prin drumuri ce pleacă din spre alte vârfuri:

Din tabelul de mai sus deducem că .

Procedăm la fel pe coloana întâi, scriind tabelul, pentru economie de spațiu, tot pe orizontală obținem:

Din tabelul de mai sus deducem ca mulțimea vârfurilor care sunt legate prin drumuri cu este .

Acum găsim prima componentă tare conexă .

Eliminăm în matricea A liniile și coloanele corespunzătoare vârfurilor din și obținem matricea:

Cum pe linia lui în matricea A avem numai cifra 0, deducem că următoarea componentă tare conexă este . Eliminând linia și coloana corespunzătoare vârfului din A, obținem matricea:

Cum pe coloana lui în matricea A avem numai cifra 0, deducem că următoarea componentă tare conexă este . Eliminând linia și coloana corespunzătoare vârfului din A, obținem matricea:

Calculând matricea drumurilor pentru matricea obținrm:

Din observația 2. 3. 1. deducem că și , de unde mai obținem componenta tare conexă .

Observația 2. 3. 2. Deoarece oricare două vârfuri dintr-o componentă tare conexă sunt legate între ele prin drumuri, rezultă că un graf poate fi reprezentat prin unul care are ca vărfuri componentele tare conexe, arcele de legătură, între ele stabilindu-se după arcele din graful dat. În cazul exemplului nostru obținem graful din figura 2. 3. 5. Graful astfel obținut se numește graful condensat atașat grafului dat.

Observația 2. 3. 3. Graful condensat este important în rezolvarea multor probleme practice deoarece reduce dimensiunea sistemelor complexe.

2. 4. Drumuri și circuite hamiltoniene

Una dintre cele mai cunoscute probleme economice este problema comis voiajorului. Comis voiajorul este un individ care trebuie să prezinte s-au să distribuie marfa comandată la o serie de centre distribuite în general neliniar pe o anumită zonă teritorială (localitățile dintr-un județ, magazinele dintr-un cartier, persoanele dintr-un sat etc). Dacă numărul de obiective care trebuie vizitate este mare sau foarte mare iar timpul disponibil foarte limitat atunci devine vitală o asemenea organizare a trecerii pe la fiecare obiectiv încât să se efectueze în timpul minim posibil. Acest timp minim se traduce prin drumul cel mai scurt, iar cel mai scurt drum este evident cel în care se trece pe la fiecare obiectiv o singură dată. În plus, la sfârșit trebuie să se afle în punctul inițial, adică sediul firmei la care lucrează.

O reprezentare a regiunii aprovizionate, în care centrele pe la care se trece sunt vizualizate prin puncte iar căile de acces la acestea prin segmente de curbe, va fi evident un graf, problema reducându-se la a găsi circuitul hamiltonian de lungime minimă.

În timp, s-au evidențiat o multitudine de probleme reductibile la găsirea unui drum (sau circuit) hamiltonian într-un graf, cum ar fi:

Problema poștașului (găsirea traseului cel mai scurt care trece pe la toate locuințele ce aparțin de oficiul poștal la care lucrează acesta);

Problema adunării deșeurilor (cel mai scurt drum care trece pe la toate punctele de depozitate a deșeurilor);

Problema succesiunii operațiilor (executarea mai multor operații pe o mașină în acea ordine în care suma timpilor consumați cu pregătirea mașinii pentru trecerea de la o operație la următoarea să fie minim)

Ordinea lipirii unor componente electronice pe o placă, etc;

Fie G = (X, U) un graf orientat.

Definiția 2. 4. 1. Drum hamiltonian este un drum elementar care trece prin toate nodurile X ale grafului G.

Definiția 2. 4. 2. Circuit hamiltonian este un circuit elementar care trece prin toate nodurile X ale grafului G.

Exemplul 2. 4. 1. În figura 2. 4. 1. se observă că drumul este drum hamiltonian, iar drumul este circuit hamiltonian.

Definiția 2. 4. 3. Putere de atingere a unui nod xi X în graful G este numărul de noduri la care se poate ajunge din xi.

Observația 2. 4. 1. Puterea de atingere a nodului se notează cu p(xi), 1 i n și evident p(xi) .

Exemplul 2. 4. 2. În graful din figura 2. 3. 4. puterea de atingere a unui nodului este , iar

Algoritmul lui Chen pentru determinarea drumurilor hamiltoniene în grafuri fără circuite

Fie G = (X,U) un graf orientat fără circuite, cu n noduri: X = {x1, x2, … , xn}. Vom considera că am calculat matricea drumurilor D și puterile de atingere ale tuturor nodurilor.

Dacă în graful G există un drum de la nodul xi la nodul xj atunci evident p(xi) > p(xj), deoarece în orice vârf în care se poate ajunge din xj se poate ajunge și din xi dar din xj nu se poate ajunge în pentru că nu există circuite.

Teorema 2. 4. 1. (Chen) Un graf cu n noduri, fără circuite conține un drum hamiltonian dacă și numai dacă există relația:

Demonstrație

“” Fie H un drum hamiltonian și presupunem că nodurile grafului au fost notate în ordinea în care apar în acest drum. Atunci din orice nod xi se poate ajunge în toate nodurile cu indice mai mare și numai în acestea (altfel ar exista circuite) și deci puterea unui nod xi este n – i, de unde:

= (n – 1) + (n – 2) + … + 1 + 0 =

“” Ordonând vârfurile în ordinea descrescătoare a puterii lor de atingere (i > j p(xi) < p(xj)) și cum graful nu are circuite, vom obține o matrice D cu zerouri pe diagonala principală și sub diagonala principală (evident pe o poziție (i,i) nu se află nici un 1, deoarece graful n-are circuite, iar dacă ar fi un 1 pe poziția (i,j) cu i > j ar însemna că din xi se poate ajunge în xj, deci în toate nodurile în care se poate ajunge din xj, iar din xj nu se poate ajunge în xi, deci p(xi) > p(xj) în contradicție cu ipoteza de ordonare a nodurilor). Cum deasupra diagonalei principale sunt poziții iar suma puterilor vârfurilor este chiar rezultă că toate pozițiile de deasupra diagonalei sunt 1. Aceasta înseamnă că există toate arcele de forma (xi,xi+1), (altfel n-ar exista drum de la xi la xi+1) și deci drumul hamiltonian (x1, x2, … , xn) q.e.d.

Teorema 2. 4. 2. Dacă într-un graf orientat fără circuite, există un drum hamiltonian, atunci acesta este unic.

Demonstrație:

Deoarece un drum hamiltonian se identifică cu o permutare a nodurilor grafului, existența a două drumuri hamiltoniene implică existența a două permutări distincte a nodurilor grafului și cum două permutări distincte diferă prin cel puțin o inversiune vor exista două noduri xi și xj în ordinea xi xj pe un drum și invers pe celălalt, existând deci un drum atât de la xi la xj cât și de la xj la xi, cele două formând împreună un circuit, în contradicție cu ipoteza.

Pe aceste teoreme se bazează algoritmul lui Chen de determinare a drumului hamiltonian într-un graf orientat fără circuite:

Algoritmul lui Chen

Etapa 1. Se scrie matricea de adiacență A

Etapa 2. Se calculează matricea drumurilor D

Etapa 3. Dacă există un indice i cu dii = 1 atunci graful are circuite, nu se poate aplica algoritmul lui Chen și algoritmul se oprește. Dacă nu, se trece la Etapa 4.

Etapa 4. Se calculează puterile de atingere pentru fiecare nod, astfel la matricea D se mai adaugă o coloană ”p”, pe care se trece numărul de cifre 1 de pe fiecare linie din D. Aceste numere sunt puterile de atingere corespunzătoare vârfurilor grafului

Etapa 5. Dacă nu se verifică relația , atunci graful nu are drumuri hamiltoniene și algoritmul se oprește, altfel se trece la Etapa 6.

Etapa 6. Se ordonează nodurile în ordinea descrescătoare a puterilor lor de atingere și obținem drumul hamiltonian căutat.

Exemplul 2. 4. 3. Fie graful din figura 2. 4. 2. Să cercetăm, folosind algoritmul lui Chen dacă acest graf are drum hamiltonian.

Matricea booleană atașată grafului este:

Matricea drumurilor la care am atașat coloana purerilor de atingere ale vârfurilor este:

Deoarece deducem conform algoritmului lui Chen, că

acest graf admite un drum hamiltonia dat de

Algoritmul Yu Chen pentru grafuri cu circuite.

Acest algoritm are următorii pași:

Etapa 1. Se determină componentele tare conexe ale grafului G = (X, U), notate cu . . .

Etapa 2. Se determină graful condensat asociat grafului G = (X, U), care este un graf fără circuite.

Etapa 3. Se determină drumul hamiltonian în graful condensat, cănd există.

Etapa 4. Se aranjează componentele tare conexe în ordinea dată de drumul hamiltonian determinat la Etapa 3.

Etapa 5. Se scriu toate drumurile hamiltoniene din fiecare componentă tare conexă.

Etapa 7. Stabilim legăturile de la o componentă la alta în funcție de arcele de incidență (legătură) din graful dat, citind apoi toate drumurile hamiltoniene.

Observația 2. 4. 2. Dacă în graful condensat nu există drum hamiltonian sau între două componente nu există legătură, atunci graful nu are drumuri hamiltoniene.

Exemplul 2. 4. 4. Să aflăm drumurile hamiltoniene ale grafului din figura 2. 3. 4. Din exemplul 2. 3. 2. am aflat componentele tare conexe, care sunt: și . Graful condensat atașat grafului din figura 2. 3. 4. este graful din figura 2. 3. 5.

Se observă că in graful condensat avem următorul drum hamiltonian:

Acum, scriem componentele tare conexe în ordinea din drumul și sub ele scriem toate drumurile hamiltoniene din fiecare componentă:

Apoi stabilim legăturile între ultimele vârfuri din drumurile dintr-o componentă și primele vârfuri din componenta următoare (le indicăm prin săgeți).

Obținem drumurile hamiltoniene:

Algoritmul matricilor latine. Vom prezenta un procedeu prin care se pot găsi toate drumurile elementare, deci și cele hamiltoniene, precum și circuitele hamiltoniene.

Definiția 2. 4. 4. Se numește alfabet o mulțime de semne numite simboluri sau litere {si│iI} unde I este o mulțime oarecare de indici, finită sau nu.

Definiția 2. 4. 5. Se numește cuvânt un șir finit de simboluri notat .

Definiția 2. 4. 6. Se numește înmulțire latină o operație definită pe mulțimea cuvintelor unui alfabet, notată "", astfel:

=

(produsul a două cuvinte se obține prin concatenarea lor)

Observația 2. 4. 3. Înmulțirea latină este asociativă, are ca element neutru cuvântul vid, nu e comutativă și un element este inversabil doar dacă este cuvântul vid.

Definiția 2. 4. 7. Se numește adunare latină o funcție definită pe mulțimea cuvintelor unui alfabet cu valori în mulțimea părților mulțimi cuvintelor, notată "" astfel:

=

(suma a două cuvinte este mulțimea formată din cele două cuvinte)

Fie G = (X, U) un graf. Cu ajutorul definițiilor de mai sus putem prezenta pașii algoritmului matricilor latine.

Etapa 1. Construim matricea latină asociată grafului, dată de :

lij =

și matricea , definită prin:

=

numită matricea latină redusă.

Etapa 2. Se calculează succesiv matricile:

L2 = L , L3 = L2 , … ,Lk+1 = Lk

folosind operațiile de înmulțire și adunare latină, alfabetul fiind mulțimea nodurilor grafului, unde operația de înmulțire este ușor modificată, produsul dintre două elemente ale matricilor fiind 0, dacă unul dintre ele este 0 sau au un nod comun și este produsul latin al lor, în caz contrar.

Din felul cum a fost construită, matricea Lk va conține toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (câte are graful cu totul) rezultă că:

primele n-1 puteri ale lui L conțin toate drumurile elementare din graf;

puterile lui L mai mari sau egale cu n au toate elementele egale cu 0;

matricea Ln-1 conține toate drumurile hamiltoniene din graf (dacă există).

Observația 2. 4. 4. Dacă dorim să obținem circuitele hamiltoniene se va calcula , dar admitem, ca excepție, situația de repetare a primului și a ultimului vârf (cel care închide circuitul).

Exemplul 2. 4. 5. Pentru graful din figura 2. 4. 3. vom determina cu ajutorul algoritmului matricelor toate drumurile hamiltoniene

Scriem matricea latină L, iar apoi din ea găsim matricea latină , obținută din matricea latină L prin suprimarea primei litere a elementelor nenule.

Apoi calculăm matricea și obținem:

Urmează să calculăm matricea și obținem:

La final calculăm matricea și obținem:

În concluzie, graful dat mai sus are 6 drumuri hamiltoniene, acestea sunt: , , , , , .

Observația 2. 4. 5. Pentru a obține circuitele hamiltoniene se va calcula , dar acum se admite ca primul și ultimul vârf să se repete. Prin urmare matricea are forma:

În concluzie, graful dat are 5 circuite hamiltoniene:, , , și .

Capitolul III

Rezolvarea unor probleme relative la drumuri de valoare optimă

3. 1. Grafuri valorizate. Principiul optimalității.

Fie G = (X, U) un graf orientat fără bucle, adică .

Definiția 3. 1. 1. Graful G = (X, U) este valorizat dacă există funcția R.

Dacă atunci v(u) se numește valoarea arcului u.

Fie drumul în graful G.

Definiția 3. 1. 2. Se numește valoarea drumului d, numărul

Observația 3. 1. 1. Dacă v(u) = 1 și , rezultă v(d) = k.

Observația 3. 1. 2. Fie a, b X vom nota prin D(a, b) mulțimea drumurilor ce au ca vârf inițial pe a și ca vârf final pe b.

Definiția 3. 1. 3. Se numește drum optim în D(a, b) un drum astfel ca:

unde prin optim vom înțelege maxim sau minim.

Propoziția 3. 1. 1. (Principiul optimalității) Orice subdrum al unui drum optim este optim.

Demonstrație. Fie , drumul de valoare minimă

(optimă) ce conține vârfurile a,X și subdrumurile și ,se observă că . Vom arata că are valoare minimă.

Presupunem prin reducere la absurd că nu are valoare minimă și fie astfel încât , considerăm acum drumul se observă că ceea ce contrazice faptul că d este drumul de

valoare minimă. Prin urmare are valoare minimă.

Fie D(a, c, b) mulțimea drumurilor ce conțin vârfurile a, c, bX. Are loc:

Propoziția 3. 1. 2. Fie și , astfel încât are loc . Drumul d este optim în D(a, c, b) dacă și numai dacă este drum optim în D(a, c) și este drum optim în D(c, b).

Demonstrație. Dacă este drum minimal (optim), iar unde din propoziția 3.1. 1. deducem că este drum optim în D(a, c) și este drum optim în D(c, b).

Fie acum un drum oarecare, considerăm drumurile și . Din minimalitate drumurilor și avem: de unde deducem că drumul este minim.

3. 2. Drumuri optime într-un graf. Algoritmi de găsire a drumului optim

În marea majoritate a problemelor care pot fi modelate prin grafuri nu ne interesează numai dacă există sau nu legături între componentele reprezentate prin nodurile grafului ci și intensitatea acestora. Această intensitate are semnificația unei valori numerice (pozitive sau negative) asociate arcului corespunzător legăturii a cărei intensitate o măsoară.

În aplicațiile economice această valoare poate fi:

lungimea drumului dintre două localități;

costul parcurgerii rutei reprezentate prin arcul corespunzător;

durata parcurgerii rutei respective;

cantitatea transportată pe ruta respectivă;

capacitatea maximă a rutei respective;

câștigul realizat prin trecerea de la o stare la alta a sistemului;

consum de energie pentru efectuarea trecerii respective;

punctaj realizat etc.

Din cauza varietății nelimitate a grafurilor posibile, nu există un algoritm care să rezolve orice problemă în timp util, dar s-au elaborat o mulțime de algoritmi, fiecare fiind cel mai eficace în anumite cazuri. Acești algoritmi pot fi grupați în cinci categorii:

Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);

Algoritmi prin ajustări succesive: (Ford);

Algoritmi prin inducție (Dantzig);

Algoritmi prin ordonare prealabilă a vârfurilor grafului;

Algoritmi prin extindere selectivă (Dijkstra).

În continuare vom prezenta trei dintre acești algoritmi.

3. 2. 1. Algoritmul lui Bellman – Kalaba

Algoritmul se aplică în grafuri finite care nu au circuite de valoare negativă (pentru o problemă de minim) sau care nu au circuite de valoare pozitivă (într-o problemă de maxim) și găsește drumurile de valoare minimă (maximă) de la toate nodurile grafului la un nod oarecare, fixat. Dacă dorim să cunoaștem drumurile de valoare minimă (maximă) între oricare două noduri vom aplica algoritmul, pe rând, pentru fiecare nod al grafului.

Fie unde un graf orientat finit. Presupunem (fără a restrânge generalitatea, că am numerotat nodurile astfel încât nodul spre care căutăm drumurile de valoare minimă (maximă) de la celelalte noduri să fie xn.

Se construiește matricea pătratică M cu dimensiunea egală cu numărul de noduri ale grafului ale cărei elemente sunt:

mij =

Se adaugă succesiv liniile Li la matricea M, elementele acestora calculându-se prin relațiile de recurență:

L1j = mjn j = 1,…,n (prima linie este ultima coloană, transpusă, a matricii M)

Lij = min (Li-1j , (mjk + Li-1k)) într-o problemă de minim

sau Lij = max (Li-1j , (mjk + Li-1k)) într-o problemă de maxim

După calcularea fiecărei linii noi se compară elementele ei cu cele ale precedentei:

Dacă Lij = Li-1,j pentru orice j = 1,…,n atunci se oprește recurența și ultima linie calculată conține valorile minime ale drumurilor de la celelalte noduri la nodul xn.

Dacă există cel puțin un indice j cu Lij Li-1j se trece la calcularea noii linii

Pentru găsirea drumului care dă valoarea minimă de la un nod xj la nodul xn se găsesc, începând înapoi de la ultima linie, pe care s-au obținut valorile finale, notată Lf, nodurile ,, …, care formează drumul căutat, unde =, = și fiecare alt indice ki+1 este cel pentru care s-a obținut minimul(maximul) de pe poziția ki al liniei Li.

Observația 3. 2. 1. Pentru grafuri foarte mari, algoritmul necesită un volum mare de memorie, prin necesitatea memorării matricei M, care este greu de manipulat. Chiar dacă din cele n2 arce posibile graful ar avea doar un procent foarte mic, matricea grafului va avea tot n2 poziții de memorat și analizat.

Exemplul 3. 2. 1. Presupunem dat graful orientat de mai jos, în care se dorește găsirea drumului de valoare minimă de la nodul x1 la nodul x9.

Matricea M va fi

După calcularea liniilor Li obținem:

Deoarece L4 = L5 oprim calcularea liniilor după calcularea liniei 5. În această linie se află valorile celor mai scurte drumuri de la toate nodurile la nodul . Drumul dorit de noi () are valoarea dată de prima poziție a liniei 5, fiind egal cu 13.

Pentru a găsi acest drum, plecăm înapoi de la linia 4 și avem:

3. 2. 2. Algoritmul lui Ford simplificat

Algoritmul lui Ford simplificat se aplică doar în grafuri care nu admit circuite. Cu ajutorul lui se găsește drumul de valoare optimă între două noduri fixate xi și xj. Printr-o eventuală renumerotare a nodurilor putem presupune că nodul de la care pornește drumul este , care va fi numit nod inițial, iar nodul la care se termină este xn, numit nod final.

Algoritmul este:

I se dă vârfului inițial valoarea 0 (zero): w = 0

Se construiește mulțimea A formată din nodul inițial:

Se analizează nodurile din afara mulțimii A.

Dacă există noduri în care se poate ajunge prin arce directe doar de la nodurile mulțimii A, acestea se adaugă la mulțimea A, cu valoarea:

w(xi) = , în problemele de minim

sau

w(xi) = , în problemele de maxim

apoi se trece la Etapa 4

Dacă nu există nici un nod de acest tip atunci nu există nici un drum de la x1 la xn. STOP

Se analizează mulțimea A:

Dacă xn A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de la x1 la xn. Pentru găsirea acestui drum se pornește înapoi de la nodul final xn și se găsesc nodurile ,, …, care formează drumul căutat, unde = xn, = x1 și fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

Dacă xn A se reia algoritmul de la Etapa 3.

Exemplul 3. 2. 2. Pentru același graf, cel din figura 3. 2. 1. și aceeași pereche de noduri și , aplicând algoritmul lui Ford vom avea succesiv:

pas1: w(x1) = 0

pas2:

pas3: Nodurile în care se poate ajunge doar din x1:

pas4:

pas3: și nodurile în care se poate ajunge prin arce directe doar din și sunt:

pas4:

pas3: și nodurile în care se poate ajunge prin arce directe doar din , și sunt:

pas4:

pas3: și nodurile în care se poate ajunge prin arce directe doar din și sunt:

pas4:

pas3: și nodurile în care se poate ajunge prin arce directe doar din și sunt:

pas4:

pas3: și nodurile în care se poate ajunge prin arce directe doar din și sunt:

pas4: și urmează să găsim drumul care are lungimea 13.

Avem succesiv:

deci drumul căutat este:

Observația 3. 2. 2. Dacă graful are un circuit atunci se poate demonstra ușor că nu vom putea da valoare nici unui nod al acestuia și dacă există vreun drum de la la xn care trece prin unul din nodurile circuitului nu vom putea da valoare nici lui xn, cu toate că există drum de la la xn.

Observația 3. 2. 3. Algoritmul necesită pentru memorare și manipulare doar cunoaște-rea, pentru fiecare nod, a nodurilor spre care "pleacă" arce din acesta și valorile acestor arce, fiind mult mai ușor de aplicat sau implementat pe calculator. El are însă dezavantajul că se poate aplica doar în grafuri fără circuite.

3. 2. 3. Algoritmul lui Dijkstra

În algoritmul Ford simplificat, pentru a găsi valoarea nodului final, deci a drumului minim, plecăm de la nodul inițial în toate direcțiile posibile, păstrând de fiecare dată toate nodurile analizate. Acest fapt duce la un consum inutil de timp, deoarece foarte multe din aceste noduri nu vor face parte din drumul optim. Pentru a elimina acest neajuns, algoritmul lui Dijkstra încearcă să păstreze, la fiecare iterație, mulțimea minimă de noduri care să le conțină pe toate cele care vor forma efectiv drumul optim. În plus, algoritmul se poate aplica și în drumuri cu circuite. Ca un minus este faptul că se aplică doar la probleme de minim. Algoritmul are următorii pași:

I se dă vârfului inițial valoarea 0 (zero):

Se construiește mulțimea A formată din nodul inițial:

Se analizează nodurile din afara mulțimii A.

Dacă există noduri în care se poate ajunge prin arce directe de la noduri din A (nu doar de la nodurile mulțimii A, ca la algoritmul lui Ford simplificat) se calculează pentru toate acestea:

w(xi) = în problemele de minim dar, spre deosebire de

algoritmul lui Ford simplificat, se adaugă la mulțimea A doar cel pentru care se obține valoarea minimă, apoi se trece la Etapa 4.

Dacă nu există nici un nod de acest tip, atunci nu există nici un drum de la x1 la xn. STOP

Se analizează mulțimea A:

Dacă xn A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de la x1 la xn. Pentru găsirea acestui drum se pornește înapoi de la nodul final xn și se găsesc nodurile ,, …, care formează drumul căutat, unde = xn, = x1 și fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

Dacă xn A se reia algoritmul de la Etapa 3.

Exemplul 3. 2. 3. Vom aplica algoritmul lui Dijkstra la același graf, cel din figura 3. 2. 1. folosit la ceilalți algoritmi, pentru a putea face comparații:

pas1:

pas2:

pas3: Mulțimea nodurilor în care se poate ajunge și din este:

pas4:

pas3: și mulțimea nodurilor în care se poate ajunge prin arce directe din sau este:

pas4:

pas3: și mulțimea nodurilor în care se poate ajunge prin arce directe din , sau este:

pas4:

pas3: și mulțimea nodurilor în care se poate ajunge prin arce directe din , , , și este:

pas4:

pas3: și mulțimea nodurilor în care se poate ajunge prin arce directe din și este:

pas4:

pas3: și mulțimea nodurilor în care se poate ajunge prin arce directe din și este:

pas4: x9 A și urmează să găsim drumul optim care are lungimea 13.

Avem succesiv:

deci drumul căutat este:

Concluzii

Teoria grafurilor, prin aplicarea algoritmilor combinatoriali, este folosită pentru aflarea drumului cel mai scurt și mai eficient ca și in problema comis voiajerul cand trebuie să livreze marfa de la distribuitori la clienți. Deci intreprinderile de livrări de marfă pot să folosească această strategie pentru ușurarea munci lor. Sau problema poștașului care trebuie să găsească drumul cel mai scurt și mai rapid de la o adresă la alta să livreze scrisorile.

Acești algoritmi sunt foarte utili pentru aceste probleme și sunt eficienți pentru reducerea timpului de livrare.

Mai pot fi folosiți pentru harta traseurilor autobuzelor în transportul de personae pentru găsirea traseurilor acestora, pentru unirea cât mai multor puncte puternic populate.

Grafurile au o importață imensă în informatică, de exemplu: în unele probleme de sortare și căutare-elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri într-un graf sau schema logică a unui program se poate reprezenta print-un graf orientat în care o instrucțiune sau un bloc de instrucțiuni este reprezentat print-un nod, iar muchiile direcționate reprezintă calea de execuție sau in programare orientată pe obiect, ierarhia obiectelor(claselor) imio program poate fi reprezentată printr-un graf în care fiecare nod reprezintă o clasă, iar muchiile reprezintă relații între acestea.

Teoria grafurilor ne va ajuta să rezolvăm o parte din problemele cu care ne confruntăam în viața noastră zilnică, problemele rezolvate mai sus sau altele cum ar fi: rețeaua de apă, rețeaua de canalizare, un traseu montan, vizitarea mănăstirilor din țara, etc. În această situație ne ajută să gasim un traseu cu costul cel mai mic și într-un timp rezonabil.

În concluzie spunem că teoria grafurilor a fost descoperită pentru a ne ușura viața și pentru a realize unele lucruri cât mai rapid și cât mai eficient și cu costuri minime.

Anexa

Anexa 1

Obtinerea arborelui partial de cost minim folosind algoritmul lui Kruskal

Fie un graf neorientat conex. Fiecărei muchii u îi asociem un cost c(u)>0. Problema constă în a determina un graf parțial conex A=(X,Δ) astfel încat suma costurilor muchiilor din Δ să fie minimă.

Observăm că graful parțial de cost minim este chiar un arbore. Într-adevăr, A este conex. Dacă A ar conține un ciclu, atunci eliminând o muchie oarecare din acest ciclu, obținem tot un graf parțial conex, având însă un cost mai mic. Rezultă că A este un arbore.

Problema enunțată se mai numește problema conectării orașelor cu cost minim, deoarece putem să plecăm de la un graf complet în care cele n vârfuri reprezintă orașe; costul unei muchii (i,j) reprezintă costul conectării directe a orașelor i și j. Un arbore parțial de cost minim reprezintă modalitatea optimă (din punctul de vedere al constructorului) de la lega direct perechi de orașe astfel încât în final orice oraș să fie conectat direct sau indirect cu toate celelalte.

Metoda Greedy permite construirea arborelui parțial de cost minim muchie cu muchie astfel: se alege întâi muchia de cost minim, iar apoi se adaugă repetat muchia de cost minim nealeasă anterior și care nu formează cu precedentele un ciclu. Vom alege astfel n-1 muchii, obținând un graf conex cu n-1 vârfuri, care este deci arbore. Evident, va mai trebui demonstrat că arborele astfel construit este de cost minim. Algoritmul de mai sus este datorat lui Kruskal.

Vom presupune că muchiile apar într-o matrice MAT cu m linii și trei coloane; fiecare linie corespunde unei muchii, primele două elemente reprezentând extremitățile muchiei, iar al treilea reprezentând costul atașat muchiei. Vom presupune că în MAT muchiile apar în ordinea crescătoare a costului atașat lor.

Înainte de a vedea cum se verifică dacă o nouă muchie formează împreună cu precedentele muchii alese un ciclu, vom considera un exemplu.

Observăm că la fiecare pas în algoritmul lui Kruskal ia naștere o pădure, obținută din pădurea precedentă unind doi arbori. Pădurea inițială este formată din n arbori, fiecare constând dintr-un singur vârf

Pentru a soluționa problema apariției unui ciclu prin inserarea unei muchii, o modalitate eficientă este aceea de a memora pentru fiecare vârf tatăl său TATA(i) în pădurea curentă. Atunci în momentul în care muchia (i,j) devine candidată la inserarea ei în arborele parțial de cost minim, pentru a determina dacă ea formează cu precedentele un ciclu este suficient să verificăm dacă i și j fac parte din același arbore; în caz negativ vom adăuga muchia respectivă, ceea ce revine la unirea a doi arbori cu ajutorul procedurii REUN1.

Observație. Arborele reprezentat prin vectorul TATA, rezultat în urma execuției procedurii Kruskal, nu este parțial de cost minim; într-adevăr, la inserarea unei muchii (i,j), pentru pădurea curentă se unesc nu vârfurile i și j, ci rădăcinile arborilor ce le conțin.

În procedura KRUSKAL care urmează presupunem pentru simplificare că muchiile au atașate drept costuri valori întregi.

procedure KRUSKAL(n, m, MAT, COST, TATA)

integer MAT(m, 3), TATA(n)

for i = 1, n

TATA(i) ← –1

repeat

j ← 1; COST ← 0

for j= 1, m –1

do

if i > m then write ‘NU’;

return

endif

i1 ← MAT(j, 1);

i2 ← MAT(j, 2);;

call APART(i1, TATA, n, t1)

call APART(i2, TATA, n, t2)

if t1 = t2 then call REUN1(t1, t2, TATA, n);

write MAT(j, 1), MAT(j, 2)

COST ← COST + MAT(j, 3);

j ← j + 1;

exit

endif

j←j+1

repeat

write COST;

return

end

Să trecem la analiza timpului necesitat de algoritm. Ordonarea celor m muchii în ordinea crescătoare a costurilor atașate necesită timpul O(m log2 m). Investigarea celor m muchii necesită un timp proporțional cu m log2 n, conform timpului de lucru al procedurii APART. În plus, de n-1 ori se execută calculele corespunzătoare lui , care necesită un timp constant. Cum , va rezulta că procedura KRUSKAL are o eficacitate de ordinul O(m log2 m). Am ținut cont că datele de intrare sunt construite din m, n și MAT, deci au lungimea 3m+2.

Mai rămâne să demonstrăm corectitudinea procedurii KRUSKAL.

Propoziție. Algoritmul lui Kruskal furnizează un arbore de cost minim.

Fie u1, u2, …, un-1 muchiile alese – în această ordine – de algoritmul Kruskal. Vom nota Uk={u1,…,uk}. Fie v1, …, vn-1 muchiile unui arbore de cost minim și fie Vk={v1, …, vk}. Presupunem . Demonstrăm că c(ui)=c(vi) pentru orice i=1,…,n-1. Într-adevăr, în caz contrar, fie k primul indice pentru care. Să considerăm graful . Evident G' va conține un ciclu și numai unul, ciclu care va conține o muchie (în caz contrar cu muchiile din Uk s-ar putea forma un ciclu, ceea ce nu este posibil). Eliminând această muchie, vom obține un arbore . Evident , în caz contrar algoritmul alegând drept uk pe vj. Nu putem avea însă deoarece atunci costul lui G'' va fi mai mic decât cel minim. De aceea rezultă și am obținut G'' de cost minim în care primele k componente au aceeași valoare cu cele din Uk. Contradicție.

Anexa 1.1

Cod sursa Algoritm Kruskal

Project Client

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace Kruskal

{

public partial class frmCost : Form

{

public int _cost;

public frmCost()

{

InitializeComponent();

}

private void btnOk_Click(object sender, EventArgs e)

{

if (txtCost.Text == string.Empty)

{

errorProvider1.SetError(txtCost, "Care este costul?");

}

else

{

_cost = int.Parse(txtCost.Text);

this.Close();

}

private void txtCost_KeyPress(object sender, KeyPressEventArgs e)

{

e.Handled = !Char.IsDigit(e.KeyChar);

}

namespace Kruskal

{

partial class frmCost

{

/// <summary>

/// Required designer variable.

/// </summary>

private System.ComponentModel.IContainer components = null;

/// <summary>

/// Clean up any resources being used.

/// </summary>

/// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>

protected override void Dispose(bool disposing)

{

if (disposing && (components != null))

{

components.Dispose();

}

base.Dispose(disposing);

}

#region Windows Form Designer generated code

/// <summary>

/// Required method for Designer support – do not modify

/// the contents of this method with the code editor.

/// </summary>

private void InitializeComponent()

{

this.components = new System.ComponentModel.Container();

this.btnOk = new System.Windows.Forms.Button();

this.txtCost = new System.Windows.Forms.TextBox();

this.errorProvider1 = new System.Windows.Forms.ErrorProvider(this.components);

((System.ComponentModel.ISupportInitialize)(this.errorProvider1)).BeginInit();

this.SuspendLayout();

//

// btnOk

//

this.btnOk.Location = new System.Drawing.Point(30, 35);

this.btnOk.Name = "btnOk";

this.btnOk.Size = new System.Drawing.Size(75, 23);

this.btnOk.TabIndex = 1;

this.btnOk.Text = "&Ok";

this.btnOk.UseVisualStyleBackColor = true;

this.btnOk.Click += new System.EventHandler(this.btnOk_Click);

//

// txtCost

//

this.txtCost.Location = new System.Drawing.Point(17, 7);

this.txtCost.Name = "txtCost";

this.txtCost.Size = new System.Drawing.Size(100, 20);

this.txtCost.TabIndex = 0;

this.txtCost.KeyPress += new System.Windows.Forms.KeyPressEventHandler(this.txtCost_KeyPress);

//

// errorProvider1

//

this.errorProvider1.ContainerControl = this;

//

// frmCost

//

this.AcceptButton = this.btnOk;

this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);

this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;

this.ClientSize = new System.Drawing.Size(141, 63);

this.ControlBox = false;

this.Controls.Add(this.txtCost);

this.Controls.Add(this.btnOk);

this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle;

this.MaximizeBox = false;

this.MinimizeBox = false;

this.Name = "frmCost";

this.StartPosition = System.Windows.Forms.FormStartPosition.CenterScreen;

this.Text = "Cost";

((System.ComponentModel.ISupportInitialize)(this.errorProvider1)).EndInit();

this.ResumeLayout(false);

this.PerformLayout();

}

#endregion

private System.Windows.Forms.Button btnOk;

private System.Windows.Forms.TextBox txtCost;

private System.Windows.Forms.ErrorProvider errorProvider1;

}

namespace Kruskal

{

partial class frmMain

{

/// <summary>

/// Required designer variable.

/// </summary>

private System.ComponentModel.IContainer components = null;

/// <summary>

/// Clean up any resources being used.

/// </summary>

/// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>

protected override void Dispose(bool disposing)

{

if (disposing && (components != null))

{

components.Dispose();

}

base.Dispose(disposing);

}

#region Windows Form Designer generated code

/// <summary>

/// Required method for Designer support – do not modify

/// the contents of this method with the code editor.

/// </summary>

private void InitializeComponent()

{

this.panel1 = new System.Windows.Forms.Panel();

this.butonRezolva = new System.Windows.Forms.Button();

this.butonReseteaza = new System.Windows.Forms.Button();

this.SuspendLayout();

//

// panel1

//

this.panel1.BackColor = System.Drawing.Color.White;

this.panel1.Location = new System.Drawing.Point(12, 12);

this.panel1.Name = "panel1";

this.panel1.Size = new System.Drawing.Size(524, 429);

this.panel1.TabIndex = 0;

this.panel1.Paint += new System.Windows.Forms.PaintEventHandler(this.panel1_Paint);

this.panel1.MouseClick += new System.Windows.Forms.MouseEventHandler(this.panel1_MouseClick);

//

// butonRezolva

//

this.butonRezolva.Location = new System.Drawing.Point(576, 341);

this.butonRezolva.Name = "butonRezolva";

this.butonRezolva.Size = new System.Drawing.Size(75, 23);

this.butonRezolva.TabIndex = 1;

this.butonRezolva.Text = "&Rezolva";

this.butonRezolva.UseVisualStyleBackColor = true;

this.butonRezolva.Click += new System.EventHandler(this.butonRezolva_Click);

//

// butonReseteaza

//

this.butonReseteaza.Location = new System.Drawing.Point(576, 34);

this.butonReseteaza.Name = "butonReseteaza";

this.butonReseteaza.Size = new System.Drawing.Size(75, 23);

this.butonReseteaza.TabIndex = 2;

this.butonReseteaza.Text = "&Reseteaza";

this.butonReseteaza.UseVisualStyleBackColor = true;

this.butonReseteaza.Click += new System.EventHandler(this.butonReseteaza_Click);

//

// frmMain

//

this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);

this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;

this.BackColor = System.Drawing.SystemColors.ControlLight;

this.ClientSize = new System.Drawing.Size(694, 453);

this.Controls.Add(this.butonReseteaza);

this.Controls.Add(this.butonRezolva);

this.Controls.Add(this.panel1);

this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle;

this.MaximizeBox = false;

this.Name = "frmMain";

this.StartPosition = System.Windows.Forms.FormStartPosition.CenterScreen;

this.Text = "Kruskal Algorithm";

this.ResumeLayout(false);

}

#endregion

private System.Windows.Forms.Panel panel1;

private System.Windows.Forms.Button butonRezolva;

private System.Windows.Forms.Button butonReseteaza;

}

using System;

using System.Collections.Generic;

using System.Drawing;

using System.Windows.Forms;

namespace Kruskal

{

public partial class frmMain : Form

{

#region Member Variables

const int _radius = 20;

const int _halfRadius = (_radius / 2);

Color culoarepunct = Color.Aqua;

Color culoaremuchie = Color.Red;

IList<Punct> varfuri;

IList<Muchie> _graph, _graphSolved;

Punct _primpunct, _urmpunct;

bool deseneazamuchie, _rezolvat;

#endregion

public frmMain()

{

InitializeComponent();

Clear();

}

#region Events

private void panel1_MouseClick(object sender, MouseEventArgs e)

{

Point clicked = new Point(e.X – _halfRadius, e.Y – _halfRadius);

if (Control.ModifierKeys == Keys.Control)//daca Ctrl este apasat

{

if (!deseneazamuchie)

{

_primpunct = SelecteazaPunct(clicked);

deseneazamuchie = true;

}

else

{

_urmpunct = SelecteazaPunct(clicked);

deseneazamuchie = false;

if (_primpunct != null && _urmpunct != null && _primpunct.Name != _urmpunct.Name)

{

frmCost formCost = new frmCost();

formCost.ShowDialog();

Point stringPoint = GetStringPoint(_primpunct.Position, _urmpunct.Position);

_graph.Add(new Muchie(_primpunct, _urmpunct, formCost._cost, stringPoint));

panel1.Invalidate();

}

else

{

varfuri.Add(new Punct(varfuri.Count, clicked));

panel1.Invalidate();

}

private void panel1_Paint(object sender, PaintEventArgs e)

{

Graphics g = e.Graphics;

DeseneazaVarfuri(g);

DeseneazaMuchii(g);

g.Dispose();

}

private void butonRezolva_Click(object sender, EventArgs e)

{

if (varfuri.Count > 2)

{

if (_graph.Count < varfuri.Count – 1)

{

MessageBox.Show("Lipsa muchii", "Atentie", MessageBoxButtons.OK, MessageBoxIcon.Exclamation);

}

else

{

butonRezolva.Enabled = false;

IKruskal kruskal = new Kruskal();

int totalCost;

_graphSolved = kruskal.Solve(_graph, out totalCost);

_rezolvat = true;

panel1.Invalidate();

MessageBox.Show("Costul total: " + totalCost.ToString(), "Solutie", MessageBoxButtons.OK, MessageBoxIcon.Information);

}

private void butonReseteaza_Click(object sender, EventArgs e)

{

DialogResult dr = MessageBox.Show("Reseteaza ?", "Atentie!", MessageBoxButtons.YesNo, MessageBoxIcon.Exclamation);

if (dr == DialogResult.Yes)

{

butonRezolva.Enabled = true;

Graphics g = panel1.CreateGraphics();

g.Clear(panel1.BackColor);

Clear();

}

#endregion

#region Private Methods

private void DeseneazaMuchii(Graphics g)

{

Pen p = new Pen(culoaremuchie);

var muchii = _rezolvat ? _graphSolved : _graph;

foreach (Muchie e in muchii)

{

Point v1 = new Point(e.V1.Position.X + _halfRadius, e.V1.Position.Y + _halfRadius);

Point v2 = new Point(e.V2.Position.X + _halfRadius, e.V2.Position.Y + _halfRadius);

g.DrawLine(p, v1, v2);

DrawString(e.Cost.ToString(), e.StringPosition, g);

}

private void DrawString(string strText, Point pDrawPoint, Graphics g)

{

Font drawFont = new Font("Arial", 15);

SolidBrush drawBrush = new SolidBrush(Color.Black);

g.DrawString(strText, drawFont, drawBrush, pDrawPoint);

}

private void DeseneazaVarfuri(Graphics g)

{

Pen p = new Pen(culoarepunct);

Brush b = new SolidBrush(culoarepunct);

foreach (Punct v in varfuri)

{

g.DrawEllipse(p, v.Position.X, v.Position.Y, _radius, _radius);

g.FillEllipse(b, v.Position.X, v.Position.Y, _radius, _radius);

DrawString(v.Name.ToString(), v.Position, g);

}

private Punct SelecteazaPunct(Point pClicked)

{

foreach (Punct v in varfuri)

{

var distance = Distanta(v.Position, pClicked);

if (distance <= _radius)

{

return v;

}

return null;

}

private double Distanta(Point start, Point end)

{

return Math.Sqrt(Math.Pow(start.X – end.X, 2) + Math.Pow(start.Y – end.Y, 2));

}

private Point GetStringPoint(Point start, Point end)

{

int X = (start.X + end.X) / 2;

int Y = (start.Y + end.Y) / 2;

return new Point(X, Y);

}

private void Clear()

{

varfuri = new List<Punct>();

_graph = new List<Muchie>();

_rezolvat = false;

_primpunct = _urmpunct = null;

}

#endregion

}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Windows.Forms;

namespace Kruskal

{

static class Program

{

/// <summary>

/// The main entry point for the application.

/// </summary>

[STAThread]

static void Main()

{

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false);

Application.Run(new frmMain());

}

Project Kruskal

namespace Kruskal

{

using System.Collections.Generic;

public interface IKruskal

{

IList<Muchie> Solve(IList<Muchie> graph, out int totalCost);

}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Drawing;

namespace Kruskal

{

public class Muchie : IComparable

{

#region Members

private Punct v1, v2;

private int cost;

private Point stringPosition;

#endregion

#region Public Properties

public Punct V1

{

get

{

return v1;

}

public Punct V2

{

get

{

return v2;

}

public int Cost

{

get

{

return cost;

}

public Point StringPosition

{

get

{

return stringPosition;

}

#endregion

#region Constructor

public Muchie(Punct v1, Punct v2, int cost, Point stringPosition)

{

this.v1 = v1;

this.v2 = v2;

this.cost = cost;

this.stringPosition = stringPosition;

}

#endregion

#region IComparable Members

public int CompareTo(object obj)

{

Muchie e = (Muchie)obj;

return this.cost.CompareTo(e.cost);

}

#endregion

}

using System;

using System.Drawing;

namespace Kruskal

{

public class Punct

{

#region Members

private int name;

#endregion

#region Public Properties

public int Name

{

get

{

return name;

}

public int Rang { get; set; }

public Punct Origine { get; set; }

public Point Position { get; set; }

#endregion

#region Constructor

public Punct(int name, Point position)

{

this.name = name;

this.Rang = 0;

this.Origine = this;

this.Position = position;

}

#endregion

#region Methods

internal Punct GasesteOrigine()

{

if (this.Origine != this)//sunt unicul parinte ? (sunt unica origine ?)

{

this.Origine = this.Origine.GasesteOrigine();// Nu? atunci gaseste-mi originea.

}

return this.Origine;

}

internal static void Join(Punct origine1, Punct origine2)

{

if (origine2.Rang < origine1.Rang)// rangul originine2 este mai mic decat rangul origine2?

{

origine2.Origine = origine1;//da! atunci origine1 este parintele origine2.

}

else // rangul origine2 este mai mare sau egal cu origine1

{

origine1.Origine = origine2;//faceti-l pe origine2 parinte

if (origine1.Rang == origine2.Rang)// ambele ranguri sunt egale?

{

origine2.Rang++;//incrementeaza origine2, trebuie sa ajungem la o singura origine pentru tot arborele

}

#endregion

}

namespace Kruskal

{

using System.Collections.Generic;

using System.Linq;

public class Kruskal : IKruskal

{

#region IKruskal

IList<Muchie> IKruskal.Solve(IList<Muchie> graph, out int totalCost)

{

QuickSort(graph, 0, graph.Count – 1);

IList<Muchie> solvedGraph = new List<Muchie>();

totalCost = 0;

foreach (Muchie ed in graph)

{

Punct origine1 = ed.V1.GasesteOrigine();

Punct origine2 = ed.V2.GasesteOrigine();

if (origine1.Name != origine2.Name)

{

totalCost += ed.Cost;

Punct.Join(origine1, origine2);

solvedGraph.Add(ed);

}

return solvedGraph;

}

#endregion

#region Private Methods

private void QuickSort(IList<Muchie> graph, int left, int right)

{

int i, j, x;

i = left; j = right;

x = graph[(left + right) / 2].Cost;

do

{

while ((graph[i].Cost < x) && (i < right))

{

i++;

}

while ((x < graph[j].Cost) && (j > left))

{

j–;

}

if (i <= j)

{

Muchie y = graph[i];

graph[i] = graph[j];

graph[j] = y;

i++;

j–;

}

while (i <= j);

if (left < j)

{

QuickSort(graph, left, j);

}

if (i < right)

{

QuickSort(graph, i, right);