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 domeniul matematicii studiul lor, teoria graficelor , constituie 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 diferite capitole ale informaticii (de exemplu pentru a schematiza programe, circuite, rețele de calculatoare, hărți ale site-urilor). Ele sunt, de asemenea, baza sistemelor și modelelor de procese studiate în inginerie , chimie , biologie moleculară , cercetare operațională , organizarea 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 numite arce sau 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 se va spune că graficul este bine specificat ). Dacă în schimb $ȘI$ ${\ displaystyle E}$ $ȘI$ este un set multiplu , apoi vorbim despre un 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ă capete coincidente se numește buclă . Un grafic fără direcții fără bucle se numește 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 sub forma unui copac , un caz special al unui grafic

Seturile $V.$ ${\ displaystyle V}$ $V.$ și $ȘI$ ${\ displaystyle E}$ $ȘI$ de obicei se presupune că sunt finite și multe dintre cele mai cunoscute rezultate nu sunt adevărate (sau sunt destul de diferite) pentru grafice infinite, deoarece multe dintre argumente eșuează î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)}$ fără margini se numește 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 ₀ , v ₁ , ..., v _n (nu neapărat toate distincte) și de o succesiune de margini care le leagă (v ₀ , v ₁ ) , (v ₁ , v ₂ ), ..., (v _n-1 , v _n ) . Vârfurile v ₀ și v _n se numesc extreme ale căii.

O cale cu două laturi distincte una de alta se numește cale .

O cale închisă ( v ₀ = v _n ) fără arcuri repetate se numește circuit .

O cale închisă ( v ₀ = v _n ) fără margini sau noduri repetate se numește ciclu .

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 puncte finale v și u . Dacă o astfel de cale nu există, se spune că v și u sunt „deconectate”. Relația de legătură dintre vârfuri este o relație de echivalență .

Pentru i = 1, ..., k ( k clase de echivalență ), subgrafele G _i = (V _i , E _i ) pot fi definite ca subgrafele maxime care conțin toate elementele conectate între ele, care iau numele de conectat componente ale lui G , a căror 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, "conectivitatea arcului" este definită ca cardinalitatea setului ne-gol A ⊂ E astfel încât G \ A ( G din care au fost eliminate toate marginile 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.

Fie conectivitatea lui G indicată de κ ( G ), conectivitatea arcului lui G indicată de κ '( G ) și gradul minim de G indicat de δ _min ( G ).

„Teorema Whiteny” afirmă că pentru orice grafic G se menține relația κ ( G ) ≤ κ '( G ) ≤ δ _min ( G ).

Cuplaj și acoperiri

Având în vedere un grafic simplu G = (V, E) , o mulțime M = (S, A) compusă din perechi de vârfuri luate două câte două și ale marginilor care leagă aceste vârfuri este o cuplare (sau potrivire sau potrivire) dacă fiecare vârf al S are gradul 0 sau 1.

În special, fiecare nod cu gradul 1 este numit „ m- saturat” și fiecare nod cu gradul 0 este numit „ m- expus”.

Având în vedere o potrivire M = (S, A) pe G = (V, E) , o cale P ⊆ E este "alternantă m" dacă P conține alternativ marginile lui E și marginile lui A.

O cale alternativă de m „mărește” dacă primul și ultimul vârf al acelei căi sunt expuse la m .

Potrivit „teoremei lui Berge”, o potrivire a M a lui G este maximă dacă și numai dacă G nu conține căi de mărire a m .

O suprapunere a unui grafic G = (V, E) este un set S- V ne-gol astfel încât fiecare arc din E este incident în 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.

Fie ν ( G ) cardinalitatea potrivirii maxime a lui G și τ ( G ) cardinalitatea maximă a coperților lui G.

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

Pe de altă parte, mai general, pentru orice grafic se menține ν ( G ) ≥ τ ( G ).

Tipuri de grafice

Realizarea graficelor

Există două moduri generale de a reprezenta un grafic cu o structură de date utilizabilă de un program : lista de adiacență și matricea de adiacență . Î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, păstrează 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.

Indicat cu V cardinalitatea setului de vârfuri ale graficului și cu E cardinalitatea setului de arce ale graficului, cele două reprezentări, cea prin liste și cea prin matricea de adiacență , necesită respectiv Θ (V + E ) și spațiul de memorie Θ (V ² ) .

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ă mai multe sintaxe pentru reprezentarea graficului, unele bazate pe limbaj XML , cum ar fi DGML , DotML , GEXF , GraphML , GXL și XGMML , și altele textuale, cum ar fi DOT , Graph Modeling Language (GML), LCF și Trivial Graph Format .

Aplicații

Teoria graficelor are numeroase 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 fost propuse diferite metode de partiționare (și constrângeri de conexiune), precum și măsuri ale centralității nodurilor pentru a testa aplicabilitatea modelului la rețelele individuale ^[2] .

Acest tip de rețea a fost creat pentru a modela și explica diferitele creșteri economice dintre țări, adică tendința spre concentrarea bogăției economice și financiare constatate în sistemele de țări începând cu cel de-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 graficul G = (V, ∅) gol , cu V ≠ ∅, iar graficul G = (∅, ∅) nul .
^ (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 dicționarul lema « 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 .
GraphsJ Software educațional open source în Java, cu interfață grafică intuitivă, care vă permite să rezolvați pas cu pas multe probleme legate de grafic. Extensibil datorită SDK-ului său scris în Java.
GraphNview: software open source pentru crearea, vizualizarea și animarea graficelor orientate , pe bioemulation.altervista.org .
Un grafic folosit pentru a calcula toate modelele posibile de ecran de blocare Android , la 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 graficul G = (V, ∅) gol , cu V ≠ ∅, iar graficul G = (∅, ∅) nul .

[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]