Vecinătate (teoria graficelor)

În teoria graficelor spunem că două vârfuri ale unui grafic neorientat sunt vecine sau adiacente dacă sunt conectate printr-o margine. Vecinătatea unui nod poate desemna toate nodurile învecinate sau altfel un subgraf asociat, de exemplu subgraful. Într-un grafic direcționat , se folosește în general termenul predecesor sau succesor.

Definiție formală

Definiții clasice

Într-un grafic nedirecționat , vecinătatea unui vârf , adesea notată ( N pentru vecinătate ) poate desemna mai multe lucruri: $G = (V, E)$ $v \ în V$ $N_ {G} (v)$

Setul de vârfuri învecinate: $\ {w: (v, w) \ în E \}$
Subgraful indus de vârfurile anterioare, cu sau fără în funcție de versiune. $G$ $v$

Variante

În cazul graficelor orientate, putem defini și o noțiune de vecinătate orientată.
Se întâmplă să considerăm un vecin la o distanță de un vârf, adică toate vârfurile separate de v cu mai puțin de k margini. Acesta este cazul în special în calculul distribuit sincron. $k$

Utilizări

Noțiunea de vecinătate este o noțiune clasică a teoriei graficelor, ea intervine de exemplu pentru a defini conceptele de colorare , de stabil și de acoperire prin vârfuri .

Un exemplu de aplicație este modelarea rețelelor sociale în care vecinătatea unui vârf reprezintă cunoașterea unei persoane. În acest context, vecinătatea face posibilă definirea coeficientului de grupare .

Note și referințe

De exemplu în Olivier Fouquet, Théorie des graphes: o scurtă introducere (cu o prejudecată algebrică presupusă) ,2012( citiți online [PDF] ).
Vezi de exemplu în David Peleg , Distributed Computing: A Locality-Sensitive Approach , vol. 5, SIAM,2000