Metode Eficiente de Solutionare a Problemelor de Amplasare

Sumar

Introducere

Capitolul 1. Notiuni introductive

§ 1.1 Graful orientate și neorientat

§ 1.2 Subgrafuri

§ 1.3 Lanțuri și cicluri

§ 1.4 Metrica în grafurile neorientate

§ 1.5 Reprezentări ale grafurilor

Capitolul 2. Amplasarea centrelor în graf

§ 2.1 Centrul și raza grafului

§ 2.2 Centrul absolut

§ 2.3 Algoritmi de căutare a centrelor absolute

2.3.1 Metoda Hakimi

2.3.2. Metoda iterativă

§ 2.4 Centre multiple

§2.5. Centre multiple absolute

§2.6. Problema centrului pentru unele clase de grafuri neorientate

Capitolul 3. Amplasarea medianelor în graf

§3.1. Mediana grafului

§3.2. Mediane multiple

§3.3. Mediane absolute

§3.4. Metode de rezolvare a probleme p-medianei

3.4.1. Formularea problemei în termenii programării liniare

3.4.2. Algoritmul branch and bound

3.4.3. Algoritmul euristic

CONCLUZII

BIBLIOGRAFIE

Anexă

Introducere

În activitatea practică permanent apare problema amplasșrii cât mai optime. Astfel, dacă graful reprezintă rețeaua de drumuri ce unește careva localități (vârfurile grafului) atunci poate fi cercetată problema amplasării optimale a spitalelor, secțiilor de poliție, unităților de pompieri sau a altelor centre de deservire. Pentru a rezolva această problemă folosim două compartimente ale Teoriei Grafurilor, care se numesc Amplasarea centrelor în graf și Amplasarea medianelor în graf.

Teoria Grafelor este o ramură a matematicii, relativ tânără : prima lucrare a teoriei grafelor a fost scrisă de Euler acum două secole. Studiul acestei teorii a fost stimulat de aparitia în 1936, la Lipzig, a cărtii lui D. Konig de ”Teoria Grafelor orientate si neorientate”.

Printre matematicienii care au adus contributii importante în domeniul teoriei grafelor în ultimele decenii sunt : O. Ore, C. Berge, F. Harary, P. Erdos, W. Tutte.

Un șir de probleme cu caracter aplicativ se reduc la găsirea locului amplasării optime în graf astfel încât suma distanțelor de la acest centru până la celelalte vârfuri ale grafului să fie cât mai minimală posibilă. Vârful grafului care corespunde amplasării optimale se numește mediana grafului. Astfel de probleme deseori apar în practică. De exemplu, în cazul determinării locului pentru amplasarea stației telefonice într-o rețea telefonică, a stației de distribuire a unei rețele electrice, a depozitelor într-o rețea de drumuri (în ultimul caz vârfurile grafului reprezintă consumatorii), etc.

În acestă lucrare este prezentat rolul centrului si medianei unui graf în soluționarea problemei de amplasare. Asa cum deseori este nevoie de a amplasa careva puncte de deservire într-o oarecare regiune,astfel încât ele să se afle mai aproape de centrul ei,rolul atât centrului cât si a medianei este foarte important.

Capitolul 1. Notiuni introductive

§1.1. Grafuri orientate si neorientate

În general, o multime , de puncte sau vârfuri, și o aplicație , a mulțimii , în ea însăși, o definim un graf pe care îl vom nota . Deoarece aplicația este reprezentată simbolic prin arce orientate, graful mai poate fi pus în evidentă de cuplul format din mulțimea a vârfurilor și multimea a arcelor, adică .

Dacă într-un graf numărul vârfurilor sale, notat prin , este finit, atunci graful se numeste graf finit.

Graful definit pe multimea a vârfurilor sale și de multimea a muchiilor sale se numeste graf neorientat.

De exemplu în figura 1.1 desi există 5 arce, nu avem decât 3 muchii, deoarece arcele si conduc la o singură muchie, iar bucla nu este o muchie. Prin buclă se întelege un arc a cărui extremitate initială coincide cu extremitatea finală.

Fig.1.1

Elementele multimii se numesc vârfuri, iar elementele multimii – muchii ale grafului.

Reprezentarea grafică se poate desena în plan, reprezentând vârfurile sale prin puncte si muchii( arcele ) prin linii care unesc anumite perechi de puncte. La grafurile orientate se pun și săgesi pe arce, care indică sensul de deplasare.

Un exemplu de graf neorientat este dat în figura 1.2 :

2

4

1

3

Fig. 1.2 5

Graful pentru care , se numeste . Se mai spune că graful cu vârfuri este graf de ordin n. Pentru a specifica, că și sunt mulțimi de vârfuri și respectiv muchii ale unui graf vom utiliza notațiile și .

De exemplu un graf are ca mulțime de vârfuri , iar mulțimea .

Acest graf este reprezentat în figura 1.3.

Fig 1.3

se numeste , deoarece două vârfuri care apar într-o pereche de vârfuri din U nu formează o pereche ordonată,nici unul din ele nefiind privilegiat în raport cu celălalt.

Dacă o muchie este determinată de perechea de vârfuri atunci vom scrie . În acest caz si se numesc extremitati ale muchiei , iar însă si vârfurile se numesc adiacente. Se spune că fiecare din vârfurile si este incident muchiei si reciproc. Adiacenta dintre si se notează prin . Două muchii se numesc adiacent dacă sunt incidente unui vârf comun.

Dacă este un vârf al grafului , atunci mulțimea se numeste și se notează sau mai simplu . Grad sau valensa vârfului este cardinalul multimii și se notează prin sau .

Graful, oricare două vârfuri ale caruia sunt adiacente, se numeste graf complet și se notează prin Kn. Numarul de muchii ale lui Kn este:

.

Graful G = (X;U) cu se numeste graf vid și se noteaza prin On, iar graful, pentru care

|X| = 1, U = se numeste graf trivial. Dacă , și fiecare muchie a grafului G = (X; U) are o extremitate în X1, iar alta în X2, atunci graful G se numeste bipartit și se notează prin G = (X1,X2;U). Graful bipartit, în care fiecare vârf din X1 este adiacent cu fiecare vârf din X2 se numeste graf bipartit complet.

Un exemplu de graf complet este arătat în figura 1.5 :

Fig 1.5

Conform definiției grafului neorientat mulțimea UG ar putea să contină muchii ale caror extremităti coincid. Astfel de muchii se numesc bucle. De asemenea, o pereche de vârfuri poate fi prezentă de mai multe ori în UG. În acest caz mulțimea de muchii determinate de aceeași pereche de vârfuri se mai numeste muchie multiplă. Graful, ce contine bucle și muchii multiple se numeste pseudograf, iar graful ce conține bucle se numeste multigraf.

Graful G = (X ;U) se numeste orientat, daca U este o multime de perechi ordonate de elemente din X . Graful orientat se noteaza prin . Elementele multimii se numesc arce. Pentru arcul = (x, y) vârful x este extremitate initială, iar y – extremitate finală. Se spune că arcul = (x, y) este orientat de la x spre y . Vârful X se mai numeste predecesorul vârfului y , iar y – succesorul vârfului X .

Din definiția grafului orientat rezultă că perechile de vârfuri si reprezintă arce diferite. Graful orientat , care pentru orice doua vârfuri , nu contine în acelasi timp arcele si se numeste antisimetric, iar graful antisimetric cu un număr maxim de arce se numeste turnir.

Un exemplu de graf orientat este dat în figura 1.6 :

5

1

4 6

2

Fig 1.6

1

2 5 2 5

3 4 3 4

Fig. 1.7 Fig. 1.8

În cazul când XH = XG graful H se numeste subgraf parțial al grafului G, deci un graf parțial al unui graf G se obține din G prin suprimarea anumitor legături dintre vârfurile lui G.

De exemplu graful din figura 1.9 este graf partial al grafului din figura 1.7.

1

2 5

3 4

Fig. 1.9

Fie graful din figura 1.10. Extremitatea initial x se numeste precedesorul vârfului y, iar y se numeste succesorul vârfului x.

y

v

x

Fig 1.10

Prin vom nota multimea succesorilor vârfului x, iar – multimea predecesorilor vârfului x.

Prin notăm multimea arcelor de intrare pentru x,iar prin multimea arcelor de iesire pentru vârful x.

Este evident că : si .

Numărul se numeste semigrad de intrare al vârfului x.

Numărul se numeste semigrad de ieșire al vârfului x.

Numărul se numeste grad al vârfului x.

Într-un graf neorientat, graful unui vârf x, notat d(x) , este numărul muchiilor care se leagă de vârful x.

De exemplu pentru graful din figura 1.7 obtinem d(1)=2,d(2)=3,d(3)=3,d(4)=3,d(5)=3.

Prin definitie un vârf izolat este unul care are gradul zero,adică nu se leagă prin muchii de nici un alt vârf.Se numeste vârf suspendat, vârful care are gradul 1.

§ 1.2 Subgrafuri

Vom utiliza în continuare notiunile de subgraf/subgraf partial al grafului .

Un graf se numește subgraf al grafului , generat de submulțimea de vârfuri, dacă

1) ;

2) două vârfuri sunt adiacente în H dacă și numai dacă ele sunt adiacente în G

Conform definiției, orice graf poate fi considerat drept subgraf al său.

Un graf se numește subgraf parțial al grafului , dacă iar .

§ 1.3 Lanturi si cicluri

O succesiune de vârfuri se numește lanț în graful , dacă . În acest caz, se spune că lanțul unește vârfurile . Vom considera că o muchie din aparține lanțului , dacă și numai dacă și sunt vârfuri vecine în , adică și (sau invers). Vârfurile se numesc extremități ale lanțului, iar numărul – lungimea lui. Dacă atunci se numește ciclu.

Lanțul, ce conține fiecare muchie a grafului cel mult o singură dată se numește lanț simplu, iar lanțul, toate vârfurile căruia sunt distincte două câte două, se numește lanț elementar.

Ciclul ce conține fiecare muchie a grafului cel mult o singură dată se numește ciclu simplu, iar ciclul, toate vârfurile căruia sunt distincte două câte două, se numește ciclu elementar.

Nu orice graf conține cicluri elementare. Graful conex ce nu conține cicluri elementare se numește arbore. Subgraful parțial conex ce nu conține cicluri elementare se numește arbore parțial.

Lanțul (ciclul) ce conține fiecare muchie a grafului exact o singură dată se numește lanț (ciclu) eulerian.

Lanțul (ciclul) ce conține fiecare vârf al grafului exact o singură dată se numește lanț (ciclu) hamiltonian.

Graful care conține ciclu eulerian se numește graf eulerian, iar graful care conține ciclu hamiltonian se numește graf hamiltonian.

Dacă într-un graf orice două vârfuri sunt unite printr-un lanț, atunci acest graf se numește conex. Subgraful maximal conex al grafului se numește componentă conexă.

Submulțimea cu un număr minim de vărfuri A ale unui graf se numește mulțime de articulație a acestui graf, dacă după eliminarea acesteia din G se obține un graf nou cu un număr mai mare de componente conexe în raport cu G.

În cazul , unicul vârf ce aparține mulțimii A se numește punct de articulație. Muchia grafului cu aceeași proprietate se numește istm. Evident, dacă u este un istm al unui graf cu vârfuri, atunci cel puțin una dintre extremitățile sale este punct de articulație. Afirmația inversă nu este adevărată.

Orice subgraf maximal al grafului , care nu conține puncte de articulație, se numește bloc.

Exemplu de lanturi este arătat în figura 1.11

1

2 3

4 G

5 6 7

Fig. 1.11

În graful G o parte din lanturi sunt :

=[1,2,4,5,6,7]

=[7,6,5,4,7]

=[3,4,5,6,7,4,2]

=[1,2,4,6,5]

Dintre acestea lanturi elementare sunt si

§ 1.4 Metrica în grafurile neorientate

Notăm prin d(x,y) lungimea minimă a lanțurilor ce unesc vârfurile x, y. În cazul când între două vârfuri nu există nici un lanț, se consideră . Numărul se numește distanța pe mulțimea de vârfuri ale unui graf , deoarece satisface axiomele metricii, adică pentru oricare trei vârfuri au loc următoarele relații:

1) și , dacă și numai dacă ,

2) ,

3) .

Cu ajutorul distanței se definește puterea de gradul al grafului. Vom numi putere de gradul al unui graf , graful ce conține aceeași mulțime de vârfuri cu și în care două vârfuri sunt adiaceubgraf maximal al grafului , care nu conține puncte de articulație, se numește bloc.

Exemplu de lanturi este arătat în figura 1.11

1

2 3

4 G

5 6 7

Fig. 1.11

În graful G o parte din lanturi sunt :

=[1,2,4,5,6,7]

=[7,6,5,4,7]

=[3,4,5,6,7,4,2]

=[1,2,4,6,5]

Dintre acestea lanturi elementare sunt si

§ 1.4 Metrica în grafurile neorientate

Notăm prin d(x,y) lungimea minimă a lanțurilor ce unesc vârfurile x, y. În cazul când între două vârfuri nu există nici un lanț, se consideră . Numărul se numește distanța pe mulțimea de vârfuri ale unui graf , deoarece satisface axiomele metricii, adică pentru oricare trei vârfuri au loc următoarele relații:

1) și , dacă și numai dacă ,

2) ,

3) .

Cu ajutorul distanței se definește puterea de gradul al grafului. Vom numi putere de gradul al unui graf , graful ce conține aceeași mulțime de vârfuri cu și în care două vârfuri sunt adiacente dacă și numai dacă în are loc inegalitatea .

§ 1.5 Reprezentări ale grafurilor

În afară de reprezentarea grafului descris nemijlocit cu ajutorul mulțimilor de vârfuri și muchii, graful mai poate fi reprezentat atât algebric, prin intermediul matricei de adiacență, a matricei de incidență etc. , cât și geometric, unde vârfurile grafului corespund unor puncte din spațiu, iar orice muchie se reprezintă printr-o linie continuă, ce unește punctele corespunzătoare extremităților acesteia. În cazul grafurilor orientate, liniile sunt înzestrate cu săgeți, care corespund orientării arcelor. Graful care poate fi reprezentat în plan astfel, încăt orice două muchii ale sale nu au puncte comune interioare se numește planar. Însăși reprezentarea geometrică a grafului planar, ce posedă proprietatea indicată, se numește graf-plan. Se mai spune că graful-plan este o reprezentare corectă în plan a grafului planar. La suprimarea din plan a muchiilor și vârfurilor unui graf-plan întreg planul se împarte în componente conexe, numite fațete (fețe) ale lui . Componentele conexe mărginite se numesc fațete interioare, iar componența conexă nemărginită – fațetă exterioară. Orice graf-plan conține exact o fațetă exterioară.

O matrice binară de dimensiune se numește matrice de adiacență a grafului cu mulțimea de vârfuri , dacă:

Matricea de adiacență a grafului este o matrice simetrică cu elementele de pe diagonala principală egale cu zero. Liniile și coloanele acestei matrici corespund vârfurilor grafului. Numărul de unități dintr-o linie (coloană) este egal cu gradul vârfului corespunzător acestei linii (coloane).

Exemplu. Vom examina graful reprezentat în figura 1.12. Pentru acest graf matricea de adiacentă este următoarea:

O matrice binară , de dimensiune se numește matrice de incidență a grafului , , , dacă

Exemplu. Pentru graful din figura 1.12 matricea de incidentă este următoare:

În cazul grafurilor orientate matricea de incidentă este o matrice .

Un rol deosebit la studierea arborilor partiali ai unui graf neorientat îl joacă matricea lui Kirhgoff, careeste o matrice binară

pătratică de dimensiunea cu proprietatea că suma elementelor oricărei linii si a oricărei coloane este egală cu zero.

Capitolul 2. Amplasarea centrelor in graf

§ 2.1 Centrul și raza grafului

În actvitatea practică mereu apar probleme de amplasare cât mai optimală a centrelor de deservire sau a echipamentelor în rețele sau grafuri. Astfel, dacă graful reprezintă rețeaua de drumuri ce unește careva localități (vârfurile grafului) atunci poate fi cercetată problema amplasării optimale a spitalelor, secțiilor de poliție, unităților de pompieri sau a altelor centre de deservire. În asemenea cazuri criteriul de optimizare constă în minimizarea distanței (sau timpului de călătorie) de la punctul de deservire până la cel mai îndepărtat vârf al grafului. Problema generală constă în amplasarea a mai multor centre de deservire. În acest caz distanța de la cel mai îndepărtat vârf al grafului până la cel puțin un centru de deservire trebuie să fie minimală posibilă. Locurile de amplasarea a serviciilor obținute la soluționarea acestor probleme se numesc centre ale grafului.

Vom cerceta problema de amplasare a centrelor în cazul grafurilor ponderate cu ponderile corespunzătoare arcelor (care reprezintă lungimea) și asociate vârfurilor (care pot reprezenta, de exemplu, dimensiunea sau importanța obiectelor).

Fie un graf orientat, ponderat. Prin vom nota mulțimea vârfurilor pentru care în graful G există drumurile din vârful în lungimile ponderate ale cărora nu întrec valoarea . Iar prin – mulțimea vârfurilor pentru care în G există drumurile din vârful în lungimile ponderate ale cărora nu întrec valoarea .

Astfel,

(2.1)

Pentru fiecare vârf al grafului se definesc două numere:

(2.2)

.

Numerele și se numes respectiv număr de divizare exterioară și număr de divizare interioară a vărfului . Vom menționa că este elementul maximal din linia a matricii care se obține din matricea distanțelor la înmulțirea fiecărei colane j cu , iar este elementul maximal din coloana a matricii ce se obține la înmulțirea fiecărei linii j a matricii distanțelor cu .

Fie (X,U) un graf (finit sau nu): fiind date 2 vârfuri x si y, abaterea d(x,y) dintre x si y este, prin definitie, lungimea celui mai scurt drum dintre x si y.

Dacă x=y, punem, prin conventie, d(x,x)=0; dacă , punem d(x,x)=∞.

Teorema 1. d(x,x) verifică relațiile

d(x,x)=0, (1*)

d(x,y)+d(y,z) ≥ d(x,z) (2*)

În consecintă, dacă graful este simetric, avem:

d(x,y)=d(y,x) (3*)

Demonstratia este imediată; dacă graful este simetric, functia d(x,y) care verifică (1*),(2*),(3*) este o distantă în sensul topologic al cuvântului.

Numim abaterea unui vârf x numărul:

