Utilizând grafice, puteți rezolva problemele

Teoria graficelor - a apărut la sfârșitul secolului al XVIII-lea și a devenit acum un instrument matematic foarte puternic și în continuă dezvoltare.

În multe cazuri, viața unui vechi obicei, ne împinge să tragă pe hârtie, punctele care reprezintă populația, orașele, produse chimice și așa mai departe. D. și conectați puncte cu linii sau săgeți denotă o relație. Astfel de scheme se găsesc peste tot sub diferite denumiri: sociogramă (în psihologie), simplex (topologie), circuitul electric (in fizica), organigrama (în economie), rețele de comunicații, arbori de familie, etc. D. Koenig, fără îndoială primul, a sugerat numirea unor astfel de scheme "grafice" și studierea sistematică a proprietăților lor.








Primul dintre conceptele de bază ale teoriei grafurilor este noțiunea de vertex. În teoria graficelor, se presupune că este primară și nu este definită. Nu este greu să vă imaginați la nivelul dvs. intuitiv. De obicei, vârfurile graficului sunt reprezentate în mod clar ca cercuri, dreptunghiuri prin alte figuri (figura 1). Cel puțin un vârf trebuie să fie prezent în fiecare grafic.

Un alt concept de bază al teoriei grafurilor este arcul. În mod normal, arcele reprezintă segmente de linii drepte sau curbe care leagă vârfurile. Fiecare dintre cele două capete ale arcului trebuie să coincidă cu un anumit vârf. Cazul în care ambele capete ale arcului coincid cu același vârf nu sunt excluse. De exemplu, în figura 2 - imaginile admisibile ale arcurilor și în figura 3 - inadmisibile:



În teoria graficelor, se folosesc două tipuri de arce: direcționare non-direcțională sau orientată (orientată). Un grafic care conține numai arce orientate se numește un grafic orientat sau un digraph.

Arcurile pot fi unidirecționale, fiecare arc având o singură direcție sau bidirecțional.

În majoritatea aplicațiilor, este posibil, fără pierderea sensului, înlocuirea arcului nedirecționat cu un arc bidirecțional și a arcului bidirecțional cu două arce unidirecționale. De exemplu, după cum se arată în Fig. 4.


Ca regulă generală, grafic sau imediat construit astfel încât toate muchiile să aibă aceleași caracteristici direcționale (de exemplu, toate - one-way), sau redus la o astfel de formă de transformări. Dacă arcul AB este îndreptat, atunci înseamnă că de la cele două capete unul (A) este considerat începutul, iar cel de-al doilea (B) este sfârșitul. În acest caz, se spune că începutul arcului AB are un nod A, iar capătul - Vertex B, în cazul în care arcul este direcționat de la A la B, sau că - în arc veniturile AB din nodurile A și partea B (Figura 5).


Două vârfuri ale graficului, conectate printr-un arc (uneori, indiferent de orientarea arcului) se numesc noduri adiacente.

Un concept important în studiul grafurilor este conceptul unei căi. Cale A1, A2. An este definit ca o secvență finită (trupă) a nodurilor A1, A2. An și arce A1, 2, A2, 3. An-1, n conectând consecutiv aceste vârfuri.

Un concept important în teoria graficelor este conceptul de conexiune. Dacă pentru oricare dintre cele două vârfuri ale graficului există cel puțin o cale de conectare - se spune că graficul este conectat.







De exemplu, dacă desenați un grafic al sistemului circulator uman, în cazul în care nodurile corespund organelor interne, iar arcul electric - capilare de sânge, atunci acest grafic este evident conectat. Este posibil să afirm că sistemul circulator al celor două persoane arbitrare este un grafic incoerent? Evident că nu, pentru că în natură există așa-numitele. "Gemenii siamezi".

Conectivitatea nu poate fi doar o caracteristică calitativă a graficului (conectată / neconectată), ci și cantitativă.

