Vecindad (teoría de grafos)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Un grafo de 6 vértices y 7 aristas

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.

La vecindad es frecuentemente denotada NG(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 mas 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.


Referencias[editar]

  • Hell, Pavol (1978). «Graphs with given neighborhoods I». Colloque internationaux C.N.R.S., No. 260, Problems Combinatories et theorie des graphes. pp. 219–223. 
  • Sedlacek, J. (1983). «On local properties of finite graphs». Graph Theory, Lagów. Lecture Notes in Mathematics, no. 1018, Springer-Verlag. pp. 242–247. 
  • Wigderson, Avi (1983). «Improving the performance guarantee for approximate graph coloring». Journal of the ACM 30 (4):  pp. 729–735. doi:10.1145/2157.2158.