Teoria grafurilor

Teoria grafurilor este una din subsecțiunile matematicii, principala caracteristică distinctivă a acesteia fiind metoda geometrică în studiul obiectelor. Fondatorul său este considerat a fi matematician renumit L. Euler.

Aplicarea teoriei graficului la sfârșitul secolului al 19-lea, a fost redus la soluționarea problemelor interesante și a atras atenția publicului considerabilă. Pornind de la secolul 20, atunci când teoria grafurilor a fost format ca o disciplină matematică independentă, a fost utilizat pe scară largă în domenii cum ar fi cibernetica, fizica, logistica, programare, biologie, electronica, transport și sisteme de comunicații.

Concepte de bază ale teoriei grafurilor

Graficul este unul de bază. În terminologie, se poate întâlni un astfel de concept ca o rețea identică cu un grafic. Ultimul este un număr net de puncte, adică vârfuri și segmente, adică marginile, ambele capete ale cărora corespund unui anumit număr de puncte. Teoria grafurilor nu face un sens clar în valorile marginilor și vârfurilor. De exemplu, orașele și drumurile care le conectează, unde primele sunt vârful graficului, iar al doilea - marginile. Mai multă importanță teoretică este dată arcurilor. Dacă marginea are o direcție, atunci are numele unui arc, dacă graficul cu marginile orientate, se numește digraph.

În terminologia teoriei, se remarcă și următoarele concepte:

Un subgraf este un grafic, toate muchiile și vârfurile acestuia fiind printre vârfuri și muchii.

Un grafic conectat este unul care are un lanț care le leagă pentru două vârfuri diferite.

Un graf conectat ponderat este unul a cărui funcție de greutate este dată.

Un arbore este un grafic conectat, fără cicluri.

Scheletul este un subgraf care este un copac.

In imaginea graficului în notația definit planul este utilizat: punctul vertex selectat corespunde suprafeței elementare și dacă marginea este între nodurile, punctele respective sunt combinate segment. Dacă graficul este orientat, aceste segmente sunt înlocuite cu săgeți.

Dar nu comparați imaginea graficului cu el, adică cu o structură abstractă, pentru că un grafic poate fi dat mai mult decât o reprezentare grafică. Se dă un desen pe plan, pentru a vedea care perechi de vârfuri sunt unite de margini și care nu sunt.

Printre unele probleme ale teoriei grafurilor se numără:

1. Sarcina celui mai scurt lanț (înlocuirea echipamentelor, plasarea ambulanțelor și stațiilor telefonice).
2. Problema debitului maxim (ordonarea mișcării într-o rețea dinamică, distribuirea muncii, organizarea capacității).
3. Sarcina de acoperire și ambalare (plasarea punctelor de dispecerizare).
4. Colorarea în grafice (plasarea memoriei pe computerele electronice).
5. Comunicarea de rețele și grafice (crearea unei rețele de comunicații, analiza rețelelor de comunicații).

În prezent, este imposibil să programezi majoritatea problemelor fără a cunoaște teoria grafurilor. Acest lucru face mai ușor și mai ușor să lucrați cu un computer.

Programarea folosește o mulțime de structuri și metode universale pentru rezolvarea problemelor, iar una dintre ele este teoria graficelor. Valoarea sa este greu de supraestimat. Teoria grafică în programare facilitează găsirea informațiilor, optimizarea programelor, conversia și distribuirea datelor. Datorită algoritmilor teoriei, este posibil să le aplicăm și să le evaluăm în uz pentru rezolvarea problemelor specifice, pentru a modifica algoritmul fără a reduce gradul de certitudine matematică a versiunii finale a programului.

O proprietate importantă a unui sistem sau model de control este o colecție relații binare atunci când tastați acțiuni și unități de date. Aceste structuri sunt singurele părți ale programelor și informațiile pe care le transformă. Prin urmare, graficele sunt baza unei construcții pentru programator.