Dacă minimul abaterilor este un număr finit, atunci punctul de abatere minimă este un centru al vârfului x al grafului; un punct de abatere maximă este un punct periferic al grafului; un graf poate avea mai multe centre sau nici unul.

Dacă un graf admite un centru , abaterea se numeste rază a grafului; avem deci, pentru raza p formula:

.

Dacă graful nu admite centre, punem p=+∞.

Teorema 2. Dacă într-un graf finit G=(X,U) se pune și dacă

1 < p < ∞, atunci raza p a grafului verifică relația :

Dacă p=∞, teorema este evidentă; să presupunem deci p < ∞, ceea ce implică faptul că graful admite centrul . Numărul vârfurilor cu o abatere, fată de , egală cu 1 este ≤p; numărul vârfurilor cu o abatere ,egală cu 2 este etc. Avem deci

sau

de unde

De aici se obține formula enunțată.

Teorema 3. Dacă un graf finit G=(X,U) este complet (adică dacă orice pereche de vârfuri este legată cel puțin într-o directive), atunci raza sa este ≤ 2; în consecintă orice vârf pentru care

este un centru.

Dacă p=1, teorema este evidentă.

Dacă p<1, să considerăm un vârf pentru să fie maxim ( există deoarece graful este U-mărginit). Cum pentru orice x, dacă arătăm că , atunci rezultă că în același timp este un centru si că

p=2.

Să rationăm prin absurd si să presupunem . Există atunci un vârf care nu poate fi atins de nici pe un drum de lungime 1, nici pe un drum de lungime 2. Cum , avem

.

Pe de altă parte, dacă z este un vârf din , avem (deoarece altfel y ar fi atins de pe un drum de lungime 2), de unde si

Avem deci, în final,

.

Cum avem incluziunea strictă

.

De unde .

Am ajuns aici la o contradicție.

COROLAR. Dacă un graf finit G=(X,U) este total, atunci el admite un centru. Într-adevăr, graful G=(X,U) putem atinge din punctul x celelalte vârfuri printr-un drum de lungime finită.

Deci, acest graf admite o rază si are un centru.

Definiție. Vârful se numește centru exterior al grafului G dacă

. (2.3)

Definiție. Vârful se numește centru interior al grafului G dacă

. (2.4)

Deasemenea pot fi definite numărul de divizare exterioară-interioară

și centrul exterior-interior ca vârf al garfului cu cel mai mic număr de divizare exterioară-interioară.

Interpretarea centrelor poate fi variată. Astfel, centrul exterior poate fi interpretat ca o secție de pompieri și, deci, minimal trebuie să fie timpul pentru drumul de la secție la locul unde s-a produs incediul. Ca centrul interior poate fi privit un adăpost în cazul calamităților naturale – oamenii trebuie sa ajunga la adăpost în timp minimal. Spitalul de urgență poate servi ca exemplu pentru centru exterior-interior – minimal trebuie să fie drumul „spital-pacient-spital”.

Vom prezenta un algoritm de căutare a centrului exterior într-un graf arbitrar.

Algoritmul de căutare a centrului exterior

Se construiește matricea distanțelor, unde și reprezintă lungimea drumului minim din vârful în vârful a grafului. La generarea acestei matrice poate fi aplicat algortmul lui Dijkstra sau cel al lui Floyd.

Se construiește matricea înmulțind fiecare colană j a matricii distanțelor D cu ponderea a vârfului .

Pentru fiecare linie i a matricei se determină maximumul. Ca rezultat se obține un șir de lungimea n, în care elementul i reprezintă numărul de divizare exterioară a vârfului .

În șirul creat se determină valoarea minimală. Fiecare vârf al grafului număr de divizare exterioară a căruia coincide cu această valoare este centrul exterior al garfului.

Algoritmul de căutare a centrului interior al grafului se deosebește de cel descris doar prin faptul ca la pasul 2 se construește matricea care se obține la înmulțirea fiecărei linii j a matricii distanțelor cu ponderea a vârfului și la pasul 3 pentru fiecare coloană a matricii se determină maximumul.

Vom cerceta graful din Fig. 1. cu ponderile tuturor arcelor egale cu 1 și ponderile vârfurilor definite de vectorul (2, 1, 3, 3, 2, 4).

Matricea distanțelor acestui garf este

Valorile divizărilor exterioare și interioare ale vârfurile grafului sunt indicate în ultima linie și respectiv ultima coloană a matricii.

Astfel, graful cercetat posedă un singur centru exterior (deoarece ) și două centre interioare (). Raza exterioara a grafului este egală cu 6, iar cea interioară cu 9.

§2.2. Centrul absolut

Vom aminti că într-un graf orientat arcele și se numesc simetrice și pot fi substituite cu muchia . În continuare vom generaliza noțiunea de centru pentru așa numitele „puncte artificiale” care pot fi plasate pe muchiile grafului. Deci, se vor cerceta grafurile neorientate și grafurile orientate cu arce simetrice.

Relațiile (2.2) definesc numerele de divizarea pentru orice vârf . Vom generaliza această definiție pentru „punctele artificiale” amplasate pe muchiile grafului. Fie G un graf arbitrar și o muchie cu ponderea a acestui graf (Fig. 2).

Punctul artificial y plasat pe muchia a poate fi definit cu ajutorul lungimii a porțiunii a acestei muchii cu condiția că:

. (2.5)

Numerele de divizare a punctului y, indiferent de faptul este el vârf al grafului G sau punct artificial al unei muchii a grafului, se determină conform relațiilor:

,

(2.6)

.

Definiție. Punctele , pentru care , și pentru care se numesc centru exterior absolut și, respectiv, centru interior absolut al grafului G.

Definiție. Numărul de divizare exterioară a centrului exterior absolut se numește rază exterioară absolută a grafului, iar numărul de divizare interioară a centrului interior absolut se numește rază iterioară absolută a lui G, care se notează și respectiv.

Exemplu. Fie în gaful neorientat G din Fig. 3 ponderile tuturor vârfurilor sunt egale cu 1 și .

Deoarece garful este neorientat, pentru fiecare vârf al grafului numerele lui de divizare exterioară și inetrioară coincid. În cazul când centrul grafului se va cauta doar în vârfurile acestui graf vom avea matricea distanțelor:

Ușor se observă că vârfurile și sunt centrele grafului G, iar raza grafului este egală cu 5.

Vom plasa acum pe muchia un punct y astfel ca . În acest caz matricea distanțelor va fi:

Efectuând calculele necesare observăm că punctul y este „mai central” decât orice vârf al grafului și, deci, este centru absolut al grafului G, iar raza absolută este egală cu 4.

Menționăm că în caz general în graf pot exista mai multe centre absolute amplasate atât în vârfurile grafului, cât și pe muchiile lui.

§ 2.3 Algoritmi de căutare a centrelor absolute

Ușor se observă că în grafurile orientate centrele absolute nu pot fi situate pe arce. Într-adevăr. Fie un punct de pe arcul și un vârf sau un punct arbitrar de pe un careva arc al grafului orientat . Dacă în nu există arcul simetric, atunci și . De aceea în cazul grafurilor orientate pot fi eliminate toate arcele, cu excepția celor simetrice, care se substituie prin muchii respective, și problema se va reduce la căutarea centrelor absolute în grafurile neorientate. În acest caz centrul absolut exterior și centrul absolut interior al grafului coincid. Astfel, în continuare nu este necesar de specificat care centru absolut va fi căutat.Vom analiza doi algoritmi de căutare a centrelor absolute în graf.

2.3.1. Metoda Hakimi

Acest algoritm permite determinarea locației exacte a centrului absolut și calcularea numărului de divizarea al lui (raza absolută).

Algoritmul Hakimi.

Pe fiecare muchie se caută punctul cu cel mai mic număr de divizare.

Dintre toate punctele , în calitate de centru absolut se alege punctul cu cel mai mic număr de divizare.

Pasul 2 al algoritmului descris este simplu. Primul pas este considerabil mai dificil și se realizează în modul următor.

Fie muchia a grafului G. Pentru orice punct are loc:

(2.3.1.1)

Notăm și, deoarece , relația (2.3.1.1) poate fi scrisă astfel . (2.3.1.2)

Pentru un vârf fixat și pot fi determinate valorile minimale ale expresiilor din parantezele pătrate ale relației (2.3.1.2).

În acest scop pe plan se construiesc dreptele:

(2.3.1.3)

Curba înfășurătoare inferioară a acestor drepte reprezintă graficul dependenței distanței

ponderate de locația punctului pe muchia.

În continuare pe același plan se construiesc curbele înfășurătoare inferioare pentru toate celelalte vârfuri. Curba înfășurătoare superioară a curbelor construite reprezintă graficul dependenței valorii de locația punctului pe muchia dată. Înfășurătoarea superioară poate avea mai multe puncte de minim.

Punctul care corespunde celui mai mic punct de minim este centrul absolut pe muchia. Se calculează centrele absolute pentru toate celelalte muchii ale grafului.

Centrul absolut al grafului va fi punctul cu cea mai mică valoare a numărului de divizare .

Exemplu. Vom cerceta problema amplasării unui spital care va deservi 6 zone ale orașului. Fie graful din figura 1.3.1.1, în care vârfurile corespund zonelor respective, iar lungimea muchiei reprezintă timpul, necesar pentru a ajunge din zona în zona. Vom considera că vârfurile grafului au ponderi unitare și nu este impusă restricția ca spitalul să fie amplasat doar în zonele. În aceste condiții amplasarea optimală a spitalului va fi în unul din centrele absolute ale grafului respectiv.

