Elemente de Teoria Grafelor

INTRODUCERE

Lumea contemporană este produsul unui continuu progres, astfel creându-se noi tehnologii şi metode de modelare. În acelaşi timp, însă, apar şi o varietate de probleme unde se cere să se construiască sisteme complexe cu ajutorul unei anumite ordonări ale elementelor. Acestea sunt planificarea calendaristică a producţiei, probleme logice, probleme de construire a sistemelor de comunicaţii şi cercetarea procesului de transmitere a informaţiei, probleme de alegere a structurii grupurilor sociale, probleme din teoria jocurilor etc.

Complexitatea proceselor economice, cerinţele mereu crescânde ale conducerii şi planificării ştiinţifice a economiei într-un avânt fără precedent, impun cunoaşterea soluţiilor optime din punct de vedere economic, cu maximum de precizie. În soluţionarea unor astfel de probleme complexe nu mai pot fi utilizate metodele empirice care pot conduce la pagube materiale considerabile, ci trebuie folosite metode matematice moderne. Se poate afirma că în momentul de faţă acţiunea de folosire a matematicilor moderne se extinde cu maximum de eficienţă la toate nivelele de decizie.

Grafele se întâlnesc în cele mai diverse domenii de activitate, care pot fi concretizate prin scheme orientate, cum sînt probleme de repartiţie, probleme de planificare, conducere şi control, probleme de psihologie şi altele tot atât de importante.

Varietatea de situaţi în care apare graful a impus abstractizarea acestei noţiuni, ajungîndu-se în cele din urmă la o disciplină de sine stătătoare.

Aşa se explică faptul că astăzi grafele sînt folosite cu succes în discipline matematice ca algebra, calculul probabilităţilor, teoria funcţiilor etc.

Metodele folosite de teoria grafelor permit o soluţionare intuitivă şi, ca atare, uşoară şi rapidă, a unor probleme complexe care, altfel, ar necesita operaţii multiple şi abstracte. Se poate spune pe drept cuvânt, că teoria grafelor poate fi folosită totdeauna în probleme în care se cere optimizarea unei acţiuni.

Ca disciplină de sine stătătoare, teoria grafelor s-a constituit destul de recent şi cu toate acestea, datorită vastului câmp de aplicabilitate, precum şi datorită procedeelor eficace de investiţie ce ajută intuiţia, ea aluat o mare amploare, constituind la ora actuală un instrument de lucru util pentru economişti, ingineri, tehnicieni etc.

Una primele lucrări cu referire la teoria grafelor a fost cea a lui L. Euler în vestitul raţionament despre podurile din Kooenegsperg. Însă acest articol al anului 1736 al lui L. Euler a fost unicul în decursul a aproximativ o sută de ani. Interesul pentru problemele de teoria grafelor a reapărut la mijlocul secolului XIX şi a fost într-o mare parte concentrat în Anglia. Unele ştiinţe au influenţat asupra acestui fapt datorită cercetărilor reţelelor electrice, modelului cristalelor şi structura moleculelor.

Bazele teoriei grafelor ca disciplină matematică însă au fost puse de matematicianul ungar D. Kenig, autorul primei monografii în 1936, în care grafele sînt redate ca obiecte matematice abstracte şi în care sînt depuse bazele teoriei grafelor generale.

Primul ciclu de lecţii despre relaţiile binare şi grafe a fost propus societăţii americane matematice în decursul sesiunii de vară în Cicago în 1942. În acea perioadă manuscrisele acestor lecţii nu a fost pregătită pentru tipărire din cauza unor lucrări mai urgente, acestea apărând mai târziu ca surse accesibile.

I. NOŢIUNI DE BAZĂ ÎN TEORIA GRAFELOR

1. ELEMENTE INTRODUCTIVE

Grafele pot fi privite ca obiecte abstracte; studiate cu un aparat matematic propriu. Pe de alta parte; ele sunt utilizate in modelarea si studiul unor sisteme sau pentru rezolvarea de probleme din diverse domenii ale activităţii umane: informatica; economie; armata; fizica; chimie; transporturi; geografie; proiectare; etc. Teoria grafelor este atât un obiect de cercetare teoretica; cat si un furnizor de algoritmi si metode generale pentru rezolvarea unor probleme concrete (practice).Succesul depinde de capacitatea utilizatorului de a asocia problemei sale un graf si de a-si formula in termenii teoriei grafelor.

Teoria grafelor este o ramură a teoriei mulţimilor, destul de recentă care s-a dovedit foarte utilă şi cu aplicaţii în domenii variate: economie, chimie organică, organizare, psihologie, anumite domenii ale artei etc.

Exemplul 1. Să presupunem că se pune problema construirii unei şosele între două centre industriale, notate cu x0 şi x11, care ar putea să treacă prin localităţile x1, x2, x3, x4, x5, x6, x7, x8, x9, x10. Cunoscând costul lucrării pentru porţiunile de şosea care leagă între ele diverse localităţi (xi), să se determine traseul şoselei dintre localităţile x0 şi x11 astfel încât cheltuielile totale pentru efectuarea lucrării să fie minime.

Fig. I.1.1

Dacă reprezentăm localităţile prin puncte, iar porţiunile de şosea prin arce, atunci obţinem schema din figura I.1.1. Putem presupune că ar fi vorba de o regiune muntoasă cu şosele înguste pe care sensul de circulaţie este unic, de unde rezultă orientarea în sens unic a arcelor de pe figură.

Exemplul dat a permis asocierea unor figuri constituite din puncte şi arce orientate (săgeţi) care unesc perechi din aceste puncte.

În sens matematic, aceste săgeţi pot simboliza o aplicaţie F pentru care extremitatea iniţială a arcului reprezintă argumentul sau variabila, iar extremitatea finală a aceluiaşi arc reprezintă imaginea sau valoarea aplicaţiei.

Tot din figuri reiese că oricărui punct (sau vârf) al mulţimii X = {xi} îi corespunde, prin aplicaţia F, o submulţime a aceleiaşi mulţimi X.

Astfel, dacă considerăm figura I.1.2, distingem corespondenţele următoare

Fig. I.1.2

Uneori, în aplicaţii, este util să se cunoască semnificaţia notaţiei . Din exemplul de mai înainte s-a văzut că

Prin vom înţelege

Analog,

În general

Dacă în figura I.1.2 se schimbă sensul tuturor săgeţilor, atunci se obţine imaginea reciprocă F-1.

Pentru figura I.1.2 avem :

= ; ={x1, x3}; ={x2}; ={x3}; ={x6, x7, x3}; ={x1, x5}; ={x1, x2, x7}

În general, o mulţime X, de puncte sau vârfuri, şi o aplicaţie F, a mulţimii X în ea însăşi, definesc un graf pe care-l vom nota G=(X, F). Această notaţie pune în evidenţă atât mulţimea X a vârfurilor cît şi aplicaţia F.