Glosar de teoria graficelor

Un grafic G este o pereche ( V , E ) unde V este un set și E ⊆ V × V este un subset al produsului cartezian al lui V de la sine. Elementele lui V se numesc noduri, iar cele ale lui E se numesc arce . Nodurile sunt deseori numite „vârfuri”. Arcurile se mai numesc „laturi” sau „margini”.

Există două tipuri de grafice:

graficele nedirecționate , unde relația E este simetrică , atunci (a, b) ∈ E → (b, a) ∈ E. În acest tip de grafic, arcurile sunt adesea numite margini, iar nodurile sunt vârfuri .
grafice orientate , unde relația E nu este simetrică și există o relație de ordine între noduri.

Index
0 - 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ?

LA

Adiacenta

Pentru un nod x al unui grafic G = ( V , E ), setul de noduri conectate se numește adiacență Adj ( x ).

Copac

Același subiect în detaliu: Arborele (grafic) .

Un copac este o pădure conectată, adică un grafic conectat și aciclic. ^[1] Poate fi definit și ca un grafic nedirecționat în care oricare două vârfuri sunt conectate printr-o singură cale.

Arborele liber

Un copac liber este un grafic conectat și aciclic nedirecționat.

Arc

Un arc (sau margine ), împreună cu vârful , este unul dintre cele două blocuri fundamentale ale unui grafic. Într-un grafic $G=\langle V,E\rangle$ ${\ displaystyle G = \ langle V, E \ rangle}$ ${\ displaystyle G = \ langle V, E \ rangle}$ fiecare arc $e\in E$ ${\ displaystyle și \ în E}$ ${\ displaystyle și \ în E}$ găsiți o pereche de vârfuri $(v,u)\in V^{2}$ ${\ displaystyle (v, u) \ în V ^ {2}}$ ${\ displaystyle (v, u) \ în V ^ {2}}$ .

C.

Buclă

Un arc care are două capete coincidente se numește buclă .

Lanţ

Fie G = ( V , E ) un grafic orientat sau nedirecționat: un n-tuplu de noduri ( v ₀ , ..., v _m ) se numește un lanț de lungime m între v ₀ și v _m dacă:

(\forall i=1,...,m)((v_{i-1},v_{i})\in E)\lor ((v_{i},v_{i-1})\in E)

{\ displaystyle (\ forall i = 1, ..., m) ((v_ {i-1}, v_ {i}) \ în E) \ lor ((v_ {i}, v_ {i-1}) \ în E)}

{\ displaystyle (\ forall i = 1, ..., m) ((v_ {i-1}, v_ {i}) \ în E) \ lor ((v_ {i}, v_ {i-1}) \ în E)}

Un lanț ( v ₀ , ..., v _m , v ₀ ) se numește ciclic . Un grafic a-ciclic poate conține lanțuri ciclice, caz în care nu este conectat singular.

Ciclu

Într-un grafic spunem ciclu (sau circuit ) de lungime m un lanț ( v ₀ , ..., v _{m -1} , v ₀ ); un ciclu simplu este un ciclu care nu trece de două ori de la același nod sau formal un ciclu ( v ₀ , ..., v _{m -1} , v ₀ ) pentru care:

\forall i,k=1,...,m-1,(i\neq k\Rightarrow v_{i}\neq v_{k})

{\ displaystyle \ forall i, k = 1, ..., m-1, (i \ neq k \ Rightarrow v_ {i} \ neq v_ {k})}

\ forall i, k = 1, ..., m-1, (i \ neq k \ Rightarrow v_ {i} \ neq v_ {k})

Clique (sau clica)

Dacă G = (V, E) este un grafic nedirecționat, o clică (sau o clică) C G este un plafon complet al subgrafului, adică astfel încât toate nodurile C să fie adiacente în perechi și că niciun alt subgraf complet al lui G nu conține C.

Conexiune

Se spune că Vertex v este conectat la w dacă există o cale de la v la w .
Se spune că un grafic este conectat dacă vârfurile v și w sunt conectate pentru toate v , w ∈ V.
Se spune că un grafic direcționat este puternic conectat dacă există o cale de la v la w pentru fiecare pereche v , w ∈ V

Acoperire Markov

