Grafic (matematică)

Un grafic este o abstractizare matematică a unui sistem real de orice natură, ale cărui obiecte au conexiuni pe perechi. Un graf ca obiect matematic este o colecție de două mulțimi - mulțimea de obiecte în sine, numită mulțimea de vârfuri , și mulțimea conexiunilor lor pe perechi, numită mulțime de muchii. Un element al unui set de muchii este o pereche de elemente ale unui set de vârfuri.

Graficele sunt utilizate pe scară largă în știința și tehnologia modernă. Ele sunt utilizate atât în științele naturii (fizică și chimie), cât și în științele sociale (de exemplu, sociologie), dar utilizarea graficelor a primit cea mai mare scară în informatică și tehnologii de rețea.

Ca cel mai simplu exemplu din viață, putem da o diagramă de zbor a unei anumite companii aeriene, care este modelată printr-un grafic, unde vârfurile graficului sunt orașe, iar marginile sunt zboruri care leagă perechi de orașe. Un arbore de directoare într-un computer este, de asemenea, un grafic: unitățile, folderele și fișierele sunt vârfuri, iar marginile arată imbricarea fișierelor și folderelor în foldere și unități [1] . Structura Wikipedia este modelată de un grafic direcționat , în care articolele sunt vârfurile graficului, iar hyperlinkurile sunt arce ( hartă tematică ).

Graficele sunt principalul obiect de studiu în teoria grafurilor .

Definiții

Sistemele de natură reală modelate prin grafice sunt foarte diverse, deci există diferite tipuri de grafice. Cea mai simplă abstractizare a sistemelor cu elemente care au conexiuni pe perechi este un grafic simplu .

Grafic simplu

Definiție. Un grafic simplu este o colecție de două mulțimi - o mulțime nevidă și un set de perechi neordonate de elemente diferite ale mulțimii . O mulțime se numește un set de vârfuri , o mulțime se numește un set de muchii $G(V,E)$ $V$ $E$ $V$ $V$ $E$

G(V,E)=\left\langle V,E\right\rangle,\quad V\neq \varnothing,\quad E\subseteq V\time V,\quad \left\{v,v\ dreapta\}\notă E,\quad v\în V

adică mulţimea este formată din submulţimi de 2 elemente ale mulţimii . $E$ $V$

Termeni înrudiți

Teoria grafurilor nu are o terminologie bine stabilită. Prin urmare, unele publicații pot folosi alți termeni decât cei enumerați mai jos.

Un vârf (nod, punct) ( eng. nod, nod, punct ) al unui graf este un element al unui set de vârfuri ; $G$ $v\in V(G)$

O muchie (linie) ( în engleză margine, linie ) a unui grafic este un element al setului de muchii , sau , unde ; $G$ $e\in E(G)$ $e=\stanga\{v_{1},v_{2}\dreapta\}$ $v_{1}\in V(G),\quad v_{2}\in V(G)$

Elementele unui graf sunt vârfurile și muchiile acestuia ale grafului; $G$ $v\in V(G)$ $e\in E(G)$

Ordinea ( ordinea engleză ) a unui grafic este numărul cardinal al mulțimii de vârfuri , sau, cu alte cuvinte, numărul de vârfuri; $G$ $n=|V(G)|$

Dimensiunea ( English size ) a graficului este numărul cardinal al setului de muchii sau, cu alte cuvinte, numărul de muchii; $G$ $m=|E(G)|$

Un vârf este incident cu o muchie dacă ; apoi mai spun că există o margine la ; $v$ $e$ $v\in e$ $e$ $v$

Nodurile de sfârșit (capete) ( eng. vârfuri, capete ) sunt două vârfuri incidente la o muchie. Muchia leagă ( English joins ) vârfurile sale de capăt;

