Teoria Grafurilor

Introducere

Teoria grafurilor este o ramură a matematicii moderne cu caracter aplicativ şi derivă din teoria mulţimilor, având originile în rezolvarea unor probleme neînsemnate pentru dezvoltarea matematicii în ansamblul ei. Primul matematician care a început studiul acestei discipline este D.Kaning, el fiind şi cel care a numit-o teoria grafurilor sau teoria grafilor.

Rapida dezvoltare a teoriei grafurilor s-a datorat şi în mare măsură evoluţiei spectaculoase a cercetării operaţionale, care urmăreşte găsirea indicilor de eficacitate maximă indiferent de domeniul de activitate. Solicitată a participa la procesul de optimizare a fenomenelor, teoria grafurilor şi-a constituit un fond de teoreme proprii pe baza cărora s-au elaborat o mulţime de algoritmi c formează astăzi instrumentul specific al acestei teorii.

În stadiul ei actual de dezvoltare, teoria grafurilor se desprinde de topologie şi, deşi foloseşte obiectele algebrei şi ale teoriei mulţimilor, nu se mai poate spune că face parte din aceste discipline.

Evoluţia teoriei grafurilor seamănă cu cea a calculului probabilităţilor. Apărută prin analizarea unor jocuri distractive, rezultatele obţinute au constituit embrionul teoriei de mai târziu, pentru ca în prezent aceasta să ajungă să fie necesară în mai toate domeniile de activitate. Astfel, numai în matematici, grafurile sunt utilizate în algebra booleană, în topologie, în combinatorie şi în calculul probabilităţilor – pentru studiul lanţurilor Markov, în care matricea de trecere se reprezintă prin grafuri – în programarea liniară la analiza problemelor de transport şi repartiţie, în programarea dinamică pentru determinarea politicii optime, în teoria jocurilor, în teoria informaţiei – la studiul semnelor şi codurilor.

Analiza şi prezentarea învăţămintelor celei de-a doua conflagraţii mondiale au prilejuit specialiştilor militari o atitudine critică la adresa inoportunităţii şi ineficienţei unor măsuri întreprinse de factorii de decizie.

Ca obiect al ştiinţei militare, lupta armată ridică astăzi numeroase probleme de o factură deosebită, a căror soluţionare nu se mai poate întemeia pe metode empirice şi, în nici un caz, nu se mai poate limita la acestea. În prezent mijloacele tehnice, mereu mai complexe, mai sofisticate, încorporând realizări de vârf ale ştiinţei şi tehnologiei, s interpun între obiectul şi subiectul acţiunilor de luptă. În paralel ponderea operaţiilor logice, a modelelor de abstractizare, formalizare şi modelare, a raţionamentului strategic, a tehnicilor moderne de calcul şi informare se află într-o continuă creştere.

Pornind şi de la faptul că prima lucrare în domeniu publicată în România, “Teoria Grafelor”, semnată de Petre Irinescu şi Alexandru Roşu în anul 1968 a apărut la Editura Militară, voi încerca să arăt că teoria grafurilor reprezintă un instrument de optimizare şi rezolvare de probleme în domeniul militar, în general şi în acţiunile subunităţilor de artilerie, în special.

Lucrarea de faţă a fost structurată pe 6 capitole în care voi încerca să prezint câteva posibilităţi de aplicare a teoriei grafurilor în optimizarea acţiunilor subunităţilor de artilerie. Primul capitol conţine noţiuni generale privind teoria grafurilor, în timp ce al doilea capitol oferă unele exemple de algoritmi de optimizare cu aplicabilitate în domeniul militar. În capitolul trei am prezentat câteva posibilităţi de aplicare a teoriei grafurilor în domeniul militar, pentru ca în capitolele patru, cinci şi şase să prezint două aplicaţii ale teoriei grafurilor în optimizarea acţiunilor subunităţilor de artilerie şi un program informatic de rezolvare printr-un algoritm de optimizare a unor probleme ce pot apărea în acţiunile subunităţilor de artilerie.

1.Noţini introductive privind teoria grafurilor

1.1. Generalităţi

Se numeşte graf, ansamblul format dintr-o mulţime X şi o aplicaţie multivocă Γ a lui X în X. Se notează G=(X,Γ).

Numărul elementelor mulţimii X determină ordinul graficului finit. Dacă cardX=n, graful G=(X,Γ) se numeşte graf finit de ordinul n.

Elementele mulţimii X se numesc vârfurile grafului. Geometric, vârfurile unui graf le reprezentăm prin puncte.

Notă: Γ este o aplicaţie multivocă ce ne defineşte pe X o relaţie binară R  R=(x,y)|xRy, x,yX . Dacă AX şi Γ:XX numim imaginea lui A prin Γ mulţimea: