Grafic

Grafic neorientat cu șase noduri și cinci arce

Graficele sunt structuri matematice discrete care prezintă interes atât pentru matematică, cât și pentru o gamă largă de domenii de aplicare. În studiul lor matematic, teoria graficelor , o parte importantă a combinatoricii ; graficele sunt folosite și în domenii precum topologia , teoria automatelor , funcțiile speciale , geometria poliedrelor , algebrele Lie . Graficele se întâlnesc în multe dintre capitolele computerului (de exemplu, pentru a contura programe, circuite, rețele de calculatoare, hărți ale site-ului). Ele sunt, de asemenea, baza sistemelor și modelelor de procese studiate în inginerie , chimie , biologie moleculară , cercetare operațională , organizare a afacerilor , geografie (sisteme fluviale, rețele rutiere, transporturi), lingvistică structurală, istorie (arbori genealogici, filologia textelor).

Definiții fundamentale

Un grafic

Un grafic este un set de elemente numite noduri sau vârfuri care pot fi conectate între ele prin linii sau arcuri care apelează laturi sau margini. Mai formal, o pereche ordonată se numește grafic $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ de seturi cu $V.$ ${\ displaystyle V}$ $V.$ set de noduri ed $ȘI$ ${\ displaystyle E}$ $ȘI$ set de arce, astfel încât elementele de $ȘI$ ${\ displaystyle E}$ $ȘI$ sunt perechi de elemente ale $V.$ ${\ displaystyle V}$ $V.$ (din $E\subseteq V\times V$ ${\ displaystyle E \ subseteq V \ times V}$ ${\ displaystyle E \ subseteq V \ times V}$ rezultă în special că $|E|\leq |V|^{2}$ ${\ displaystyle | E | \ leq | V | ^ {2}}$ ${\ displaystyle | E | \ leq | V | ^ {2}}$ ). Chiar mai formal, un grafic este un triplu $(V,E,f)$ ${\ displaystyle (V, E, f)}$ ${\ displaystyle (V, E, f)}$ , unde este $V.$ ${\ displaystyle V}$ $V.$ se numește un set de noduri, $ȘI$ ${\ displaystyle E}$ $ȘI$ se numește ansamblul arcurilor și $f$ ${\ displaystyle f}$ $f$ este o funcție care se asociază fiecărui arc $Și$ ${\ displaystyle e}$ $Și$ în $ȘI$ ${\ displaystyle E}$ $ȘI$ două vârfuri $tu, v$ ${\ displaystyle u, v}$ ${\ displaystyle u, v}$ în $V.$ ${\ displaystyle V}$ $V.$ (în acest caz graficul se va spune bine specificat). Dacă în schimb $ȘI$ ${\ displaystyle E}$ $ȘI$ este un multiset , acesta se numește multigraf .

Două vârfuri $tu, v$ ${\ displaystyle u, v}$ ${\ displaystyle u, v}$ conectate printr-un arc $Și$ ${\ displaystyle e}$ $Și$ se numesc capetele arcului; arcul $Și$ ${\ displaystyle e}$ $Și$ se identifică și cu perechea formată de extremele sale $(u,v)$ ${\ displaystyle (u, v)}$ $(u, v)$ . De sine $ȘI$ ${\ displaystyle E}$ $ȘI$ este o relație simetrică, atunci se spune că graficul este nedirectat (sau indirect), altfel se spune că este orientat (sau direct).

Un arc care are două extreme coincidente spune laț . Un grafic nedirectat, lipsit de bucle, se spune grafic simplu .

scheletul $\mathrm {sk} (G)$ ${\ displaystyle \ mathrm {sk} (G)}$ ${\ displaystyle \ mathrm {sk} (G)}$ din $G.$ ${\ displaystyle G}$ $G.$ este graficul obținut din $G.$ ${\ displaystyle G}$ $G.$ eliminând toate buclele și înlocuind fiecare arc multiplu cu un arc unic având aceleași capete.

Vârfurile aparținând unui arc sau margine se numesc extreme, puncte extreme sau vârfuri extreme ale arcului. Un vârf poate exista într-un grafic și nu aparține unui arc.

Codul sursă al paginii principale Wikipedia , afișat ca un copac , un caz special de grafic

Seturile $V.$ ${\ displaystyle V}$ $V.$ și $ȘI$ ${\ displaystyle E}$ $ȘI$ De obicei, se presupune că sunt terminate și multe dintre cele mai cunoscute rezultate nu sunt adevărate (sau sunt mai degrabă diferite) pentru grafice infinite, deoarece multe dintre argumente nu sunt în cazul infinit . Ordinea unui grafic este $|V|$ ${\ displaystyle | V |}$ ${\ displaystyle | V |}$ (numărul de vârfuri). Dimensiunea unui grafic este $|E|$ ${\ displaystyle | E |}$ ${\ displaystyle | E |}$ . Numărul de muchii incidente într-un vârf $v\in V$ ${\ displaystyle v \ in V}$ $v \ în V$ (adică numărul de arce care se conectează la acesta) se numește gradul vârfului $v$ ${\ displaystyle v}$ $v$ , unde un arc care leagă vârful la ambele capete (o buclă) este numărat de două ori.

"Gradul maxim" și "Gradul minim" al $G.$ ${\ displaystyle G}$ $G.$ ca, respectiv, gradul de vârf al $G.$ ${\ displaystyle G}$ $G.$ cu cel mai mare număr de margini incidente și gradul de vârf de $G.$ ${\ displaystyle G}$ $G.$ care are mai puține arcade incidente. Când gradul maxim și gradul minim coincid cu un număr $k$ ${\ displaystyle k}$ $k$ , suntem în prezența unui grafic $k$ ${\ displaystyle k}$ $k$ -regular (sau mai simplu grafic regulat).

Pentru un arc $\{u,v\}$ ${\ displaystyle \ {u, v \}}$ ${\ displaystyle \ {u, v \}}$ , teoreticienii graficului folosesc de obicei cea mai sintetică notație $tu v$ ${\ displaystyle uv}$ $uv$ .

Un grafic $G=(V,\emptyset )$ ${\ displaystyle G = (V, \ emptyset)}$ ${\ displaystyle G = (V, \ emptyset)}$ lipsit de arcurile menționate este un grafic nul . Un caz extrem al unui grafic nul este cel al graficului $G=(\varnothing ,\varnothing )$ ${\ displaystyle G = (\ varnothing, \ varnothing)}$ ${\ displaystyle G = (\ varnothing, \ varnothing)}$ , pentru care setul de noduri este de asemenea gol. ^[1]

Grafic complet, densitatea unui grafic

Un grafic este definit complet dacă oricare dintre vârfurile sale sunt adiacente (există un arc care le conectează). Cardinalitatea maximă a unui subgraf complet al graficului se numește densitatea graficului .

Trasee, trasee, circuite și cicluri

