Nabolaget (grafteori)

I grafteori sier vi at to hjørner av en ikke-orientert graf er naboer eller tilstøtende hvis de er forbundet med en kant. Det området av en verteks kan betegne alle sine nabo toppunktene eller også en tilhørende subgraf, for eksempel den induserte sub-graf. I en rettet graf brukes vanligvis begrepet forgjenger eller etterfølger.

Formell definisjon

Klassiske definisjoner

I en ikke-rettet graf kan nabolaget til et toppunkt , ofte betegnet ( N for nabolaget ), betegne flere ting: $G = (V, E)$ $v \ in V$ $N_ {G} (v)$

Settet med nabotopper: $\ {w: (v, w) \ i E \}$
Underbildet av indusert av de forrige toppunktene, med eller uten, avhengig av versjon. $G$ $v$

Varianter

Når det gjelder orienterte grafer, kan vi også definere en forestilling om orientert nabolag.
Det hender at vi betrakter en nabo i avstand fra toppunktet, det vil si alle toppunktene skilt fra v med mindre enn k kanter. Dette er spesielt tilfelle i synkron distribuert beregning. $k$

Bruker

Begrepet nabolag er en klassisk forestilling om grafteori, det griper inn for eksempel for å definere begrepene farging , stabil og dekning av hjørner .

Et eksempel på anvendelse er modellering av sosiale nettverk der nabolaget til et toppunkt representerer kunnskapen til en person. I denne sammenheng gjør nabolaget det mulig å definere klyngekoeffisienten .

Merknader og referanser

For eksempel i Olivier Fouquet, Théorie des graphes: en kort introduksjon (med antatt algebraisk skjevhet) ,2012( les online [PDF] ).
Se for eksempel i David Peleg , Distributed Computing: A Locality-Sensitive Approach , vol. 5, SIAM,2000