Nodurile învecinate (adiacente) ( vecini englezi , adiacent ) sunt astfel de vârfuri și care sau, cu alte cuvinte, ambele vârfuri sunt terminale pentru o muchie; $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Muchiile adiacente ( în engleză muchiile adiacente ) sunt muchii incidente la un vârf sau și - adiacente; $e_{1}=\stanga\{v,v_{1}\dreapta\}$ $e_{2}=\stanga\{v,v_{2}\dreapta\}$

Gradul (valența) unui vârf ( ing. grad, valență ) este numărul de muchii incidente cu acesta. Gradul unui vârf este notat ca ; $d(v)$

Un vârf izolat ( ing. izolat ) este un vârf cu un grad , adică nu este capătul vreunei muchii; $d(v)=0$

Un vârf suspendat (frunză) ( ing. frunză ) este un vârf cu un grad , adică, care este capătul exact al unei muchii. $d(v)=1$

De obicei, un grafic este reprezentat ca o diagramă : vârfuri - puncte, margini - linii.

Pseudograf

Un pseudograf este o colecție de două seturi - un set nevid și un set de perechi neordonate de elemente ale mulțimii . $G(V,E)$ $V$ $E$ $V$

G(V,E)=\left\langle V,E\right\rangle,\quad V\neq \varnothing,\quad E\subseteq V\times V

Elementul este permis în setul de muchii ale pseudografului . $\stânga\{v,v\dreapta\}\în E(G)$

O buclă este un element care este o muchie ale cărei vârfuri de capăt coincid. $e=\stanga\{v,v\dreapta\}$

Cu alte cuvinte, dacă elementele mulțimii E pot fi bucle, atunci graficul se numește pseudograf [2] .

Multigraf

Un multigraf este o colecție de două seturi - un set nevid și un multiset de perechi neordonate de elemente diferite ale mulțimii . $G(V,\mathbf {E} )$ $V$ $\mathbf {E}$ $V$

G(V,\mathbf {E} )=\left\langle V,\mathbf {E} \right\rangle,\quad V\neq \varnothing,\quad \mathbf {E} \subseteq V\times V\quad \left\{v,v\right\}\notin \mathbf {E} ,\quad v\in V

Muchiile multiple sunt elemente identice ale multisetului , adică muchiile ale căror vârfuri de capăt coincid. $\left\{e,e,\dots, e\right\}\in \mathbf {E}$

Cu alte cuvinte, dacă nu o mulțime, ci o familie, adică dacă conține aceleași elemente, atunci astfel de elemente se numesc muchii multiple, iar graficul se numește multigraf [2] . $E$ $\mathbf {E}$

Pseudomultigraf

Un pseudomultigraf este o colecție de două seturi - o mulțime nevidă și un multiset de perechi neordonate de elemente ale mulțimii . $G(V,\mathbf {E} )$ $V$ $\mathbf {E}$ $V$

G(V,\mathbf {E} )=\left\langle V,\mathbf {E} \right\rangle,\quad V\neq \varnothing,\quad \mathbf {E} \subseteq V\times V

Cu alte cuvinte, dacă o familie care conține aceleași elemente (mai multe muchii) și poate conține bucle, atunci graficul se numește pseudo-multigraf [2] . $\mathbf {E}$ $\mathbf {E}$

Graficul direcționat

Graficul direcționat (digraf) ( eng. graficul direcționat sau dirgaph ) este un set de două seturi - o mulțime nevide și un set de arce sau perechi ordonate de diferite elemente ale mulțimii $G(V,E)$ $V$ $E$ $V$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing,\quad \left\langle \left\{v_{1}, v_{2}\ dreapta\},\prec \right\rangle \în E,\quad v\in V

împreună cu două display-uri

init:E\rightarrow V,\quad ter:E\rightarrow V

unde maparea atribuie fiecărui arc vârful său inițial (începutul arcului) , iar maparea atribuie fiecărui arc vârful său final (sfârșitul arcului) . Se spune că arcul duce de la la $init:E\rightarrow V$ $init(e)$ $ter:E\rightarrow V$ $ter(e)$ $e$ $init(e)$ $ter(e)$

Grafic mixt