Matricea distanțelor (a timpului) pentru graful din figura 2.3.1.1 este:

Deoarece graful este neorientat numărul de divizare exterior este egal cu numărul de divizare interior, astfel , deci este centrul grafului cu raza egală cu 8.

În continuare vom calcula centrul absolut al grafului și deoarece graful este neorientat, vom căuta centrele absolute de pe toate muchiile.

Fie în muchia distanța se calculează de la la . Aplicând formulele (2.3.1.3), obtinem:

.

; .

; .

; .

; .

; .

Graficele funcțiilor și (), pentru , sunt prezentate în figura 2.3.1.2a.

Astfel, pe muchia există un singur centru absolut local , care se află la distanța 6 de la vârful si distanta 2 de , iar raza absolută locală este .

Similar vom proceda cu muchia , calculând de la la .

.

; .

; .

; .

; .

; .

Graficele funcțiilor și (), pentru , sunt prezentate în figura 2.3.1.2b. Centrul absolut de pe muchia coincide cu vârful , adică , iar raza absolută locală este .

Pentru muchia cu de la la avem:

.

; .

; .

; .

; .

; .

Graficele funcțiilor și () sunt prezentate în figura 2.3.1.2c. Centrul absolut de pe muchia este , care se află la distața 4 de la și la distața 2 de la , iar raza absolută locală este .

Pentru muchia cu de la la avem:

.

; .

; .

; .

; .

; .

Graficele funcțiilor și () sunt prezentate în figura 2.3.1.2d. Centrul absolut de pe muchia coincide cu vârful , adică cu raza absolută locală .

Pentru muchia cu de la la avem:

.

; .

; .

; .

; .

; .

Graficele funcțiilor și () sunt prezentate în figura 2.3.1.2e. Centrul absolut de pe muchia coincide cu vârful , adică cu raza absolută locală .

Pentru muchia cu de la la avem:

.

; .

; .

; .

; .

; .

Graficele funcțiilor și () sunt prezentate în figura 2.3.1.2f. Centrul absolut de pe muchia coincide cu vârful , adică cu .

Pentru muchia cu de la la avem:

.

; .

; .

; .

; .

; .

Graficele funcțiilor și () sunt prezentate în figura 2.3.1.2g. Centrul absolut de pe muchia coincide cu vârful la fel și cu vârful , adică și raza absolută locală este .

Pentru muchia cu de la la avem:

.

; .

; .

; .

; .

; .

Graficele funcțiilor și () sunt prezentate în figura 2.3.1.2h. Centrul absolut de pe muchia coincide cu vârful , adică cu raza absolută locală .

Pentru muchia cu de la la avem:

.

; .

; .

; .

; .

; .

Graficele funcțiilor și () sunt prezentate în figura 2.3.1.2i. Centrul absolut de pe muchia este , care se află la distanța 4 de la și la distanța 6 de la cu raza absolută locală .

Conform algoritmului Hakimi centrul absolut al grafului este unul din centrele absolute locale determinate cu număr minim de divizare. Calculăm

și deci,. Astfel, centrul absolut al grafului este situat pe muchia la distanța 4 de la vârful si la distanta 2 de la vârful .

Algoritmul lui Hakimi poate fi considerabil optimizat. Ideea principală constă în evaluarea inițială a mărimii razei absolute a grafului și excluderea din cercetare a muchiilor pe care, în baza estimărilor efectuate, nu poate fi situat centrul absolut.

Vom considera că centrul absolut al grafului se află pe muchia . Atunci valoarea razei absolute a grafului nu este mai mică decât

iar mărimea este limita inferioară pentru raza absolută a grafului G.

În continuare vom presupune că centrul absolut al grafului este situat în mijlocul muchiei . În acest caz raza absolută a grafului este egală cu , unde este ponderea vârfului în care mărimea atinge valoarea maximă, iar este limita superioară pentru raza absolută a grafului.

Astfel, orice muchie , pentru care , poate fi exclusă din cercetare la aplicarea algorimului Hakimi de căutare a centrului absolut al grafului.

Vom aplica modificările propuse pentru graful din exemplul precedent. Obținem:

pentru muchia ,

pentru muchia

pentru muchia

pentru muchia

pentru muchia

pentru muchia

pentru muchia

pentru muchia

pentru muchia

Calculăm limita superioară pentru raza absolută a grafului. Muchiile , pentru care mărimile corespunzătoare, pot fi excluse din cercetare și algoritmul Hakimi se va aplica doar pe muchiile. Limita inferioară pentru raza absolută a grafului este . Această valoarea este doar o aproximare a valorii exacte a razei absolute a grafului care, conform calculelor din exemplul precedent, este egală cu 6.

2.3.2. Metoda iterativă

Metoda iterativă, va fi expusă pentru cazul grafurilor neorientate. Pentru a aplica metoda iterativă pe grafuri orientate noțiunile „neorientate”, fără a genera schimbări esențiale, se vor substitui cu analogiile lor „orientate”.

Vom menționa că această metodă nu determină locul exact al centrului absolut și valoarea exactă a razei absolute a grafului. În rezultatul aplicării metodei iterative se determină domeniul în care se găsește centrul absolut, și, respectiv, valoarea aproximativă a razei absolute.

Fie mulțimea tuturor punctelor y de pe muchiile grafului G din care se poate ajunge în vârful pe lanțuri (drumuri), a căror lungime ponderată nu întrece . Evident, raza absolută r a grafului G este valoarea minimă a lui pentru care din careva punct y al garfului se poate ajunge în orice vârf al lui G pe lanțuri cu lungime ponderată nu mai mare decât. Deci, r este valoarea minimală a lui pentru care se respectă condiția:

(2.3.2.1)

Astfel, atribuind lui o valoare destul de mică pentru fiecare , se construiesc mulțimile și se verifică îndeplinirea relației (2.3.2.1). Dacă această relație nu are loc, atunci valoarea lui se mărește puțin și din nou se construiesc mulțimile verificând relația menționată. Procesul descris se repetă până când se va îndeplini relația (2.3.2.1). Valoarea corespunzătoare a lui se ia în calitate de rază absolută r a grafului G. În plus, deoarece valorile cu care se mărește sunt foarte mici, la finalizarea procesului iterativ intersecția

(2.3.2.2)

va conține un singur punct care și este centru absolut al grafului. În cazul existenței a mai multor centre absolute intersecția (2.3.2.2) poate să conțină mai multe puncte.

Amintim că este distanța minimă dintre două vârfuri arbitrare și a grafului G. Ușor se observă că, dacă , atunci și, prin urmare, intersecția (2.3.2.2) deasemenea este vidă.

Astfel, procesul iterativ de căutare a centrului absolut al grafului poate înceape cu valoarea , unde

.

dat fiind faptul că raza r nu poate fi mai mică decât. Atunci valoarea poate fi interpretată ca diametrul grafului. Vom menționa doar, că în realitate diametrul grafului nu este neapărat de două ori mai mare decât raza absolută.

Algoritmul iterativ

Se alege o valoare aleatoare și inițial se consideră ,unde .

Se construiesc mulțimile , și se determină intersecția acestor mulțimi.

Dacă această intersecție este vidă, atunci valoarea lui se majorează cu și se trece la pasul 2. În caz contrar, centrul absolut se află în domeniul determinat de această intersecție.

§2.4 Centre multipe

În unele cazuri, când există necesitatea amplasării a mai multor obiecte, centre de deservire, se admite o generalizare a noțiunii de centru: se cercetează nu doar un singur punct (centru), dar o mulțime din p puncte care formează centrul multiplu (p-centru) al grafului.

O problemă care se reduce la determinarea p-centrului într-un graf poate fi formulată astfel: Cum poate fi creată o rețea de restaurante astfel, ca din orice punct al orașului să se ajungă în unul din aceste restaurante în mai puțin de 10 minute?

Fie o submulțime din p vârfuri a mulțimii X de vârfuri a grafului G. Vom nota prin cea mai mică distanță dintre vârfurile mulțimii și vârful , adică . Similar se definește distanța .

Ținând cont de definițiile numerelor de divizare externă și internă a vârfurilor (paragraful 1.1) se definește numărul de divizare externă a mulțimii

și numărul de divizare internă a mulțimii

.

Definiție. Mulțimea pentru care se numește centru extern multiplu sau p-centru extern al grafului G.

Definiție. Mulțimea pentru care se numește centru intern multiplu sau p- centru intern al grafului G.

În paragraful 2.1 s-a descris procedeul de determinare a centrului extern și a celui intern al garfului în baza matricei distanțelor. În cazul p-centrelor acest procedeu poate fi utilizat doar pentru grafuri de dimensiuni mici. Pentru aceasta se construiesc toate mulțimile posibile constituite din p vârfuri și, conform definițiilor de mai sus, se determină mulțimile și care formează p-centrele grafului. Acest procedeu presupune executarea a comparații, număr ce crește considerabil chiar pentru grafuri de dimensiuni medii. Acest mod de soluționare a problemei va necesita timp și resurse computaționale considerabile. De aceea este mai eficient să se aplice algoritmul iterativ, care va fi descris pentru p-centrele absolute ale grafului.