O „cale” de lungime n în G este dată de o succesiune de vârfuri v _0, v _1, ..., v _n (nu neapărat toate distincte) și o secvență de arce care le conectează (v _0, v ₁₎ , (v _1, v _2), ..., (v _n-1, v _n). Vârfurile v ₀ și v _n sunt numite extreme ale căii .

O cale cu laturile două câte două distincte una de alta își ia numele de mers.

O cale închisă (v ₀ = v _n) fără arcuri repetate este circuitul menționat .

O cale închisă (v ₀ = v _n) fără arcuri sau noduri repetate este numită ciclul.

Calea de urmat pentru a trimite pachete de la un nod la altul este o cale minimă.

Conectivitate

Exemple de grafice conectate (stânga) și neconectate (dreapta).

Dat fiind un grafic G = (V, E) , se spune că două vârfuri v, u ∈ V sunt „conectate” dacă există o cale cu extremele v și u. Dacă o astfel de cale nu există, v și u sunt numite „inegale”. Relația de legătură dintre vârfuri este o relație de echivalență .

Pentru i = 1, ..., k (k clase de echivalență ) sunt definite subgrafele G _i = (V _i, E _i) ca plafoanele subgrafelor care conțin toate elementele conectate între ele, care iau numele componentelor conectate G, a cărui cardinalitate este adesea notată cu γ (G).

Dacă γ (G) = 1, G se spune că este „ conectat ”.

Un „nod izolat” este un vârf care nu este conectat la niciun alt vârf. Un nod izolat are gradul 0.

Un „pod” și o „joncțiune” sunt, respectiv, un arc și un vârf care, dacă sunt suprimate, deconectează graficul.

„Conectivitatea” unui grafic G = (V, E) este definită ca cardinalitatea setului ne-gol S ⊂ V astfel încât G \ S ( G din care au fost eliminați toate nodurile lui S ) este deconectat sau este un nod izolat.

În mod similar, „arcoconectivitatea” este definită ca cardinalitatea A ⊂ E ne-gol, astfel încât G \ A (G din care au fost eliminați toate arcele lui A) este deconectat. Buclele sunt irelevante în calculul conectivității arcului, în timp ce arcurile multiple sunt numărate de numărul de arcuri pe care le includ.

Dacă conectivitatea G indicată de κ (G), arcoconnettività G indicată de κ '(G) și gradul minim de G indicat de δ _min (G).

„Teorema lui Whitney” afirmă că pentru fiecare grafic G, relația κ (G) ≤ κ '(G) ≤ δ _min (G).

Cuplaj și acoperiri

Având în vedere un grafic G = simplu (V, E), un set M = (S, A) format din perechi de vârfuri luate câte doi și de arcurile care leagă aceste vârfuri este o pereche (sau legare sau potrivire) dacă fiecare vârf de S are gradul 0 sau 1.

În particular, fiecare nod cu grad 1 se spune „m -saturato“ și fiecare nod cu un grad 0 este numit „m -esposto“.

Având o potrivire M = (S, A) a lui G = (V, E), o cale P ⊆ E este „alternantă m” dacă P conține alternativ arce de E și arcuri de A.

O cale alternativă-m „crește-m” dacă primul și ultimul vârf al acestei căi sunt -esposti m.

Conform „teoremei Berge”, o combinație de M G este maximă dacă și numai dacă G nu conține căi m -aumentanti.

O acoperire a unui grafic G = (V, E) este un set S ⊆ V ne-gol astfel încât fiecare arc din E este incident pe cel puțin un vârf al lui S. Pentru fiecare grafic, cardinalitatea maximă a unei suprapuneri este mai mare sau egală cu cardinalitatea potrivirii maxime.

Dacă ν (G) cardinalitatea potrivirii maxime a lui G și τ (G) cardinalitatea maximă a acoperirilor lui G.

König a demonstrat că, dacă G este un grafic bipartit, atunci ν (G) = τ (G).

Dar mai general, pentru orice grafic care este ν (G) ≥ τ (G).

Tipuri de grafice

Realizarea graficelor

Există două moduri generale de a reprezenta un grafic cu o structură de date utilizată de un program : lista adiacențelor și matricea adiacenței . Într-o listă de adiacență, o listă conține o listă de noduri și fiecare nod este legat de o listă de indicatori către noduri conectate printr-un arc. Într-o matrice de adiacență, o matrice $N\times N$ ${\ displaystyle N \ times N}$ $N \ ori N$ , unde este $Nu.$ ${\ displaystyle N}$ $Nu.$ Este numărul de noduri care menține o valoare adevărată într-o celulă $(a,b)$ ${\ displaystyle (a, b)}$ $(a, b)$ dacă nodul $la$ ${\ displaystyle a}$ $la$ este conectat la nod $b$ ${\ displaystyle b}$ $b$ . Matricea este simetrică numai dacă graficul nu este orientat.

Indicate cu V cardinalitatea vârfurilor grafului și E cu cardinalitatea setului de arce ale graficului, cele două reprezentări, care prin liste și care prin intermediul matricei de adiacență , necesită Θ (V + E) și Θ (V ²⁾ de spațiu de memorie.

Fiecare dintre cele două reprezentări are unele avantaje: o listă de adiacență este mai potrivită pentru reprezentarea graficelor rare sau a graficelor cu câteva arce, prin urmare este ușor să găsiți toate nodurile adiacente unui nod dat și să verificați existența conexiunilor între noduri; o matrice de adiacență, pe de altă parte, este mai potrivită pentru descrierea graficelor dense cu multe arce și, de asemenea, face mai ușoară inversarea graficelor și identificarea subgrafelor acestora.

Sintaxa pentru reprezentarea graficului

Există multe sintaxi diferite pentru reprezentarea graficelor, unele XML bazate pe limbaj ca DGML , DotML , GEXF , graphml , GXL și XGMML și alte texte, precum DOT , Graph Modeling Language (GML), LCF și Trivial Graph Format .

Aplicații

Teoria graficelor are multe aplicații pentru modelarea rețelelor de telecomunicații , a rețelelor neuronale , în biologie, în științele economice și sociale.

Din științele economice și sociale din anii 1980, adoptarea unui anumit tip de rețea ( rețea nucleu-periferie ) a început să se răspândească printre cercetători și cadre universitare, formată dintr-un bloc central, mai „dens” de conexiuni între noduri și de o set de blocuri periferice de noduri cu legături împrăștiate. În același timp, au propus partiția diferitelor metode (și constrângerile conexiunilor) și măsurile de centralitate a nodului pentru a testa aplicabilitatea modelului la rețelele individuale ^[2] .

Acest tip de rețea se naște pentru a modela și explica creșterea economică diferită între țări, tendința de concentrare a bogăției economice și a sistemelor financiare detectate în țară de la al doilea război mondial. Modelul a fost apoi extins la alte domenii de cercetare.

Există o variantă „cu trei blocuri” a rețelei „centru-periferie”: centru-semi-hiperferie-periferie.

Notă

^ Unii definesc golul graficului G = (V, ∅), cu V ≠ ∅, și nul graficul G = (∅, ∅).
^ (EN) Fabio Della Rossa, Fabio Dercole și Carlo Piccardi, Profilarea rețelelor de structură nucleu-periferie de către walkers aleatori pe nature.com, 19 martie 2013. Accesat la 4 aprilie 2018.

Elemente conexe

Alte proiecte

Wikționarul conține intrarea în dicționar „ grafic ”
Wikimedia Commons conține imagini sau alte fișiere grafice

linkuri externe

(EN) Grafic . VP Kozyrev (inițiator), Enciclopedia Matematicii .
(EN) grafic , în PlanetMath .
( EN ) Eric W. Weisstein, Grafo , în MathWorld , Wolfram Research.
Definiții pe grafice (PDF) pe wpage.unina.it.
Software educațional open source GraphsJ în Java, cu o interfață grafică intuitivă, care permite rezolvarea mai multor probleme pe grafic. Extensibil datorită SDK-ului său scris în Java.
GraphNview: software open source pentru a crea, vizualiza și anima graficele pe bioemulation.altervista.org.
Un grafic folosit pentru a calcula toate modelele posibile ale ecranului de blocare Android , pe science4fun.org.
Tutorial video: cum să creați un grafic cu PostGIS și QGis

Controlul autorității	Tezaur BNCF 6138

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Unii definesc golul graficului G = (V, ∅), cu V ≠ ∅, și nul graficul G = (∅, ∅).

[2] (EN) Fabio Della Rossa, Fabio Dercole și Carlo Piccardi, Profilarea rețelelor de structură nucleu-periferie de către walkers aleatori pe nature.com, 19 martie 2013. Accesat la 4 aprilie 2018.

[1]

[2]