Un grafic mixt este o colecție de trei mulțimi - un set nevid de vârfuri și un set de arce sau perechi ordonate de diferite elemente ale mulțimii și un set de muchii de perechi neordonate de diferite elemente ale mulțimii $G(V,E,U)$ $V$ $E$ $V$ $U$ $V$

G(V,E,U)=\left\langle V,E,U\right\rangle ,\quad V\neq \varnothing,\quad \left\langle \left\{v_{1},v_ {2}\right\},\prec \right\rangle \în E,\quad \left\{v_{3},v_{4}\right\}\în U,\quad v\in V

împreună cu două display-uri

init:E\rightarrow V,\quad ter:E\rightarrow V

Graficele direcționate și nedirecționate sunt cazuri speciale de grafice mixte.

Grafice izomorfe

Un graf se numește izomorf la un graf dacă există o bijecție de la mulțimea de vârfuri a graficului la mulțimea de vârfuri a graficului , care are următoarea proprietate: dacă graficul are o muchie de la vârf la vârf , atunci graficul trebuie să aibă o muchie de la vârf la vârf și invers - dacă graficul are o muchie de la vârf la vârf , atunci graficul trebuie să aibă o muchie de la vârf la vârf . În cazul unui graf direcționat , această bijecție trebuie să păstreze și orientarea muchiei. În cazul unui grafic ponderat, bijecția trebuie să păstreze și greutatea muchiei. $G$ $H$ $f$ $G$ $H$ $G$ $A$ $B$ $H$ $fa)$ $f(B)$ $H$ $A$ $B$ $G$ $f^{-1}(A)$ $f^{-1}(B)$

Alte definiții înrudite

O rută într-un grafic este o succesiune finită de vârfuri în care fiecare vârf (cu excepția ultimului) este conectat la următorul vârf din succesiune printr-o muchie. Un lanț este un traseu fără margini repetate. O cale simplă este o cale fără vârfuri repetate (ceea ce înseamnă că nu există muchii care se repetă într-o cale simplă).

O rută orientată (sau cale ) într-un digraf este o secvență finită de vârfuri și arce în care fiecare element este incident cu precedentul și următorul.

Un ciclu este un lanț în care primul și ultimul vârf coincid. În acest caz , lungimea traseului (sau ciclului) este numărul muchiilor sale constitutive . Rețineți că dacă vârfurile și sunt capetele unei muchii, atunci, conform acestei definiții, secvența este un ciclu. Pentru a evita astfel de cazuri „degenerate”, sunt introduse următoarele noțiuni. $u$ $v$ $(u,v,u)$

O cale (sau ciclu) se numește simplă dacă marginile din ea nu se repetă; elementar dacă este simplu și vârfurile din el nu se repetă (cu excepția inițialei și finalei în cazul unui ciclu).

Cele mai simple proprietăți ale căilor și ciclurilor:

fiecare cale care leagă două vârfuri conține o cale elementară care leagă aceleași două vârfuri;
fiecare cale neelementară simplă conține un ciclu elementar ;
fiecare ciclu simplu care trece printr-un vârf (sau muchie) conține un (sub-)ciclu elementar care trece prin același vârf (sau muchie);
o buclă este un ciclu elementar.

O relație binară pe mulțimea de vârfuri a unui graf, dată ca „există o cale de la la ”, este o relație de echivalență și, prin urmare, împărțiește această mulțime în clase de echivalență, numite componente conexe ale grafului. Dacă un grafic are exact o componentă conectată, atunci graficul este conectat. Pe componenta conectată, putem introduce conceptul de distanță dintre vârfuri ca lungime minimă a unei căi care leagă aceste vârfuri. $u$ $v$

Orice subgraf conex maxim al unui grafic se numește componentă conexă (sau pur și simplu componentă) a graficului . Cuvântul „maxim” înseamnă maxim în ceea ce privește includerea, adică nu este conținut într-un subgraf conectat cu un număr mare de elemente. $G$ $G$

