Vecindad (teoría de grafos)

La vecindad de un vértice v en un grafo G es el subgrafo inducido de G que está formado por todos los vértices adyacentes y todas las aristas que conectan dichos vértices.

Por ejemplo, la imagen muestra un grafo de 6 vértices y 7 aristas.

La misma notación también puede referirse a los conjuntos de vértices adyacentes en lugar de al correspondiente subgrafo.

La vecindad descrita anteriormente no incluye al mismo v, y es más específico referirse como la vecindad abierta de v; también es posible definir una vecindad donde v este incluido, llamada la vecindad cerrada y denotada por NG[v].

Cuando aparece sin especificar, la vecindad se presume abierta.