Veïnat (teoria de grafos)

Archiu:6n-graf.svg

Un grafo de 6 vèrtiços i 7 arestes

En teoria de grafos, un vèrtiç adjacent d'un vèrtiç v en un grafo és un vèrtiç que està conectat a v per mig d'una aresta. El veïnat d'un vèrtiç v en un grafo G és el subgrafo induït de G que està format per tots els vèrtiços adjacents i totes les arestes que conecten dits vèrtiços. Per eixemple, l'image mostra un grafo de 6 vèrtiços i 7 arestes. El vèrtiç 5 és adjacent als vèrtiços 1, 2, i 4, pero no és adjacent als vèrtiços 3 i 6. El veïnat del vèrtiç 5 és el grafo en 3 vèrtiços, 1, 2, i 4, i una aresta conectant els vèrtiços 1 i 2.

El veïnat és freqüentment denotada N_G(v) o (quan el grafo no és ambigu) N(v). La mateixa notació també pot referir-se als conjunts de vèrtiços adjacents en lloc del corresponent subgrafo. El veïnat descrit anteriorment no inclou al mateix v, i és més específic referir-se com el veïnat obert de v; també és possible definir un veïnat a on v este inclós, cridada el veïnat tancat i denotada per N_G[v]. Quan apareix sense especificar, el veïnat es presumix oberta.