O muchie dintr-un grafic se numește punte dacă îndepărtarea ei crește numărul de componente.

Caracteristici suplimentare ale graficelor

Graficul se numește:

conectat dacă pentru orice vârfuri,există o cale de lala. $u$ $v$ $u$ $v$
puternic conectat sau conectat direcțional dacă este orientat și există o cale orientată de la orice vârf la oricare altul.
un arbore dacă este conectat și nu conține cicluri non-triviale.
completă dacă oricare dintre cele două vârfuri ale sale (diferite, dacă buclele nu sunt permise) sunt conectate printr-o muchie.
bipartit dacă vârfurile sale pot fi împărțite în două submulțimi care nu se intersecteazășiastfel încât orice muchie conectează un vârf de lacu un vârf de la. $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$
k-parțial dacă vârfurile sale pot fi împărțite în submulțimi care nu se intersectează , , …, astfel încât să nu existe muchii care să conecteze vârfurile aceleiași submulțimi. $k$ $V_{1}$ $V_{2}$ $V_{k}$
bipartit complet , dacă fiecare vârf al unei submulțimi este conectat printr-o muchie la fiecare vârf al altei submulțimi.
planar , dacă graficul poate fi reprezentat printr-o diagramă pe un plan fără muchii încrucișate.
ponderat dacă fiecărei muchii a graficului i se atribuie un anumit număr, numit greutatea muchiei.
cordal dacă graficul nu conține cicluri induse cu lungime mai mare de trei.

Se mai intampla:

Generalizarea conceptului de graf

Un grafic simplu este un complex simplial unidimensional .

Mai abstract, un grafic poate fi definit ca un triplu , unde și sunt unele mulțimi ( de vârfuri și , respectiv, muchii ), și este o funcție de incidență (sau incidentor ) care atribuie fiecărei muchii (ordonate sau neordonate) o pereche de vârfuri și de la ( capetele sale ). Cazurile particulare ale acestui concept sunt: $(V,E,\varphi )$ $V$ $E$ $\varphi$ $e\în E$ $u$ $v$ $V$

Grafice Euler - un grafic în care există o cale Euler ciclică ( ciclul Euler );

Modalități de reprezentare a unui grafic în informatică

Matricea adiacentei

Un tabel în care atât coloanele, cât și rândurile corespund vârfurilor graficului. În fiecare celulă a acestei matrice, este scris un număr care determină prezența unei conexiuni de la rândul de sus la coloana de sus (sau invers).

Acesta este cel mai convenabil mod de a reprezenta grafice dense.

Dezavantajul îl reprezintă cerințele de memorie, care sunt direct proporționale cu pătratul numărului de vârfuri.

Matrice bidimensională;
Matrice cu goluri;
Setare implicită (folosind o funcție).

Matricea de incidență

Un tabel în care rândurile corespund vârfurilor graficului, iar coloanele corespund legăturilor (marginelor) graficului. Într-o celulă matriceală la intersecția unui rând cu o coloană , se scrie următoarele: $i$ $j$

unu în cazul în care conexiunea „pleacă” de sus ,

j

i

-1, dacă conexiunea „intră” în vârf, 0 în toate celelalte cazuri (adică dacă conexiunea este o buclă sau conexiunea nu este incidentă la vârf)

Această metodă este destul de încăpătoare (dimensiunea este proporțională cu ) pentru stocare, așa că este folosită foarte rar, în cazuri speciale (de exemplu, pentru a găsi rapid cicluri într-un grafic). $|V||E|$

Lista adiacentei

O listă în care fiecare vârf al graficului corespunde unui șir care stochează o listă de vârfuri adiacente. O astfel de structură de date nu este un tabel în sensul obișnuit, ci este o „listă de liste”.

Dimensiunea memoriei: . $O(|V|+|E|)$

Acesta este cel mai convenabil mod de a reprezenta grafice rare, precum și atunci când implementați algoritmi de parcurgere a graficului de bază în lățime sau adâncime, unde trebuie să obțineți rapid „vecinii” vârfului vizualizat în prezent.