§2.5 Centre multiple absolute

Similar modului de definire a centrului absolut vom defini noțiunea de p-centru absolut al grafului G. Fie mulțimea care constă din p puncte ale grafului G situate atât în vârfuri, cât și pe muchii.

Atunci, și . Astfel, este numărul de divizare externă a mulțimii , iar – numărul de divizare internă a mulțimii .

În mod analog, mulțimea cu este p-centru extern absolut și mulțimea pentru care este p-centru intern absolut al grafului G.

Ușor se observă că p-centru absolut al grafului este o generalizare a noțiunii de centru absolut. Astfel, centrul absolut definit în paragraful 2.2 în terminologia introdusă se numește 1-cen-tru absolut al grafului.

Problema generală de determinare a p-centrului absolut poate fi formulată în următoarele două moduri:

De determinat amplasarea optimală în orice puncte ale garfului a unui număr, fie p, de centre astfel, ca distanța de la cel mai îndepărtat vârf până la cel mai apropiat de el centru să fie minimală posibilă.

Fie dată o „distanță critică”. Să se determine un număr minimal de centre și o locație a acestora astfel încât fiecare vârf al grafului să se afle la „distanța critică” de la cel mai apropiat de el centru.

Problema generală este des întâlnită în practică, însă se soluționează considerabil mai dificil decât orice varianta „limitată” a ei. Menționăm că metoda Hakimi descrisă pentru determinarea centrului absolut nu poate fi generalizată pentru p-centrele absolute.

Vom cerceta un algoritmul iterativ pentru determinarea p-centrelor absolute ale grafului. Acest algoritm converge rapid și posedă următoarele avantaje :

Procesul se încheie imediat ce se obține „exactitatea” necesară în amplasarea centrelor;

Algoritm fi simplu modificat pentru căutarea soluțiilor cât mai apropiate de cele optimale și, deci, pentru analiza stabilitatății soluțiilor.

Ca și în cazul centrului absolut, graful G se consideră neorientat. Extinderea rezultatelor pe garfurile orientate este evidentă. Ideea generală a algoritmului constă în construirea domeniilor specifice care reprezintă mulțimi de puncte ale grafului cu proprietatea: din fiecare punct y al domeniului se poate ajunge în orice vârf al submulțimii de vârfuri pe lanțuri de lungime cel mult ; iar pentru orice vârf această proprietate nu este satisfăcută. Un domeniu poate fi constituit pornind de la o porțiune de muchie sau de la un singur punct.

Pentru a forma domeniile mai întâi se construiesc mulțimile definite în paragraful 2.2. Astfel, () este domeniul din care nu se poate ajunge în nici un vârf al grafului pe lanțuri lungimea cărora nu întrece . Al doilea termen din formulă exclude toate domeniile grafului G din care se poate ajunge cel puțin într-un vârf de-a lungul lanțurilor de lungime cel mult . Domeniul poate fi exprimat prin mulțimile conform formulei:

.

Aici al doilea termen din formulă exclude domeniile grafului G din care se poate ajunge, pe lanțurile de lungime cel mult , în vârfurile mulțimii și cel puțin în unul din vârfurile rămase ale grafului.

Algoritmul de determinare a p-centrului absolut a grafului[2]

Fie un graf neorientat arbitrar și p un număr întreg. Să se găsească p-centrului absolut al lui G.

Pasul 1. Se alege o mărime destul de mică . Se atribuie .

Pasul 2. Pentru fiecare vârf se construiesc mulțimile .

Pasul 3. Utilizând mulțimile se determină domeniile .

Pasul 4. Se construiește graful bipartit , unde:

X este mulțimea de vârfuri a grafului G;

este o mulțime de vârfuri în care fiecare vârf corespunde unui domeniu ;

este mulțimea de muchii astfel, încât muchiea cu o extremitate într-un vârf-domeniu, iar cealaltă într-un vârf există atunci și numai atunci când în vârful al grafului G se poate ajunge din domeniul respectiv.

Pasul 5. Se găsește mulțimea stabilă exterior minimă a garfului bipartit .

Pasul 6. Dacă numărul domeniilor în mulțimea stabilă exterior minimă este mai mare decât p, valoare lui se mărește cu () și se trece la pasul 2. În caz contrar domeniile mulțimii stabile exterior minime formează p-centru absolut al grafului G, iar este p-raza absolută.

Eroarea în determinarea conform acestui algoritm a centrului și a valorii corespunzătoare depinde liniar de valoare lui . La executarea algoritmului descris suplimentar se vor determina și , ș.a.m.d. centrele absolute ale grafului.

Vom descrie unele detalii de realizare ale algoritmului. Considerăm un fixat. Pentru orice muchie a grafului se îndeplinește una din următoarele situații: din vârful pe lanțuri lungimea căror nu întrece se poate ajunge sau în toate punctele muchiei, sau într-o porțiune din muchie, sau nu se poate ajunge în nici un punct al muchiei. Dacă din vârful respectiv se ajunge doar pe o porțiune a muchiei, de la o extremitate a muchiei până la un punct „limită”, atunci punctul „limită” se etichetează. Eticheta reprezintă lista vârfurilor grafului din care se ajunge în punctul „limită”. Astfel, aceste etichete conțin toată informația necesară pentru descrierea mulțimii . Prin urmare, constă din punctele muchiilor (sau porțiunilor de muchii), care aparțin lanțurilor ce unesc etichetele cu vârful .

După atribuirea tuturor etichetelor pentru toate vârfurile garfului fiecare muchie se va diviza în sectoare care se caracterizează doar de vârfurile în care se poate ajunge din aceste secțiuni. Deci, fiecare sector poate fi definit de un vector binar , , unde dacă din careva punct al sectorului putem ajunge în vârful și în caz contrar. Astfel, totalitatea sectoarelor descrise de același vector binar formează domeniul . Reprezentarea domeniilor prin vectori binari, din punct de vedere al calculului, este foarte comodă deși nu conține nici o informație despre amplasarea lor în graf. Acești vectori binari se numesc intersecții stricte și se notează SI (strict intersections).

La pasul 4 al algoritmului se prevede construirea grafului bipartit care, în caz general, poate avea dimensiuni mari. Conform următoarei teoreme dimensiunea acestui graf poate fi micșorată prin eliminarea domeniilor ce nu afectează soluția optimală a problemei (dacă însă există câteva soluții optimale, la aplicarea acestei procedure unele din ele pot fi pierdute).

Teoremă[2]. Având un fixat pentru determinarea unei mulțimi stabile exterior minime a grafului din pot fi excluse toate vârfurile care corespund vectorilor SI dominați în de alți vectori binari SI. Vom spune, că îl domină pe dacă , unde este produs boolean (conjuncție).

Dacă este necesar să se determine valoarea minimală a lui p pentru care fiecare vârf al garfului se află la o distanță ce nu întrece „distanța critică” de la careva centru (problema generală 2), atunci pașii 3 – 6 se realizează pentru egal cu această „distanță critică”. În acest caz numărul domeniilor în mulțimea stabilă exterior minimă reprezintă valoarea căutată a lui p, iar domeniile acestei mulțimi formează p-centrului respectiv.

Exemplu. Vom cerceta garful neorientat din Fig.6. Considerăm ponderile tuturor vârfurilor grafului egale cu 1. Numerele alăturate muchiilor acestui graf indică lungimea lor. Se cere de determinat un 2-centrul absolut încât fiecare vârf al grafului să se afle la distanța ce nu întrece de la cel puțin unul din aceste două centre.

Vom aplica algoritmul descris mai sus.

În Fig. 7. sunt reprezentate etichetele care definesc mulțimile , , pentru . Aceste etichete, obținute la parcurgerea consecutivă a muchiilor grafului, indică vârfurile cărora le corespund. Astfel, eticheta de pe muchia indică unicul punct în care se poate ajunge din vârfurile și în limitele distanței . În Fig. 7. prin liniile întrerupte atașate muchiilor garfului este reprezentată mulțimea , mulțimea punctelor în care se poate ajunge din vârful pe lanțurile a căror lungime nu întrece .

Vom determina sectoarele în care se divizează fiecare muchia a grafului:

: ,,, și punctul ;

: [];

, , ,

, , și punctul ;

,,, ,

Astfel, muchiile grafului cercetat se divizează în 15 sectoare, inclusiv sectorul vid,de pe muchia (în acest sector nu se poate ajunge, în limitele distanței 2,5, din nici un vârf al grafului). Pentru sectoarele determinate se construiesc vectorii binari SI. Unele sectoare au aceleași SI și în continuare se consideră doar 9 sectoare cu următoarele intersecții stricte SI:

De exemplu, sectorul de pe muchia mărginit de etichetele și aparține domeniului a cărui SI este (0110), deoarece doar din punctele grafului situate între aceste etichete se poate ajunge în vârfurile și (dar numai în aceste vârfuri) pe lanțuri cu lungimea cel mult 2,5.

După excluderea SI dominați de alți SI rămân doar două domenii definite de SI 7=(0110) și 9=(1101). Se construiește graful bipartit (vezi Fig. 8.), conform procedeului descris în pasul 4 al algoritmului. Mulțimea stabilă exterior minimă a grafului poate fi determinată aplicând algoritmul respectiv, descris în partea I a lucrării de față. Însă pentru garful

