Vecindario (teoría de grafos)
En la teoría de grafos, un vértice adyacente de un vértice v es un vértice conectado a v por una arista . Una vecindad de un vértice v en un gráfico G es un subgráfico generado del gráfico G , que consta de todos los vértices conjugados con v y todos los bordes que conectan dos de esos vértices. Por ejemplo, la figura muestra un gráfico con 6 vértices y 7 aristas. El vértice 5 es adyacente a los vértices 1, 2 y 4, pero no adyacente a los vértices 3 y 6. La vecindad del vértice 5 es un gráfico con tres vértices 1, 2 y 4, y una arista que conecta los vértices 1 y 2.
Un vecindario a menudo se denota como N G ( v ) o (si sabe qué gráfico está en cuestión) N ( v ). La misma notación de vecindad se puede usar para referirse al conjunto de vértices adyacentes en lugar del subgrafo generado correspondiente. La vecindad descrita arriba no incluye a la propia v , y esta vecindad se conoce como una vecindad abierta de v . Puede definir un vecindario que incluya v . En este caso, el vecindario se llama cerrado y se denota como N G [ v ]. A menos que se especifique explícitamente, se supone que la vecindad está abierta.
Los vecindarios se pueden usar para representar gráficos en algoritmos informáticos a través de una lista de adyacencia y una matriz de adyacencia . Los vecindarios también se utilizan en el coeficiente de agrupación de un gráfico, que mide la densidad promedio de sus vecindarios. Además, muchas clases importantes de grafos pueden definirse por las propiedades de sus vecindades o por la simetría mutua de las vecindades.
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 con el mismo vértice. Si tal borde existe, el vértice pertenece a su propia vecindad.
Propiedades locales de un grafo
Si todos los vértices de un grafo G tienen vecindades isomorfas a algún grafo H , entonces se dice que G es localmente un grafo H , y si todos los vértices de G tienen vecindades pertenecientes a alguna familia de grafos F , se dice que G es localmente un grafo F [1] [2] . Por ejemplo, en el gráfico del octaedro que se muestra en la figura, cada vértice tiene una vecindad isomorfa 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 un grafo K n-1 . Los únicos grafos localmente completos son la unión disjunta de grafos completos.
- El gráfico de Turan T ( rs , r ) es localmente equivalente a T (( r -1) s , r -1). Es decir, cualquier gráfico de Turan es localmente un gráfico de Turan.
- Cualquier gráfico plano es localmente plano exterior . Sin embargo, no todos los gráficos localmente planos exteriores son planos.
- Un grafo es un grafo libre de triángulos si y solo si es localmente independiente .
- Cualquier gráfico k - cromático es localmente ( k -1) -cromático. Cualquier gráfico cromático localmente k tiene un número cromático [3] .
![{\displaystyle O({\sqrt {kn)))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7df7b1e720ef01af5417f3bb4c63f8376a6ea078)
- Si una familia de grafos F se cierra bajo la operación de tomar subgrafos generados, entonces cualquier grafo en F es también localmente F. Por ejemplo, cualquier gráfico cordal es localmente cordal, cualquier gráfico perfecto es localmente perfecto, cualquier gráfico de comparabilidad es un gráfico de comparabilidad.
- Un grafo es localmente cíclico si cada vecindad es un ciclo . Por ejemplo, el gráfico del octaedro es el único gráfico localmente C 4 , el gráfico del icosaedro es el único gráfico localmente C 5 y el gráfico de Paley de orden 13 es localmente C 6 . Los gráficos localmente cíclicos que no sean K 4 son precisamente los gráficos subyacentes a la triangulación de Whitney , que incrusta gráficos en una superficie de tal manera que las caras de la incrustación corresponden a las camarillas del gráfico [4] [5] [6] . Los gráficos localmente cíclicos pueden llegar hasta los bordes [7] .
![{\ Displaystyle n^{2-o(1)))](https://wikimedia.org/api/rest_v1/media/math/render/svg/5057caa2c2df82166585d1fffd2d8046dc0e6b46)
- Los gráficos sin garras son gráficos que localmente no tienen triángulos . Es decir, para todos los vértices, el complemento del gráfico de vecindad de vértices no contiene triángulos. Un grafo que es localmente un grafo H no contiene garras si y sólo si el número de independencia de H es como máximo dos. Por ejemplo, la gráfica de un icosaedro regular no contiene garras porque es localmente C 5 y el número de independencia C 5 es dos.
Muchos vecinos
Para un conjunto A de vértices, la vecindad de A es la unión de las vecindades de los vértices, de modo que contiene todos los vértices conjugados a por lo menos un miembro de
A.
Se dice que un conjunto de vértices A de un grafo es un módulo si todos los vértices de A tienen el mismo conjunto de vecindades fuera de A. Cualquier gráfico tiene una modularización recursiva única, llamada modularización , que se puede construir a partir del gráfico en tiempo lineal . El algoritmo de descomposición modular se aplica a otros algoritmos para gráficos, incluido el reconocimiento de gráficos de comparabilidad .
Véase también
Notas
- ↑ Infierno, 1978 .
- ↑ Sedlaceck, 1983 .
- ↑ Wigderson, 1983 .
- ↑ Hartsfeld, Ringel, 1991 .
- ↑ Larrión, Neumann-Lara, Pizaña, 2002 .
- ↑ Malnic, Mohar, 1992 .
- ↑ Seress, Szabo, 1995 .
Literatura
- Nora Hartsfeld, Gerhard Ringel. Triangulaciones limpias // Combinatorica . - 1991. - vol. 11, núm. 2.- Pág. 145-155. -doi : 10.1007/ BF01206358 .
- Infierno de Pavol. . Grafos con vecindades dadas I // Problemes Combinatoires et Théorie des Graphes. - París: Éditions du Centre national de la recherche scientifique, 1978. - xiv + 443 p. — (Colloques internationaux CNRS, vol. 260). — ISBN 2222020700 . - Pág. 219-223.
- F. Larrión, V. Neumann-Lara, M. A. Pizaña. Triangulaciones de Whitney, circunferencia local y gráficos de camarilla iterados // Matemáticas discretas . - 2002. - vol. 258. - Pág. 123-135. - doi : 10.1016/S0012-365X(02)00266-2 .
- Aleksander Malnic, Bojan Mohar. Generación de triangulaciones cíclicas locales de superficies // Journal of Combinatorial Theory, Serie B . - 1992. - vol. 56, núm. 2.- Pág. 147-164. -doi : 10.1016 / 0095-8956(92)90015-P .
- J. Sedlacek. . Sobre propiedades locales de grafos finitos // Graph Theory, Lagow. - Springer-Verlag, 1983. - (Lecture Notes in Mathematics, vol. 1018). - ISBN 978-3-540-12687-4 . -doi : 10.1007/ BFb0071634 . - Pág. 242-247.
- Ákos Seress, Tibor Szabo. Gráficos densos con vecindades de ciclo // Journal of Combinatorial Theory, Serie B . - 1995. - vol. 63, núm. 2.- Pág. 281-293. -doi : 10.1006/ jctb.1995.1020 . Archivado desde el original el 30 de agosto de 2005.
- Avi Widderson. Mejora de la garantía de rendimiento para la coloración aproximada de gráficos // Journal of the ACM . - 1983. - vol. 30, núm. 4.- Pág. 729-735. -doi : 10.1145/ 2157.2158 .