Lista marginilor

O listă în care fiecare margine a graficului corespunde unui șir care stochează două vârfuri incidente marginii.

Dimensiunea memoriei: . $O(|E|)$

Acesta este cel mai compact mod de a reprezenta grafice, așa că este adesea folosit pentru stocare externă sau schimb de date.

Limbaje de descriere și programe grafice

Limbi de descriere

Pentru a descrie grafice care sunt potrivite pentru prelucrarea automată și în același timp convenabile pentru percepția umană, sunt utilizate mai multe limbaje standardizate, inclusiv:

PUNCT
GraphML
Format grafic trivial
GML
GXL
XGMML
DGML

Construire programe

Au fost dezvoltate o serie de programe comerciale pentru construirea de grafice, de exemplu, construirea de grafice stă la baza pachetelor software de aplicație ILOG (din 2009 deținute de IBM Corporation ), printre alte programe - GoView, Lassalle AddFlow, LEDA (există o ediție gratuită). ).

Există, de asemenea, un program gratuit de graficare igraph și o bibliotecă gratuită numită Boost .

Programe de vizualizare

Următoarele instrumente software sunt utilizate pentru a vizualiza grafice :

Graphviz ( Eclipse Public License )
LION Graph Visualizer.
Analizorul grafic este un program în limba rusă cu o interfață de utilizator simplă ( GNU LGPL ; numai Windows).
Gephi este un cadru grafic pentru reprezentarea și studierea graficelor ( GNU GPL , CDDL ).
Biblioteca GraphX este o bibliotecă .NET gratuită pentru calcularea și desenarea graficelor, folosind WPF 4.0 .
Biblioteca MSAGL este o bibliotecă gratuită pentru .NET [3] .

Vezi și

Note

↑ Burkatovskaya, 2014 , p. 3.
↑ 1 2 3 Burkatovskaya, 2014 , p. 6.
↑ Microsoft Automatic Graph Layout - Microsoft Research . research.microsoft.com. Consultat la 15 noiembrie 2015. Arhivat din original la 14 mai 2012. (nedefinit)

Literatură

Burkatovskaya Yu. B. Teoria graficelor. - Tomsk: Editura Universității Politehnice din Tomsk, 2014. - T. 1. - 200 p.
Distel R. Teoria grafurilor. - Novosibirsk: Editura Institutului de Matematică. S. L. Sobolev SO RAN, 2002. - 336 p. - ISBN 5-86134-101-X.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Prelegeri despre teoria grafurilor. M.: Nauka, 1990. 384 p. (Ed. 2, rev. M.: URSS, 2009. 392 p.)
Kasyanov V.N., Evstigneev V.A. Grafice în programare: procesare, vizualizare și aplicare. - Sankt Petersburg. : BHV-Petersburg, 2003. - S. 1104. - ISBN 5-94157-184-4 .
Kirsanov M.N. Grafice în arțar. — M. : Fizmatlit, 2007. — 168 p. - ISBN 978-5-9221-0745-7 .
Kormen T. M. și colab., Partea VI. Algoritmi pentru lucrul cu grafice // Algoritmi: constructie si analiza = Introduction to Algorithms. - Ed. a II-a. - M. : Williams, 2006. - S. 1296. - ISBN 0-07-013151-1 .
Ore O. Teoria grafurilor. — M .: Nauka, 1968. — 336 p.
Grafice // Dicţionar enciclopedic al unui tânăr matematician / Comp. A. P. Savin. - M . : Pedagogie , 1985. - S. 86 -88. — 352 p.
Salii VN, Bogomolov AM Fundamentele algebrice ale teoriei sistemelor discrete. - M .: Literatură fizică și matematică, 1997. - ISBN 5-02-015033-9 .
Wilson R. Introducere în teoria grafurilor. — M .: Mir, 1977. — 208 p.
Harari F. Teoria grafurilor. — M .: Mir, 1973.