bipartit din Fig. 8. mulțimea de vârfuri stabilă exterior minimă ușor se găsește prin triere directă a muchiilor și conține vârfurile 7 și 9, definite de cei doi SI. Deoarece mulțimea stabilă exterior minimă a grafului constă din două domenii și , conform pasului 6 al algoritmului ele determină p-centrul absolut al garfului G.

Domeniul care corespunde SI (0110) reprezintă sectorul muchiei mărginit de etichetele și , marcat în Fig. 7. prin A. Al doilea domeniu definit de SI (1101) reprezintă un singur punct de pe muchia în care este amplasată eticheta . În Fig. 7. acest domeniu este marcat prin B. Astfel, pentru 2-centrul absolut al grafului G constă din mulțimea A de puncte a muchiei și punctul B de pe muchia a acestui graf.

Remarcă. Algoritmul descris poate fi aplicat și la determinarea p-centrului grafului dacă se vor face câteva modificări. Deoarece în acest caz se cercetează doar vârfurile din domenii mulțimile, schimbările vor fi:

Din start toate cele distanțe din matricea distanțelor se vor aranja în ordinea nedescrescătoare . La Pasul 1 al algoritmului lui i se atribuie valoarea (), iar la Pasul 6 operația este substituită de atribuirea parametrului a valori următoare din șirul ordonat construit, adică ș.a.m.d.

În Pasul 2 și Pasul 3 mulțimile se înlocuiesc cu mulțimile .

Pasul 6. Dacă numărul vârfurilor grafului G din domeniile ce determină mulțimea stabilă exterior minimă a lui este mai mare decât p, lui i se atribuie următoarea valoare din șirul ordonat al distanțelor și se trece la pasul 2. În caz contrar vârfurile din domeniile ce formează mulțimea stabilă exterior formează p-centru grafului G.

§2.6. Problema centrului pentru unele clase de grafuri neorientate

Centrul absolut într-un arbore cu vârfuri neponderate

În cazul arborelui cu vârfuri neponderate se aplică un algoritm elegant propus în 1973 de Handller. Metoda lui Handller [54] constă în determinarea unui lanț periferic (lanț de lungime maximală în graf, nu neapărat unic) al arborelui și amplasarea centrului absolut în mijlocul acestui lanț, care poate fi atât vârf al grafului, cât și punct al muchiei.

Algoritmul lui Handller constă din următorii pași:

Se alege un vârf arbitrar al arborelui. Se determină cel mai îndepărtat vârf de la vârful ales și se notează prin .

Pentru vârful se găsește cel mai îndepărtat vârf care se notează .

Lanțul ce unește vârfurile și este lanț de lungime maximă în arborele cercetat și punctul lui de mijloc este unicul centru absolut a arborelui.

Exemplu. De găsit centrul absolut al arborelui din figura 2.6.1.1.

Alegem vârful . Distanțele de la până la toate celelalte vârfuri ale arborelui sunt prezentate în tabelul 1.

Tabelul 1

Vârful este cel mai îndepărtat vârf de la . Astfel, .

Calculând distanțele de la vârful până la toate celelalte vârfuri ale arborelui, obținem tabelul 2.

Tabelul 2

Deoarece cel mai îndepărtat vârf de la este vârful , avem .

Centrul absolut al arborelui se află pe lanțul minimal cu extremitățile , la distanța 12,5 de la vârful . (vezi figura 2.6.1.2).

2-Centrul absolut într-un arbore cu vârfuri neponderate

Pentru determinare a 2-centrului absolut în arborele neponderat se aplică algoritmul descris în paragraful precedent cu mici modificări.

Algoritmul constă din pașii:

Se determină centrul absolut al arborelui, aplicând algoritmul lui Handller.

Dacă centrul absolut este amplasat într-un vârf al grafului, atunci se elimină una din muchiile incidente centrului de pe lanțul care unește vârfurile și . În caz contrar se elimină muchia pe care este situat centrul absolut al grafului. Ca rezultat se obțin doi subarbori.

Aplicând algoritmul lui Handller, se determină centrul absolut pentru fiecare subarbore. Împreună aceste două centre reprezintă soluția problemei 2-centrului absolut pentru arborele inițial.

Exemplu. Petru a ilustra algoritmul descris, vom examina din nou arborele din figura 2.6.1.1.

Din figura 2.6.1.2 se vede că centrul absolut al arborelui este situat pe muchia . Eliminarea acestei muchii, conform pasului 2 al algoritmului, generează doi arbori și (vezi figura 2.6.2.1).

Aplicăm pasul 3 al algoritmului și determinăm centrele absolute ale arborilor obținuți. Pentru subarborele avem:

Ușor se observă că , iar . Centrul absolut al subarborelui este situat pe lanțul minim cu extremitățile la distanța 5,5 de la vârful (vezi figura 2.6.2.2).

Pentru subarborele vom avea:

Astfel, centrul absolut al subarborelui este situat pe lanțul minim cu extremitățile , la distanța 10 de la vârful (sau ).

Centrele absolute ale subarborilor și formează 2-centrul absolut al arborelui inițial (vezi figura 2.6.2.2).

Capitolul III: AMPLASAREA MEDIANEI ÎN GRAF

§3.1. Mediana grafului

Într-un șir de probleme de amplasare se cere de găsit locul pentru un centru de deservire în graf astfel, încât suma distanțelor de la acest centru până la celelalte vârfuri ale grafului să fie minimală posibilă. Vârful grafului care corespunde amplasării optimale a centrului de deservire se numește mediana grafului. Aceste probleme deseori apar în practică: de exemplu, în cazul determinării locului pentru amplasarea stației telefonice într-o rețea telefonică, a stației de distribuire a unei rețele electrice, a depozitelor într-o rețea de drumuri (în ultimul caz vârfurile grafului reprezintă consumatorii), etc.

Deasemenea se cercetează problema determinării a p-medianei într-un graf care constă în amplasarea optimă în graf a unui număr p, de puncte de deservire astfel ca suma distanțelor minime de la vârfurile grafului până la cel mai apropiat pentru ele punct de deservire sa fie minimală. Putem generaliza problema p-medianei dacă fiecărui vârf xj îi punem în corespondență ponderea vj, care poate reprezintă, de exemplu, dimensiunea sau prioritatea vârfului.

Fie un graf arbitrar orientat și ponderat. Pentru fiecare vârf vom defini două valori numite numere de transfer:

unde este cea mai mică distanță dintre vârfurile și . Numerele și se numesc număr de transfer extern și respectiv număr de transfer intern al vârfului . Fie matricea distanțelor grafului G. Numărul reprezintă suma elementelor din linia a matricei obținute în rezultatul înmulțirii fiecărei coloane j a matricei la ponderea a vârfului ce corespunde acestei coloane; numărul reprezintă suma elementelor coloanei a matricei obținute în rezultatul înmulțirii fiecărei linii j a matricei la ponderea a vârfului ce corespunde acestei linii.

Vârful pentru care se numește mediana externă a grafului G, iar vârful pentru care se numește mediana internă a acestui graf.

Considerăm graful din Fig. 1 (paragraful 2.1), în care ponderile și elementele ale matricei distanțelor sunt egale cu 1.

Vom determina numerele și pentru vârfurile acestui graf.

Calculând numerele de transfer ale grafului ușor observăm că în graful G există trei mediane interne , cu numerele de transfer intern egale cu 9, și o mediana externă, vârful cu .

Un exemplu de problemă a medianei este problema aprovizionării unui șir de consumatori cu diferite produse livrate de la același depozit. Vom considera că consumatorii pot fi uniți în grupuri astfel ca fiecare grup să fie deservit de un număr întreg de camioane. Camionul pleacă de la depozit, deservește un anumit grup de consumatori și se întoarce înapoi la depozit. Grupurile de consumatori vor reprezintă vârfurile grafului, iar rețeaua de drumuri mulțimea arcelor grafului. Fiecărui grup de consumatori i se asociază ponderea care reflectă importanța acestuia (de exemplu poate fi o valoare proporțională consumului anual sau frecvenței de aprovizionare a grupului pentru ai satisface cerințele). Se pune problema determinării locului de plasare a depozitului astfel ca distanța totală parcursă de mijloacele de transport să fie minimală posibilă. Dacă matricea distanțelor definește distanțele reale din rețeaua de drumuri, atunci locul în care trebuie plasat depozitul va fi vârful pentru care suma numerelor de transfer inter și extern este cea mai mică. Vârful poate fi considerat mediana mixtă (extern-internă) a grafului.

§3.2. Mediane multiple

Fie o submulțime a mulțimii de vârfuri X a grafului ce conține p vârfuri. Vom introduce următoarele notații:

Dacă este vârful din pentru care în una din formulele de mai sus se atinge valoarea minimală vom spune că vârful este atașat de vârful . Numerele de transfer ale mulțimii se definesc la fel ca și în cazul unui vârf:

unde și sunt numerele de transfer respectiv exterior și interior ale mulțimii . Mulțimea pentru care se numește p-mediană externă a grafului G. Analog, mulțimea pentru care se numește p-mediană internă a grafului.

Ca și în cazul p-centrelor, din punct de vedere al calculului, chiar și pentru grafurile de dimensiuni nu prea mari aplicarea formulelor de mai sus pentru determinarea p-medianelor este inadecvată. Algoritmi de determinare a p-medianelor vor fi descrise în paragrafele ulterioare.

§3.3. Mediane absolute

