Ce este teoria graficelor și cum este definit un grafic ca atare?

În 1736, pe baza lucrării fizicianului-matematician elvețian Leonhard Euler (1707-1783), s-a observat că o succesiune de vârfuri definește o cale, totuși, dacă respectiva cale constă din vârfuri diferite fără margini repetate, se numește cale sau cale eulerian; dacă în plus ajungem la punctul de plecare, parcurgând fiecare muchie o singură dată, atunci avem un ciclu (circuit) eulerian.

Citat (APA)

alexander barraza | iul. 2022
Licenta in fizica

La rândul său, definim un grafic ca o pereche ordonată (MERGE) Unde v desemnează setul (nevid) al tuturor nodurilor sau nodurilor unui graf, în timp ce A desemnează mulțimea (poate fi goală) a tuturor muchiilor sau liniilor care unesc vârfurile unui graf. Elementele setului A poate fi desemnată ca o pereche neordonată {v, w} unde v și w sunt elemente (noduri sau vârfuri) ale v, în acest fel se spune atunci că v și w sunt vârfuri adiacente (sunt unite printr-o muchie).

Teoria grafurilor ia naștere din răspunsul dat de Euler la o problemă a ingeniozității populare care se întreba cum să treacă cele șapte poduri care a unit două insule ale comunității Königsberg (parte din Germania la acea vreme, iar în prezent Kaliningrad, în Rusia), între ele și cu continent fără a folosi două ori același pod și ajungând la punctul de plecare (situat pe continent) oricare ar fi acesta, determinând că în acest caz, în cele din urmă, nu ar putea.

Problema celor șapte poduri din Königsberg

Euler a modelat Königsberg ca un grafic în care fiecare punct (vertex sau nod) reprezintă un pod și fiecare linie (margine) o cale pe uscat:

Care este soluția la această problemă?

nu există unul soluţie care îndeplinește condițiile impuse, deoarece, după cum a arătat Euler, vârfurile nu sunt de grad par, adică un număr par de linii nu afectează fiecare punct _[3]. Se pare că nu putem face mare lucru cu o structură definită la fel de simplu ca aceasta, totuși, așa cum este adesea cazul în matematica, Uneori lucrurile nu sunt ceea ce par. Astfel, una dintre cele mai prolifice, transversale și interdisciplinare domenii _[4] a cunoașterii umane, teoria grafurilor.

Grafice euleriene sau cu traiectorie euleriana?

Următoarele grafice au toate căi euleriene _[5]. Au toate ciclurile euleriene?

Să luăm al treilea grafic:

Să numărăm vârfurile:

Vedem atunci că calea definită de secvența {3,4,6,2,1,3,7,6,5,4,2} este o cale euleriana, deoarece parcurge întregul grafic fără muchii repetate, dar nu este un ciclu eulerian, deoarece nu ajunge la punctul de plecare. Ce s-ar fi întâmplat dacă am numerota vârfurile diferit? Nu mult, cu excepția faptului că acum calea ar fi definită printr-o succesiune diferită. Ce s-ar fi întâmplat dacă am urma alte căi decât cea propusă în soluția noastră inițială? La această întrebare este puțin mai complex de răspuns și implică algoritmi de care inginerii software sunt de obicei încântați. programare.

Pentru o dovadă mai riguroasă a ceea ce este expus aici trebuie să ne referim la următorul rezultat:

"Fi G un grafic conectat _[6]. Atunci da G ia o circuit Euler, gradul fiecărui vârf este par, în timp ce dacă G are o cale Euler, G are exact două vârfuri de grad impar _[7] (exact vârfurile unde începe și se termină calea)".

Putem apoi verifica că, de fapt, în graficul pe care îl luăm, doar vârfurile 3 și 6 au un grad impar (acest ar avea loc chiar dacă numerotarea vârfurilor ar fi fost diferită), prin urmare, graficul respectiv are o cale eulerian _[8]. Pentru graficele rămase putem proceda într-un mod analog și putem verifica dacă într-adevăr au căi și Cicluri euleriene, sau altfel spus, putem desena astfel de grafice fără să luăm creionul și să repetăm linii? Răspunsul la această întrebare poate fi dedus din ceea ce a fost deja explicat până acum, însă constituie un exercițiu interesant în ceea ce privește motricitatea fină, ingeniozitatea și răbdarea, invit cititorul să găsească și să deseneze grafice de 6 sau mai multe vârfuri cu traiectorie Eulerian.

Există și alte tipuri de grafice? Are teoria grafurilor aplicații în lumea „reală”?

Aceste grafice pe care le-am revizuit foarte pe scurt, sunt doar unul dintre numeroasele tipuri de grafice pe care le găsim în teoria grafurilor. Putem găsi și grafice precum arbori, foarte reprezentative în mulțimi în care elementele lor pot fi clasificate în ierarhii și în calcule de numărare și probabilitate_[9], digrafe, grafice hamiltoniene _[10], etc.

Imagine de modele grafice și rețele în psiho., de Ruiz, Ana María.

Aceste enigme, dacă vrem să le numim așa, au o aplicabilitate enormă în lumea de azi, în situații atât de diverse precum: biologie molecular _[11], tehnica de calcul_[12], telecomunicatii _[13] și analiza rețelei _[14]. Merită să întrebați atunci: nu este cel puțin curios că o problemă de aproape banal va ajunge să fie unul dintre cele mai interesante și mai vizibile rezultate ale matematicii? Poate că, pentru aceasta, a fost necesară contribuția uneia dintre cele mai illustre minți ale umanității.