Barrio (teoría de grafos)

Subgrafo formado por todos los nodos vinculados a un nodo determinado de un gráfico

En este gráfico, los vértices adyacentes a 5 son 1, 2 y 4. La vecindad de 5 es el gráfico que consta de los vértices 1, 2, 4 y el borde que conecta 1 y 2.

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 a v por una arista . La vecindad de un vértice v en un gráfico G es el subgrafo de G inducido por todos los vértices adyacentes a v , es decir, el gráfico compuesto por los vértices adyacentes a v y todos los bordes que conectan los vértices adyacentes a v .

La vecindad a menudo se denota o (cuando la gráfica no es ambigua) . También se puede utilizar la misma notación de vecindad para referirse a conjuntos de vértices adyacentes en lugar de a los correspondientes subgrafos inducidos. La vecindad descrita anteriormente no incluye a v en sí misma y es más específicamente la vecindad abierta de v ; También es posible definir una vecindad en la que se incluye el propio v , denominada vecindad cerrada y denotada por . Cuando se indica sin ninguna calificación, se supone que un vecindario está abierto. ${\displaystyle N_{G}(v)}$ ${\displaystyle N(v)}$ ${\displaystyle N_{G}[v]}$

Los vecindarios se pueden utilizar para representar gráficos en algoritmos informáticos, a través de representaciones de listas de adyacencia y matrices de adyacencia . Los barrios también se utilizan en el coeficiente de agrupamiento de un gráfico, que es una medida de la densidad media de sus barrios. Además, muchas clases importantes de gráficos pueden definirse por propiedades de sus vecindades o por simetrías que relacionan las vecindades 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.

En el gráfico del octaedro , la vecindad de cualquier vértice es de 4 ciclos .

Si todos los vértices de G tienen vecindades que son isomorfas al mismo grafo H , se dice que G es localmente H , y si todos los vértices de G tienen vecindades que pertenecen a alguna familia de grafos F , se dice que G es localmente F. ^[1] 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 ₄ .

Por ejemplo:

• Cualquier gráfico completo K _n es localmente K _n-1 . Los únicos grafos que son localmente completos son las uniones disjuntas de grafos completos.
• Un grafo de Turán T ( rs , r ) es localmente T (( r -1) s , r -1). De manera más general, cualquier gráfico de Turán es localmente Turán.
• Todo grafo plano es localmente plano externo . Sin embargo, no todos los gráficos localmente externos son planos.
• Una gráfica no tiene triángulos si y sólo si es localmente independiente .
• Cada k - gráfico cromático es localmente ( k -1)-cromático. Cada gráfico cromático localmente k tiene un número cromático . ^[2] ${\displaystyle O({\sqrt {kn}})}$
• Si una familia de gráficos F se cierra bajo la operación de tomar subgrafos inducidos, entonces cada gráfico en F también es localmente F. Por ejemplo, todo grafo cordal es localmente cordal; todo grafo perfecto es localmente perfecto; cada gráfico de comparabilidad es comparable localmente; cada gráfico (k)-(ultra)-homogéneo es localmente (k)-(ultra)-homogéneo.
• Una gráfica es localmente cíclica si cada vecindad es un ciclo . Por ejemplo, el octaedro es el único gráfico C ₄ conectado localmente , el icosaedro es el único gráfico C ₅ conectado localmente y el gráfico de Paley de orden 13 es C ₆ localmente . Los gráficos localmente cíclicos distintos de K ₄ 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. ^[3] Los gráficos localmente cíclicos pueden tener tantas aristas. ^[4] ${\displaystyle n^{2-o(1)}}$
• Los gráficos sin garras son los gráficos que localmente no tienen co-triángulos ; es decir, para todos los vértices, el gráfico complemento de la vecindad del vértice no contiene un triángulo. Un gráfico que es localmente H no tiene garras si y sólo 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 ₅ y C ₅ tiene independencia número dos.
• Las gráficas localmente lineales son aquellas en las que cada vecindad es una coincidencia inducida . ^[5]
• Las gráficas de Johnson son de cuadrícula local, lo que significa que cada vecindad es la gráfica de una torre . ^[6]

Barrio de un conjunto

Para un conjunto A de vértices, la vecindad de A es la unión de las vecindades de los vértices, por lo que es el conjunto de todos los vértices adyacentes a al menos un miembro  de A.

Se dice que un conjunto A de vértices en un gráfico es un módulo 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 puede construirse 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 von Neumann
• Segundo problema vecinal
• Figura de vértice , un concepto relacionado en poliedros
• Enlace (complejo simplicial) , una generalización de la vecindad a complejos simpliciales

Notas

1. Infierno 1978, Sedláček 1983
2. Wigderson 1983.
3. Hartsfeld y Ringel 1991; Larrión, Neumann-Lara & Pizaña 2002; Malnič y Mohar 1992
4. Seress y Szabó 1995.
5. Fronček 1989.
6. Cohen 1990.

Referencias

• Cohen, Arjeh M. (1990), "Reconocimiento local de gráficos, edificios y geometrías relacionadas" (PDF) , en Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (eds.), Geometrías finitas, edificios y temas relacionados: artículos de la conferencia sobre edificios y geometrías relacionadas celebrada en Pingree Park, Colorado, del 17 al 23 de julio de 1988 , Oxford Science Publications, Oxford University Press, págs. 85–94, SEÑOR  1072157; véanse en particular las págs. 89 y 90
• 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, S2CID  28144260.
• Hell, Pavol (1978), "Gráficos con vecindades dadas I", Problèmes combinatoires et théorie des graphes , Colloques internationaux CNRS, vol. 260, págs. 219-223.
• Larrión, F.; Neumann-Lara, V .; Pizaña, MA (2002), "Triangulaciones de Whitney, circunferencia local y gráficos de camarilla iterados", 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 de superficies localmente cíclicas", 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 gráficos finitos", Teoría de grafos, Lagów , Lecture Notes in Mathematics, vol. 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 vecindades de ciclo", Journal of Combinatorial Theory, Serie B , 63 (2): 281–293, doi : 10.1006/jctb.1995.1020.
• Wigderson, Avi (1983), "Mejora de la garantía de rendimiento para la coloración aproximada de gráficos", Journal of the ACM , 30 (4): 729–735, doi : 10.1145/2157.2158 , S2CID  32214512.