Fie un graf neorientat ponderat. Este clar că pentru grafurile neorientate numerele de transfer și coincid și în continuare în notația numărului de transfer indicii 0 și t nu se vor folosi.

Punctul y de pe muchia grafului G se numește mediană absolută dacă pentru orice vârf al grafului are loc

.

Teorema 1. Pentru orice punct y situat pe muchiile grafului există cel puțin un vârf x al grafului astfel încât .

Mulțimea care constă din vârfuri și puncte de pe muchiile grafului se numește p-mediană absolută dacă pentru orice submulțime de vârfuri ale grafului aer loc relația

.

Teorema 1 ușor se generalizează pentru cazul p-medianelor.

Teorema 2.Pentru orice submulțime care constă din vârfuri și puncte de pe muchiile grafului există cel puțin o submulțime de vârfuri astfel încât .

Din aceste două teoreme rezultă că noțiunea de mediană absolută, spre deosebire de centru absolut, nu prezintă interes deosebit. De aceea în continuare ne vom concentra atenția asupra problemei p-medianei.

Determinarea p-medianei într-un graf este problema centrală pentru o clasă largă de probleme cunoscute în literatură ca probleme de „alocare și amplasare a centrelor de deservire” sau „amplasare a depozitelor”. Aceste probleme reprezintă de fapt o generalizare a problemei p-medianei, în care vârfurilor grafului sunt asociate costurile fixe .

Problema generalizată a p-medianei poate fi formulată astfel:

Pentru un graf dat cu matricea distanțelor , ponderile și costurile fixe ale vârfurilor de determinat o submulțime alcătuită din p vârfuri pentru care mărimea este minimală posibil.

Astfel, în problema generalizată se minimizează nu numărul de transfer a mulțimii , ci întreaga funcție obiectiv, care conține costurile fixe a vârfurilor . În practică poate reprezenta, de exemplu, costul construirii unui punct de deservire (depozit, stație electrică, fabrică, etc.) la amplasarea acestuia în vârful . Problema p-medianei corespunde cazului când toate vârfurile grafului au același cost fix, adică când pentru orice . Astfel primul termen al sumei z este o mărime fixă egală cu pf care nu depinde de alegerea mulțimii .

O variantă a problemei generalizate a p-medianei des întâlnite în practică este problema care constă în minimizarea funcției obiectiv z cu condiția că numărul de vârfuri a submulțimii nu întrece p, adică .

În problemele de amplasare a depozitelor inevitabil apar diferite restricții, care nu există în problema „pură” a p-medianei. De cele mai dese ori apar restricțiile asupra valorilor minimă și maximă ale expresiei pentru orice vârf . Această expresie determină cantitatea produselor transportate din vârful și, ca consecință, reprezintă o estimare a capacității depozitului .

Dificultatea problemelor practice de amplasare a depozitelor este determinată doar de complexitatea problemei p-medianei și nu depinde de modificările și restricțiile suplimentare expuse mai sus. Ținând cont de cele menționate, vom cerceta câteva metode de care pot fi aplicate la determinarea p-medianei garfului. Deoarece metodele prezentate pot fi aplicate atât pentru determinarea medianelor externe cât și pentru cele interne indicii 0 și t a numerelor de transfer pot fi omiși.

Exemple de determinare a 1-medianei și a 2-medianei în graf

Considerăm graful G din fig. 2 în care vârfurile reprezintă localități și/sau puncte de intersecție a majorității drumurilor din arie, de la care parvin cereri de deservire.

fig. 2

Numărul cererilor care parvin pe zi sunt indicate în paranteze alături de fiecare vârf al grafului (unitățile de măsura fiind sute cereri) și reprezintă ponderea lui. Lungimile drumurilor, reprezentate de muchiile garfului, sunt indicate în kilometri. Pentru a satisface cererile existente se cere de amplasat în această arie un punct de deservire astfel ca distanța medie până la el să fie minimală.

Rezolvare. Conform Teoremei 2 există doar 8 posibilități de amplasare a centrului de deservire – în unul din cele 8 vârfuri ale grafului. Folosind unul din algoritmii de determinare a drumurilor minime, sau, în acest caz, efectuând calcule directe, se construiește matricea distanțelor a grafului G.

.

Construim matricea înmulțind fiecare coloană j a matricei distanțelor la ponderea a vârfului respectiv. Menționăm că elementele matricei au un caracter real. De exemplu, elementul din linia B și coloana D indică următoarele: dacă punctul de deservire va fi amplasat în vârful B beneficiarii din vârful D vor călători în total 900 „pasageri-kilometri” pe zi (=300 persoane x 3 km). Ținând cont de această observație, ușor determinăm soluția optimală a problemei. Mai întâi, sumând elementele din fiecare coloană i a matricei calculăm distanța totală pe care o parcurg beneficiarii dacă punctul de deservire este amplasat în vârful asociat liniei i. Împărțind distanța totală calculată la cererea totală găsim distanța medie pe care o parcurge beneficiarul până la punctul de deservire situat în vârful respectiv. Aceste calcule sunt prezentate în Tabelul.1. Amplasarea optimală a centrului de deservire este în vârful C iar distanța medie este de 2.67 km

Tabelul 1.

§3.4. Metode de rezolvare a probleme p-medianei

3.4.1. Formularea problemei în termenii programării liniare

Fie o matrice pătratică cu dimensiunea cu elementele

Considerăm , dacă vârful este mediană și în caz contrar. Problema determinării p-medianei poate fi formulată astfel:

De minimizat funcția

(3.4.1.1)

cu restricțiile

(3.4.1.2)

(3.4.1.3)

(3.4.1.4)

Si (3.4.1.5)

unde sunt elementele matricei ponderate a distanțelor grafului.

Această matrice se obține la înmulțirea fiecărei coloane j a matricei distanțelor la ponderea a vârfului . Relațiile (3.4.1.2) asigură condiția că orice vârf este atașat doar de un singur vârf mediană . Expresia (3.4.1.3) asigură existența în graf a exact p vârfuri mediane.

Din condiția (3.4.1.4) rezultă că doar atunci când , deci atașarea se efectuează numai față de vârfuri mediane. Dacă este soluția optimală a problemei definite de relațiile (3.4.1.1) – (3.4.1.5) atunci p-mediana va fi .

Dacă în problema cercetată restricțiile (2.4.1.5) se vor înlocui cu restricția

(3.4.1.6)

atunci se va obține o problemă de programare lineară. Vom remarca că, deoarece din relațiile (3.4.1.4) rezultă , pentru variabilele nu este necesar de indicat marginea superioară.

Soluția problemei de programare liniară nu întotdeauna este în numere întregi, pot obține și valori fracționare. Revel și Svane au arătat că această situație apare extrem de rar și, deci, în cele mai multe cazuri la soluționarea problemei p-medianei pot fi aplicate metodele programării liniare.

În cazul când unele valori sunt fracționare, soluția poate fi obținută folosind arborele de căutare. Unei ramuri a arborelui de căutare, care corespunde unei valorii fracționare (variabile) , îi atribuim valoarea 0 iar celeilalte ramuri valoarea 1. Pentru fiecare din ramurile obținute se continuă căutarea soluției. Procedeul se repetă până când toate valorile vor fi sau 0, sau 1.

3.4.2. Algoritmul branch and bound

Dacă problema p-medianei nu este tratată ca problemă a programării lineare ea poate fi soluționată folosind arborele de căutare. Acest mod de abordare corespunde, în cea mai mare măsură, structurii problemei studiate. Există mai multe metode care utilizează arborele de căutare. Vom descrie metoda în care fiecare problemă, ce apare la ramificare în unul din nodurile arborelui, se definește prin atribuirea variabilei a valorii 1 pentru un vârf arbitrar și un vârf fixat . Egalitatea indică că vârful este atașat de vârful și, evident, este vârf mediană.

Această metodă de căutare poate fi realizată în felul următor:

Construim matricea în care coloana j conține toate vârfurile grafului G aranjate în ordine nedescrescătoare a distanțelor acestora de la vârful . Este evident că primul vârf din această coloană, adică cel mai apropiat de este însuși vârful , deci , .

Căutarea începe cu cercetarea consecutivă a tuturor vârfurilor grafului de la până la . Vârful se atașează mai întâi de vârful , apoi de vârful , ș.a.m.d., până când nu vor fi analizate toate posibilitățile. Este necesar de menționat următoarele:

Deoarece soluția optimală constă din p vârfuri mediane, atașarea vârfului la careva vârf mediană în această soluție trebuie să fie cea mai bună din cele p atașări posibile. Cu alte cuvinte, pentru fiecare vârf trebuie să existe cel puțin încă p-1 posibilități de atașare a căror „cost” nu este mai mic decât „costul” atașării alese. Deci din matricea M pot fi eliminate ultimele p-1 linii fără a afecta soluția optimală a problemei.

Presupunem că vârful a fost atașat de vârful , fie . Fie un vârf încă neatașat, care corespunde coloanei j a metricei M. Considerăm că este al -lea vârf în lista vârfurilor aranjate în ordine nedescrescătoare a distanțelor de la vârful , adică . Atunci toate elementele , unde , pot fi excluse din cercetarea ulterioară deoarece:

după atașarea lui la , vârful devine vârf mediană;