Având în vedere un nod N al unui grafic direcționat G = ( V , E ), capacul Markov Bl ( N ) este definit ca:

\mathrm {Bl} (N)=\{X\in Vt.c.(N,X)\in E\lor (X,N)\in E\lor ((N,K)\in E\land (X,K)\in E)\}

{\ displaystyle \ mathrm {Bl} (N) = \ {X \ în Vt.c. (N, X) \ în E \ lor (X, N) \ în E \ lor ((N, K) \ în E \ land (X, K) \ în E) \}}

\ mathrm {Bl} (N) = \ {X \ in Vt.c. (N, X) \ in E \ lor (X, N) \ in E \ lor ((N, K) \ in E \ land ( X, K) \ în E) \}

Frânghie

Într-un grafic nedirecționat, o cale simplă sau un ciclu are o coardă dacă există un arc între două noduri non-consecutive ale ciclului.

ȘI

Excentricitate

Având în vedere un grafic G conectat, excentricitatea e ( v ) a unui punct v este definită ca maximul lui d ( u , v ) pentru fiecare punct u al graficului.

F.

pădure

O pădure este un grafic fără cicluri . ^[1] Numele derivă din faptul că componentele conectate ale unei păduri sunt copaci .

Fiule, nod

Fie G = ( V , E ) un grafic orientat; toate nodurile p ₀ , ..., p _n astfel încât ( v , p _i ) aparțin lui E se spune că sunt copii ai unui nod v al lui G. Dacă G este un copac, nodurile copil sunt numite și succesori .

G.

Părinte, nod

Fie G = ( V , E ) un grafic orientat; toate nodurile p ₀ , ..., p _n astfel încât ( p ₀ , v ) ∈ E se spune că sunt părinții unui nod v al lui G. Dacă G este un copac, nodurile părinte se mai numesc strămoși .

Gradul unui vârf

Numărul de muchii incidente într-un vârf v ∈ V (adică numărul de muchii care se conectează la acesta) se numește gradul de vârf v . Un arc care leagă vârful la ambele capete (o buclă) este numărat de două ori.

Grafic complet

Fie G = ( V , E ) un grafic nedirecționat; Se spune că G este complet dacă

\forall x\in V,\forall y\in V,y\in Adj(x)

{\ displaystyle \ forall x \ in V, \ forall y \ in V, y \ in Adj (x)}

\ forall x \ in V, \ forall y \ in V, y \ in Adj (x)

Dacă N este numărul de noduri, numărul muchiilor unui grafic complet este N ( N - 1) / 2

Grafic conectat

Se spune că un grafic este conectat dacă pentru fiecare pereche de noduri ( v , w ) există o cale care le unește.

Grafic triangular

Se spune că un grafic nedirectat este triangulat dacă fiecare ciclu de lungime mai mare sau egal cu 4 are o coardă.

Grafic plan

Se spune că un grafic este plan dacă poate fi reprezentat în plan astfel încât arcurile să se intersecteze numai la vârfuri.

M.

Pulover

O plasă este un subgraf conectat în care toate nodurile sunt de ordinul doi.

SAU

Ordin perfect

Fie G = ( V , E ) un grafic nedirecționat cu cardul ( V ) = n ; o ordonare a nodurilor

\alpha =[V_{1},...,V_{n}]

{\ displaystyle \ alpha = [V_ {1}, ..., V_ {n}]}

\ alpha = [V_ {1}, ..., V_ {n}]

se spune perfect dacă

\forall i,Adj(v_{i})\cap \{v_{1},...,v_{i-1}\}

{\ displaystyle \ forall i, Adj (v_ {i}) \ cap \ {v_ {1}, ..., v_ {i-1} \}}

\ forall i, Adj (v_ {i}) \ cap \ {v_ {1}, ..., v_ {i-1} \}

este o subsecțiune completă a lui G.

P.

cale

Fie G = ( V , E ) un grafic orientat sau nedirecționat: un n- tuplu de noduri ( v ₀ , ..., v _m ) se numește o cale de lungime m între v ₀ și v _m dacă:

(\forall i=1,...,m)(v_{i-1},v_{i})\in E

{\ displaystyle (\ forall i = 1, ..., m) (v_ {i-1}, v_ {i}) \ în E}

{\ displaystyle (\ forall i = 1, ..., m) (v_ {i-1}, v_ {i}) \ în E}

Evident, dacă G nu este direcționat, fiecare lanț al lui G este, de asemenea, o cale a lui G și invers.

Greutate

Un grafic ponderat asociază o etichetă (greutate) la fiecare dintre marginile sale. Greutățile sunt exprimate în general ca numere reale, dar pot fi restrânse la setul de raționale sau de numere întregi. Unii algoritmi au nevoie de mai multe restricții asupra greutății. De exemplu, algoritmul lui Dijkstra funcționează corect numai cu greutăți pozitive. Uneori, greutatea dintre două vârfuri care nu sunt conectate printr-un arc este indicată cu valoarea infinită .

bine

Într-un grafic direcționat, se spune că un nod este un puț dacă are un grad de ieșire egal cu 0.

Fântână universală

Într-un grafic orientat, un nod este numit godeu universal dacă are un grad de intrare egal cu n - 1 și un grad de ieșire egal cu 0. Dacă un godeu universal este prezent într-un grafic, acesta este unic.

R.

Rădăcină, nod

Într-un grafic orientat, un nod care nu are părinți.

S.

Subgraf

Subgraful unui grafic G este un grafic al cărui set de vârfuri este un subset al celui al lui G și a cărui relație de adiacență este un subset al celui al lui G limitat la acest subset. În sens invers, un supergraf al unui grafic G este un grafic al cărui G este un subgraf. Spunem că un grafic G conține un alt grafic H dacă un subgraf al lui G este H sau este izomorf pentru H.

Un subgraf H este un subgraf de acoperire (care se întinde subgraf în engleză ) sau un factor al unui grafic G dacă are același set de vârfuri ale lui G. Să spunem că H acoperă G.

Se spune că un subgraf H al unui grafic G este indus (sau umplut ) dacă, pentru orice pereche de vârfuri x și y de H, xy este o margine a lui H dacă și numai dacă xy este o margine a lui G. Cu alte cuvinte, H este un subgraf indus de G dacă are exact marginile care apar în G pe același set de vârfuri. Dacă mulțimea vârfurilor lui H este subsetul S al lui V (G) , atunci H poate fi scris ca G [ S ] și se spune că este indus de S.

Un grafic G este minim în raport cu o anumită proprietate P cu condiția ca G să aibă proprietatea P și nici un subgraf propriu-zis al lui G să nu aibă proprietatea P. În această definiție, termenul subgraf este de obicei înțeles să însemne „subgraf indus”. Noțiunea de maximalitate este definită dual : G este maximă față de P, cu condiția ca P ( G ) și G să nu aibă un supergraf propriu H astfel încât P ( H ).

Un grafic A care nu conține H ca subgraf indus se spune că este fără H și, mai general, dacă ${\mathcal {F}}$ ${\ displaystyle {\ mathcal {F}}}$ ${\ mathcal {F}}$ este o familie de grafice, apoi grafice care nu conțin niciun subgraf indus izomorf unui membru al ${\mathcal {F}}$ ${\ displaystyle {\ mathcal {F}}}$ ${\ mathcal {F}}$ se numesc fără ${\mathcal {F}}$ ${\ displaystyle {\ mathcal {F}}}$ ${\ mathcal {F}}$ . De exemplu, graficele fără triunghiuri sunt grafice care nu au un grafic triunghi ca subgraf indus.

Un grafic universal dintr-o clasă K de grafuri este un grafic simplu în care fiecare element din K poate fi încorporat ca subgraf.

T.

Turul unui grafic

Fiind dat un graf neorientat G, un tur în G este un ciclu care trece exact o singură dată pentru fiecare nod G. Costul unui tur este suma costurilor arcurilor sale.

Notă

^ ^a ^b Vest , p.68 .

Bibliografie

Béla Bollobás (1998): Teoria modernă a graficelor . New York: Springer-Verlag. ISBN 0-387-98488-7 [ Tratament avansat; prezentări istorice ale concluziilor capitolelor. ]
(EN) Douglas B. West, Introducere în teoria graficelor , 2001, ISBN 8178088304 .

Elemente conexe

linkuri externe

( EN ) Eric W. Weisstein, Grafo , în MathWorld , Wolfram Research.

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

[West_p68-1] Vest , p.68 .

[1]