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 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
Hartsfeld, N.; Ringel, G. (1991). «Clean triangulations». Combinatorica11: 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 Mathematics258: 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 B56 (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). . Journal of Combinatorial Theory, Series B63: 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 ACM30 (4): 729-735. doi:10.1145/2157.2158.
Datos:Q1354987
Noviembre 21, 2022
vecindad, teoría, grafos, teoría, grafos, vértice, adyacente, vértice, grafo, vértice, está, conectado, mediante, arista, vecindad, vértice, grafo, subgrafo, inducido, está, formado, todos, vértices, adyacentes, todas, aristas, conectan, dichos, vértices, ejem. En teoria de grafos un vertice adyacente de un vertice v en un grafo es un vertice que esta conectado a v mediante una arista La vecindad de un vertice v en un grafo G es el subgrafo inducido de G que esta formado por todos los vertices adyacentes y todas las aristas que conectan dichos vertices Por ejemplo la imagen muestra un grafo de 6 vertices y 7 aristas El vertice 5 es adyacente a los vertices 1 2 y 4 pero no es adyacente a los vertices 3 y 6 La vecindad del vertice 5 es el grafo con 3 vertices 1 2 y 4 y una arista conectando los vertices 1 y 2 Un grafo de 6 vertices y 7 aristas La vecindad es frecuentemente denotada NG v o cuando el grafo no es ambiguo N v La misma notacion tambien puede referirse a los conjuntos de vertices adyacentes en lugar de al correspondiente subgrafo La vecindad descrita anteriormente no incluye al mismo v y es mas especifico referirse como la vecindad abierta de v tambien 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 EditarHartsfeld 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 Larrion F Neumann Lara V Pizana M A 2002 Whitney triangulations local girth and iterated clique graphs Discrete Mathematics 258 123 135 doi 10 1016 S0012 365X 02 00266 2 Malnic 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 Lagow Lecture Notes in Mathematics no 1018 Springer Verlag pp 242 247 Seress Akos Szabo 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 Obtenido de https es wikipedia org w index php title Vecindad teoria de grafos amp oldid 118022698, wikipedia, wiki, leyendo, leer, libro, biblioteca,
