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:

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

  1. ↑ Infierno, 1978 .
  2. ↑ Sedlaceck, 1983 .
  3. ↑ Wigderson, 1983 .
  4. ↑ Hartsfeld, Ringel, 1991 .
  5. ↑ Larrión, Neumann-Lara, Pizaña, 2002 .
  6. ↑ Malnic, Mohar, 1992 .
  7. ↑ Seress, Szabo, 1995 .

Literatura