Teoria graficului este una dintre subsecțiuni.matematica, a cărei caracteristică distinctivă este metoda geometrică în studiul obiectelor. Fondatorul acesteia este considerat a fi celebrul matematician L. Euler.
Aplicarea teoriei graficului până la sfârșitul secolului XIXa venit la rezolvarea problemelor distractive și nu a atras atenția generală semnificativă. Începând cu secolul XX, când teoria graficului a fost formată într-o disciplină matematică independentă, a găsit o aplicație largă în domenii științifice precum cibernetica, fizica, logistica, programarea, biologia, electronica, sistemele de transport și comunicații.
Conceptele de bază ale teoriei graficului
Baza este un grafic.În terminologie, se poate întâlni un astfel de concept ca o rețea identică cu un grafic. Acesta din urmă este un număr necompletat de puncte, adică vârfuri și segmente, adică margini, ambele capete corespund unui număr dat de puncte. Teoria graficului nu are niciun sens în valorile muchiilor și vârfurilor. De exemplu, orașele și drumurile care le leagă, unde primul sunt vârfurile graficului, iar al doilea sunt marginile. O mai mare importanță în teorie este acordată arcurilor. Dacă o margine are o direcție, atunci are numele unui arc, dacă un grafic cu marginile orientate, se numește digraf.
În terminologia teoriei se disting și următoarele concepte:
Un subgraf este un grafic ale cărui toate marginile și vârfurile sunt printre vârfurile și marginile.
Un grafic conectat este unul cu un lanț care le leagă pentru două vârfuri diferite.
Un grafic conectat ponderat este unul cu o funcție de greutate.
Un arbore este un grafic conectat, fără cicluri.
Un schelet este un subgraf care este un copac.
La trasarea unui grafic pe un plannotație definită: vertexul selectat corespunde unui punct de pe suprafața cea mai simplă, iar dacă există o margine între vârfuri, atunci punctele corespunzătoare sunt unite de un segment. Dacă graficul este orientat, aceste segmente sunt înlocuite cu săgeți.
Dar nu comparați imaginea graficului cu eade noi înșine, adică cu o structură abstractă, deoarece mai mult de o reprezentare grafică poate fi dată unui singur grafic. Desenul de pe plan este dat pentru a vedea ce perechi de vârfuri sunt unite de margini și care nu.
Printre unele probleme ale teoriei graficului, există:
- Sarcina celui mai scurt lanț (înlocuirea echipamentului, amplasarea ambulanțelor și centrale telefonice).
- Problema fluxului maxim (eficientizarea traficului într-o rețea dinamică, distribuția muncii, organizarea lățimii de bandă).
- Problema acoperirilor și a ambalajelor (plasarea centrelor de control).
- Colorarea în grafice (alocarea memoriei pe computere electronice).
- Rețele și grafice de comunicare (crearea unei rețele de comunicare, analiza rețelelor de comunicații).
În prezent este imposibil de programat majoritatea sarcinilor fără cunoașterea teoriei graficului. Acest lucru facilitează și simplifică munca cu computerele.
Programarea folosește multe structuri șimetode universale pentru rezolvarea problemelor, iar una dintre ele este teoria graficului. Valoarea sa este greu de supraestimat. Teoria graficului în programare vă permite să simplificați căutarea de informații, să optimizați programele, să convertiți și să distribuiți date. Datorită algoritmilor teoriei, devine posibilă utilizarea și evaluarea acestora pentru a rezolva probleme specifice, pentru a modifica algoritmul fără a reduce gradul de fiabilitate matematică a versiunii finale a programului.
O proprietate importantă a unui sistem sau model de controleste un set de relații binare într-un set de 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 construcției pentru programator.