Se spune că un grafic este legat de K dacă fiecare vârf al lui este conectat cu K al altor vârfuri. Uneori vorbesc grafice slabe și puternic conectate. Aceste concepte sunt subiective. Cercetătorul numește graficul puternic conectat dacă, pentru fiecare dintre vârfurile sale, numărul de vârfuri adiacente, potrivit cercetătorului, este mare. Uneori conectivitatea este definită ca o caracteristică nu a fiecăruia, ci a unui vârf (arbitrar). Apoi, există definiții ale tipului: se spune că un grafic este legat de K dacă cel puțin unul dintre vârfurile lui este conectat cu K al altor vârfuri.

De exemplu, figura copilului unei persoane (Figura 6) este un grafic cu o conectivitate maximă de 4.


O altă caracteristică a graficului, studiată într-o serie de probleme, este adesea numită puterea unui grafic. Această caracteristică este definită ca numărul de arce care leagă cele două noduri. În acest caz, arcele care au o contra-direcție sunt adesea considerate separat.

De exemplu, în cazul în care vârfurile graficului reprezintă informația de prelucrare a nodurilor și arcelor - canalele de comunicare cu sens unic între ele, fiabilitatea sistemului nu este determinată de numărul total de canale, iar cel mai mic număr de canale în orice direcție.

Puterea, cum ar fi conectivitatea, poate fi definită atât pentru fiecare pereche de vârfuri ale graficului, cât și pentru o pereche (arbitrară).

Caracteristica esențială a unui grafic este dimensiunea sa. Acest termen este de obicei înțeles ca numărul de vârfuri și arce existente în grafic. Uneori, această valoare este definită ca suma numărului de elemente de ambele tipuri, câteodată ca produs, uneori ca numărul elementelor de un singur tip (unul sau altul).


Obiectele modelate prin grafice au o natură foarte diversă. Dorința de a reflecta această specificitate a dus la descrierea unui număr mare de soiuri de grafice. Acest proces continuă în prezent. Mulți cercetători, în scopurile lor specifice, introduc noi soiuri și își realizează cercetarea matematică cu mai mult sau mai puțin succes.

În centrul acestei diversități există câteva idei destul de simple, pe care le vom vorbi aici.

Graficele de colorare reprezintă un mod foarte popular de modificare a graficelor.

Această tehnică vă permite să măriți vizibilitatea modelului și să creșteți încărcătura matematică. Metodele de colorare pot fi diferite. Conform uneia sau altei reguli, ambele arce și vârfuri sunt colorate. Pictura poate fi definită o dată sau modificată în timp (adică atunci când graficul dobândește proprietăți); culorile pot fi transformate prin anumite reguli etc.

De exemplu, graficul să fie un model al circulației sanguine umane, în care vârfurile corespund organelor interne și arcadei capilarelor sanguine. Vom picta arterele în roșu, iar venele - în albastru. Apoi, următoarea afirmație este evidentă: în graficul examinat (Figura 8) există doar două vârfuri cu arce roșii de ieșire (în figură, culoarea roșie este arătată cu îndrăzneală).

Uneori elementele obiectului, modelate de vârfuri, au un caracter semnificativ diferit. Sau la elementele existente în obiect în procesul de formalizare se dovedește utilă adăugarea unor elemente fictive. În acest caz și în alte cazuri, nodurile unui grafic sunt împărțite în mod natural în clase (părți). Un grafic care conține vârfuri de două tipuri se numește bipartit și așa mai departe. În acest caz, numărul constrângerilor de grafic este introdus reguli referitoare la relația vârfurilor de diferite tipuri. De exemplu: "Nu există nici un arc care să conecteze vârfurile de același tip." Una dintre soiurile de grafice de acest tip este numită "plasa Petri" (Figura 9) și este destul de larg răspândită. Plasele Petri vor fi discutate mai detaliat în următorul articol din această serie.


Noțiunea de finețe poate fi aplicată nu numai la vârfuri, ci și la arce.


Utilizând grafice, puteți rezolva problemele.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: