stringtranslate.com

Vecindario (teoría de grafos)

En este grafo, los vértices adyacentes a 5 son 1, 2 y 4. El vecindario de 5 es el grafo que consiste en los vértices 1, 2, 4 y la arista que une 1 y 2.

En teoría de grafos , un vértice adyacente a un vértice v en un grafo 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 a v , es decir, el grafo compuesto por los vértices adyacentes a v y todas las aristas que conectan los vértices adyacentes a v .

El vecindario se denota a menudo como ⁠ ⁠ o (cuando el gráfico no es ambiguo) ⁠ ⁠ . La misma notación de vecindario también se puede usar para referirse a conjuntos de vértices adyacentes en lugar de los subgrafos inducidos correspondientes. El vecindario descrito anteriormente no incluye al propio v , y es más específicamente el vecindario abierto de v ; también es posible definir un vecindario en el que se incluye al propio v , llamado vecindario cerrado y denotado por ⁠ ⁠ . Cuando se establece sin ninguna calificación, se supone que un vecindario es abierto.

Los vecindarios se pueden utilizar para representar grafos en algoritmos informáticos, a través de representaciones de listas de adyacencia y matrices de adyacencia . Los vecindarios también se utilizan en el coeficiente de agrupamiento de un grafo, que es una medida de la densidad media de sus vecindarios. Además, muchas clases importantes de grafos se pueden definir 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 arista, 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 un ciclo de 4 .

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 . [1] Por ejemplo, en el grafo octaédrico , 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:

Vecindario de un conjunto

Para un conjunto A de vértices, el vecindario de A es la unión de los vecindarios de los vértices, y por lo tanto 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 grafo es un módulo si cada vértice en A tiene el mismo conjunto de vecinos fuera de A. Cualquier grafo tiene una descomposición recursiva única en módulos, su descomposición modular , que se puede construir a partir del grafo en tiempo lineal ; los algoritmos de descomposición modular tienen aplicaciones en otros algoritmos de grafos, incluido el reconocimiento de grafos de comparabilidad .

Véase también

Notas

  1. ^ El 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