En teoría de grafos , un vértice adyacente de un vértice v en un gráfico es un vértice que está conectado av por una arista . La vecindad de un vértice v en un gráfico G es el subgráfico de G inducido por todos los vértices adyacentes av , es decir, el gráfico compuesto por los vértices adyacentes av y todos los bordes que conectan los vértices adyacentes av . Por ejemplo, en la imagen de la derecha, la vecindad del vértice 5 consta de los vértices 1, 2 y 4 y el borde que conecta los vértices 1 y 2.
- Para conocer otros significados de barrios en matemáticas, consulte Barrio (matemáticas) . Para vecindarios no matemáticos, consulte Vecindario (desambiguación) .
La vecindad a menudo se denota N G ( v ) o (cuando el gráfico no es ambiguo) N ( v ). La misma notación de vecindad también se puede usar para referirse a conjuntos de vértices adyacentes en lugar de los correspondientes subgrafos inducidos. La vecindad descrita anteriormente no incluye v en sí, y es más específicamente la vecindad abierta de v ; también es posible definir una vecindad en la que se incluye v , llamada vecindad cerrada y denotada por N G [ v ]. Cuando se indica sin ninguna calificación, se asume que un vecindario está abierto.
Los vecindarios pueden usarse para representar gráficos en algoritmos de computadora, a través de la lista de adyacencia y las representaciones de matriz de adyacencia . Los vecindarios también se utilizan en el coeficiente de agrupamiento de un gráfico, que es una medida de la densidad promedio de sus vecindarios. Además, muchas clases importantes de gráficos pueden definirse por las propiedades de sus vecindarios o por simetrías que relacionan los vecindarios entre sí.
Un vértice aislado no tiene vértices adyacentes. El grado de un vértice es igual al número de vértices adyacentes. Un caso especial es un bucle que conecta un vértice consigo mismo; si existe tal borde, el vértice pertenece a su propia vecindad.
Propiedades locales en gráficos
Si todos los vértices en G tienen vecindarios que son isomorfos al mismo grafo H , se dice que G es localmente H , y si todos los vértices en G tienen vecindarios que pertenecen a alguna familia de grafos F , se dice que G es localmente F ( Hell 1978 , Sedláček 1983 ). Por ejemplo, en el gráfico de octaedro , que se muestra en la figura, cada vértice tiene un vecindario isomorfo a un ciclo de cuatro vértices, por lo que el octaedro es localmente C 4 .
Por ejemplo:
- Cualquier grafo completo K n es localmente K n-1 . Los únicos gráficos que están localmente completos son uniones disjuntas de gráficos completos.
- Un gráfico de Turán T ( rs , r ) es localmente T (( r -1) s , r -1). De manera más general, cualquier grafo de Turán es localmente Turán.
- Cada grafo plano es localmente plano exterior . Sin embargo, no todos los grafos del plano exterior local son planos.
- Una gráfica está libre de triángulos si y solo si es localmente independiente .
- Cada k - gráfico cromático es localmente ( k -1) -cromático. Cada gráfico localmente k -cromático tiene un número cromático( Wigderson 1983 ).
- Si una familia gráfico F está cerrada bajo la operación de tomar subgrafos inducidos, entonces cada gráfico en F también es localmente F . Por ejemplo, cada grafo cordal es localmente cordal; cada gráfico perfecto es localmente perfecto; cada gráfico de comparabilidad es localmente comparable.
- Un gráfico es localmente cíclico si cada vecindario es un ciclo . Por ejemplo, el octaedro es el único gráfico C 4 conectado localmente , el icosaedro es el único gráfico C 5 conectado localmente , y el gráfico de Paley de orden 13 es C 6 localmente . Los gráficos localmente cíclicos distintos de K 4 son exactamente los gráficos subyacentes de las triangulaciones de Whitney , incrustaciones de gráficos en superficies de tal manera que las caras de la incrustación son las camarillas del gráfico ( Hartsfeld & Ringel 1991 ; Larrión, Neumann-Lara & Pizaña 2002 ; Malnič y Mohar 1992 ). Los gráficos cíclicos locales pueden tener tantos comobordes ( Seress y Szabó 1995 ).
- Los gráficos sin garras son los gráficos que son localmente libres de co -triángulos ; es decir, para todos los vértices, el gráfico de complemento de la vecindad del vértice no contiene un triángulo. Una gráfica que es localmente H está libre de garras si y solo si el número de independencia de H es como máximo dos; por ejemplo, la gráfica del icosaedro regular no tiene garras porque es localmente C 5 y C 5 tiene la independencia número dos.
- Los gráficos localmente lineales son los gráficos en los que cada vecindario es un emparejamiento inducido ( Fronček 1989 ).
Barrio de un conjunto
Para un conjunto A de vértices, el barrio de A es la unión de las vecindades de los vértices, y por lo que es el conjunto de todos los vértices adyacentes a al menos un miembro de A .
Un conjunto A de vértices en una gráfica se dice que es un módulo de si cada vértice en A tiene el mismo conjunto de vecinos fuera de A . Cualquier gráfico tiene una descomposición recursiva única en módulos, su descomposición modular , que se puede construir a partir del gráfico en tiempo lineal ; Los algoritmos de descomposición modular tienen aplicaciones en otros algoritmos de gráficos, incluido el reconocimiento de gráficos de comparabilidad .
Ver también
- Manta de markov
- Barrio de Moore
- Barrio de Von Neumann
- Segundo problema de barrio
- Figura de vértice , un concepto relacionado en geometría poliédrica
Referencias
- Fronček, Dalibor (1989), "Gráficos localmente lineales", Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz / 136481 , MR 1016323
- Hartsfeld, Nora; Ringel, Gerhard (1991), "Triangulaciones limpias", Combinatorica , 11 (2): 145-155, doi : 10.1007 / BF01206358.
- Hell, Pavol (1978), "Gráficos con vecindarios dados I", Problèmes combinatoires et théorie des graphes , Colloques internationaux CNRS, 260 , pp. 219-223.
- Larrión, F .; Neumann-Lara, V .; Pizaña, MA (2002), "Triangulaciones de Whitney, circunferencia local y gráficas de clicas iteradas" , Matemáticas discretas , 258 (1-3): 123-135, doi : 10.1016 / S0012-365X (02) 00266-2.
- Malnič, Aleksander; Mohar, Bojan (1992), "Generación de triangulaciones localmente cíclicas de superficies", Journal of Combinatorial Theory, Serie B , 56 (2): 147-164, doi : 10.1016 / 0095-8956 (92) 90015-P.
- Sedláček, J. (1983), "Sobre las propiedades locales de los gráficos finitos", Teoría de grafos, Lagów , Lecture Notes in Mathematics, 1018 , Springer-Verlag, págs. 242–247, doi : 10.1007 / BFb0071634 , ISBN 978-3-540-12687-4.
- Seress, Ákos; Szabó, Tibor (1995), "Gráficos densos con vecindarios en bicicleta" , Journal of Combinatorial Theory, Serie B , 63 (2): 281-293, doi : 10.1006 / jctb.1995.1020 , archivado desde el original el 30 de agosto de 2005.
- Wigderson, Avi (1983), "Mejora de la garantía de rendimiento para coloración aproximada de gráficos", Journal of the ACM , 30 (4): 729–735, doi : 10.1145 / 2157.2158.