Vecindad (teoría de grafos)

En teoría de grafos, un vértice adyacente de un vértice v en un grafo es un vértice que está conectado a v mediante una arista. 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. El vértice 5 es adyacente a los vértices 1, 2, y 4, pero no es adyacente a los vértices 3 y 6. La vecindad del vértice 5 es el grafo con 3 vértices, 1, 2, y 4, y una arista conectando los vértices 1 y 2.

Un grafo de 6 vértices y 7 aristas

La vecindad es frecuentemente denotada N_G(v) o (cuando el grafo no es ambiguo) N(v). 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 N_G[v]. Cuando aparece sin especificar, la vecindad se presume abierta.