vârful poate fi atașat la vârful cu „costul” care nu întrece „costul” de atașare la orice alt vârf . Totodată este clar, că dacă la careva pas de întoarcere a procedurii de căutare aranjarea vârfului față de se modifică, atunci elementele care nu au fost marcate (excluse din cercetare) trebuie să fie analizate.

Fie vârful este atașat la vârful . Putem presupune că toate vârfurile nu sunt vârfuri mediane, deoarece în caz contrar distanța de la vârful până la cel puțin unul din ele n-ar întrece distanța de la până la vârful . Deci, aceste vârfuri pot fi (excluse din cercetare) în toate coloanele . Trebuie să se țină cont de faptul că aceste vârfuri se exclud temporar și urmează să fie restabilite în fiecare caz când se modifică aranjarea vârfului față de .

Dacă din cercetare sunt excluse primele t elemente ale coloanei j care corespund vârfului neatașat și elementul este vârf mediană, atunci vârful trebuie să fie atașat la vârful . În acest caz nu apare necesitatea de a cerceta alte posibilități de atașare, până când careva dintre primele t elemente va putea fi restabilit (ca rezultat al modificării în aranjările precedente ale vârfurilor, ceea ce va afecta mulțimea vârfurilor „excluse”). Această concluzie este o consecință directă a punctelor 2 și 3.

Dacă la o etapă q a procesului de căutare va fi construită mulțimea din p vârfuri mediane (rezultat al procedurii de atașare a vârfurilor), atunci fiecare vârf rămas nearanjat poate fi atașat la cel mai apropiat vârf mediană. Este evident că aceasta este soluția particulară optimală, corespunzătoare atașării efectuate a vârfurilor. La pasul următor al procedurii pasul de întoarcere, trebuie modificată aranjarea vârfurilor, obținută la etapa q.

3.4.3. Algoritmul euristic

O metodă euristică de determinare a p-medianei a fost propusă de Teitz și Bart [55] .

Metoda constă în alegerea aleatoare a p vârfuri care constituie mulțimea inițială S și este o aproximare a p-medianei . Apoi se verifică dacă există un vârf care ar putea substitui careva vârf ca vârf mediană. În acest sens se construiește o mulțime nouă și se compară numerele de transfer și. Dacă , atunci vârful se înlocuiește cu . Astfel din mulțimea S se obține o mulțime nouă care aproximează mai bine p-mediana . Similar se procedează cu mulțimea , ș.a.m.d. până când se va construi o mulțime, nici un vârf al căreia nu poate fi substituit cu un vârf din astfel încât ca să se obțină o mulțime nouă cu un număr de transfer mai mic decât . Mulțimea este aproximația mulțimii .

Descrierea algoritmului

În mod aleator se construiește mulțimea S din p vârfuri care se consideră aproximație inițială a p-medianei. Toate vârfurile se consideră „necercetate”.

Se alege un vărf necercetat și pentru fiecare vârf se calculează „sporul” care corespunde substituirii vârfului cu vârful :

(3.4.3.1)

Se determină.

(i) Dacă , atunci considerăm că vârful este „cercetat” și trecem la pasul 2.

(ii) Dacă , atunci considerăm că vârful este „cercetat”, modificăm mulțimea , și trecem la pasul 2.

Repetăm pașii 2 și 3 până când toate vârfurile din vor fi „cercetate”. Dacă la executarea procesului descris s-a efectuat doar pasul 3(i), adică nu s-a realizat nici o substituire de vârfuri, atunci trecem la pasul 5. În caz contrar (dacă s-a efectuat cel puțin o substituire de vârfuri) toate vârfurile din se declară „necercetate” și trecem la pasul 2.

Algoritmul își încheie lucrul. Mulțimea S este o aproximație acceptabilă a p-medianei .

Evident, algoritmul descris nu totdeauna asigură o soluție optimală. Pentru a ilustra aceasta vom cerceta graful neorientat din figura 3.4.3.1, în care ponderile vârfurilor grafului se consideră egale cu 1, iar numerele atașate muchiilor reprezintă ponderile acestora. Vom determina o 2-mediană a acestui graf. Dacă în calitate de mulțime inițială S se ia mulțimea , cu numărul de transfer , atunci nici o substituire a unui singur vârf în S nu va genera o mulțime cu numărul de transfer mai mic decât 8. Însă mulțimea nu este 2-mediană a grafului dat. Există două 2-mediane a acestui graf, și anume și , cu numărul de transfer .

Vom spune că mulțimea S din p vârfuri este -optimală dacă substituirea oricăror vârfuri a mulțimii S cu vârfuri ce nu aparțin mulțimii S nu generează o mulțime nouă cu numărul de transfer mai mic decât cel al lui S. Evident, dacă S este p-mediana a unui graf, atunci S este p-optimală. Deasemenea este clar că dacă este mulțime -optimală, iar mulțimea este -optimală, atunci , unde .

Utilizând noțiunile introduse, soluția obținută la aplicarea algoritmului descris mai sus este 1-optimală. Există algoritmi similari și pentru generarea soluțiilor 2-optimale, 3-optimale, etc. Pentru verificarea -optimalitatea mulțimii S e necesar de realizat

substituiri și calculări ale numerelor de transfer . Acest număr crește repede odată cu creșterea valorii lui . De aceea, astfel de algoritmi practic nu pot fi utilizați pentru .

Concluzie

În rezultatul efectuării acestei lucrări și studierii asupra temei date am putut să trag anumite concluzii, și anume:

Deși Teoria Grafelor este un domeniu relativ tânăr al matematicii, se întâlnește în diverse domenii de activitate, care pot fi expuse prin scheme orientate, în așa probleme cum ar fi problemele de repartiție,planificare, conducere și control, probleme de psihologie, chimie sau biologie.

Anume varietatea situațiilor atunci când apare graful a impus abstractizarea acestei noțiuni, ajungându-se în final la o disciplină de sine stătătoare, care s-a dezvoltat recent, care datorită aplicabilității sale și a procedeelor eficace de rezolvare, a luat o mare amploare.

Această teorie își găsește numeroase aplicații în diverse probleme practice: la rezolvarea problemelor de transport, problemelor privind fluxuri șe rețele, precum și a problemelor de amplasare, probleme ce au fost minuțios cercetate în această lucrare.

Problemele de amplasare se întâlnesc foarte des în activitatea astfel apare problema soluționării lor eficace. Aici intervine problema centrului, care are un rol destul de important deoarece, de exemplu în cazul amplasării punctelor de deservire este foarte important de ale aranja astfel încât distanța maximală de la client la centru să fie minimală. La fel și problema medianei,se pune problema găsirii unui vârf încât suma distanțelor de la acest centru până la celelalte vârfuri ale grafului să fie minimală posibilă.

Bibliografie

1)N. Christofides, Graph theory. An algorithmic approach (AP, 1975)

2) S. Cataranciuc, Teoria grafurilor în probleme si aplicatii, USM, Chisinău,2004

3) T.C.E. Cheng, Liying Kang, , C.T. Ng, An improved algorithm for the p-center problem on interval graphs with unit lengths, Computers and Operations Research, Volume 34 Issue 8, August, 2007

4) F. Harary, Graph Teory ,Editura Мир,Moscova,1973(in russian)..

P.S. Soltan, D.K. Zambitchi, Ch. F. Prisăcaru, Extremal problems on graphs and algorithms of their solving, Chisinău, 1974,(in russian).

6) Reza Zanjirani Farahani, Masoud Hekmatfar – Editors, Facility Location, Concepts, Models, Algorithms and Case Studies, Springer-Verlag Berlin Heidelberg 2009.

7) S. Bespamyatnikh, Binay Bhattacharya, Mark Keill, David Kirkpatrick, Michael Segal, Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs, NETWORKS, Vol. 39(3), 2002.

8) S. Cataranciuc, A. Niculită, Aspecte algoritmice ale teoriei grafurilor. Partea I, CEP USM, Chisinău 2006.

9) S. Cataranciuc, A. Niculită, Aspecte algoritmice ale teoriei grafurilor. Partea II, CEP USM, Chișinău 2012.

Bibliografie

1)N. Christofides, Graph theory. An algorithmic approach (AP, 1975)

2) S. Cataranciuc, Teoria grafurilor în probleme si aplicatii, USM, Chisinău,2004

3) T.C.E. Cheng, Liying Kang, , C.T. Ng, An improved algorithm for the p-center problem on interval graphs with unit lengths, Computers and Operations Research, Volume 34 Issue 8, August, 2007

4) F. Harary, Graph Teory ,Editura Мир,Moscova,1973(in russian)..

P.S. Soltan, D.K. Zambitchi, Ch. F. Prisăcaru, Extremal problems on graphs and algorithms of their solving, Chisinău, 1974,(in russian).

6) Reza Zanjirani Farahani, Masoud Hekmatfar – Editors, Facility Location, Concepts, Models, Algorithms and Case Studies, Springer-Verlag Berlin Heidelberg 2009.

7) S. Bespamyatnikh, Binay Bhattacharya, Mark Keill, David Kirkpatrick, Michael Segal, Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs, NETWORKS, Vol. 39(3), 2002.

8) S. Cataranciuc, A. Niculită, Aspecte algoritmice ale teoriei grafurilor. Partea I, CEP USM, Chisinău 2006.

9) S. Cataranciuc, A. Niculită, Aspecte algoritmice ale teoriei grafurilor. Partea II, CEP USM, Chișinău 2012.