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.
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 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.
Referencias editar
- Hartsfeld, N.; Ringel, G. (1991). «Clean triangulations». Combinatorica 11: 145-155. doi:10.1007/BF01206358.
- 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.
- Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002). «Whitney triangulations, local girth and iterated clique graphs». Discrete Mathematics 258: 123-135. doi:10.1016/S0012-365X(02)00266-2.
- Malnič, Aleksander; Mohar, Bojan (1992). «Generating locally cyclic triangulations of surfaces». Journal of Combinatorial Theory, Series B 56 (2): 147-164. doi:10.1016/0095-8956(92)90015-P.
- Sedlacek, J. (1983). «On local properties of finite graphs». Graph Theory, Lagów. Lecture Notes in Mathematics, no. 1018, Springer-Verlag. pp. 242-247.
- Seress, Ákos; Szabó, Tibor (1995). «Dense graphs with cycle neighborhoods». Journal of Combinatorial Theory, Series B 63: 281-293. doi:10.1006/jctb.1995.1020. Archivado desde el original el 30 de agosto de 2005.
- Wigderson, Avi (1983). «Improving the performance guarantee for approximate graph coloring». Journal of the ACM 30 (4): 729-735. doi:10.1145/2157.2158.
Datos: Q1354987
