Vecindad (teoría de grafos)

En teoría de grafos, un vértice adyacente, vecindad o neighbourhood 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 grafo G es el subgrafo de G inducido por todos los vértices adyacentes av, es decir, el grafo compuesto por los vértices adyacentes avy todas las aristas que conectan los vértices adyacentes av.

El vecindario a menudo se denota o (cuando el gráfico no es ambiguo) . La misma notación de vecindad también se puede usar para referirse a conjuntos de vértices adyacentes en lugar de los subgrafos inducidos correspondientes. La vecindad descrita arriba no incluye a la propia v, y es más específicamente la vecindad abierta de v; también es posible definir una vecindad en la que el mismo v está incluido, llamada vecindad cerrada y denotada por . Cuando se establece sin ninguna calificación, se supone que un vecindario está abierto.

Los vecindarios se pueden usar para representar gráficos en algoritmos informáticos, 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 agrupación de un gráfico, que es una medida de la densidad promedio de sus vecindarios. Además, muchas clases importantes de grafos pueden definirse por las propiedades de sus vecindarios o por las 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 tal borde existe, el vértice pertenece a su propio vecindario.

Propiedades locales en grafos

Si todos los vértices en G tienen vecindades que son isomorfas al mismo grafo H, se dice que G es localmente H, y si todos los vértices en G tienen vecindades 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 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 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.
• Cada gráfico plano es localmente plano exterior. Sin embargo, no todos los gráficos localmente planos exteriores son planos.
• Un grafo no tiene triángulos si y solo si es localmente independiente.
• Todo gráfico k -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 de grafos F se cierra bajo la operación de tomar subgrafos inducidos, entonces cada grafo en F es también localmente F. Por ejemplo, todo grafo cordal es localmente cordal; todo grafo perfecto es localmente perfecto; cada gráfico de comparabilidad es localmente comparable.
• Un grafo es localmente cíclico si cada vecindad es un ciclo. Por ejemplo, el octaedro es el único grafo C ₄ localmente conectado, el icosaedro es el único grafo C ₅ localmente conectado y el gráfico de Paley de orden 13 es C ₆ localmente. Grafos localmente cíclicos que no sean 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 (Hartsfeld & Ringel 1991; Larrión, Neumann-Lara & Pizaña 2002; Malnič y Mohar 1992). Los grafos localmente cíclicos pueden tener tantos como aristas (Seress & Szabó 1995).
• Los gráficos sin garras son los gráficos que están localmente libres de cotriángulos; es decir, para todos los vértices, el gráfico de complemento de la vecindad del vértice no contiene un triángulo. Un gráfico que es localmente H no tiene garras si y solo si el número de independencia de H es como máximo dos; por ejemplo, el gráfico del icosaedro regular no tiene garras porque es localmente C ₅ y C ₅ tiene la independencia número dos.
• Los grafos localmente lineales son los grafos en los que cada vecindad es un emparejamiento inducido (Fronček 1989).

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 se puede construir a partir del gráfico en tiempo lineal; Los algoritmos de descomposición modular tienen aplicaciones en otros algoritmos gráficos, incluido el reconocimiento de gráficos de comparabilidad.