En teoría de grafos , un componente de un grafo no dirigido es un subgrafo inducido en el que dos vértices cualesquiera están conectados entre sí por caminos , y que no está conectado a vértices adicionales en el resto del grafo. Por ejemplo, el gráfico que se muestra en la ilustración tiene tres componentes. Un vértice sin aristas incidentes es en sí mismo un componente. Un gráfico que está conectado tiene exactamente un componente, que consiste en el gráfico completo. Los componentes también se denominan a veces componentes conectados .
Una relación de equivalencia
Una forma alternativa de definir componentes involucra las clases de equivalencia de una relación de equivalencia que se define en los vértices del gráfico. En una gráfica no dirigida, se puede llegar a un vértice v desde un vértice u si hay una ruta de u a v . En esta definición, un solo vértice se cuenta como una ruta de longitud cero, y el mismo vértice puede aparecer más de una vez dentro de una ruta. La accesibilidad es una relación de equivalencia , ya que:
- Es reflexivo : hay un camino trivial de longitud cero desde cualquier vértice hasta sí mismo.
- Es simétrico : si hay un camino de u a v , las mismas aristas forman un camino de v a u .
- Es transitivo : si hay una ruta de u a v y una ruta de v a w , las dos rutas pueden concatenarse para formar una ruta de u a w .
Los componentes son entonces los subgrafos inducidos formados por las clases de equivalencia de esta relación.
El número de componentes
El número de componentes es un invariante topológico importante de un gráfico. En la teoría de grafos topológicos se puede interpretar como el número cero de Betti del grafo. En la teoría de grafos algebraicos, es igual a la multiplicidad de 0 como valor propio de la matriz laplaciana del grafo. También es el índice del primer coeficiente distinto de cero del polinomio cromático de un gráfico. Los números de componentes juegan un papel clave en el teorema de Tutte que caracteriza los gráficos que tienen coincidencias perfectas y en la definición de la tenacidad del gráfico .
Algoritmos
Es sencillo calcular los componentes de un gráfico en tiempo lineal (en términos de los números de los vértices y los bordes del gráfico) utilizando la búsqueda primero en amplitud o la búsqueda en profundidad . En cualquier caso, una búsqueda que comience en algún vértice particular v encontrará el componente completo que contiene v (y no más) antes de regresar. Para encontrar todos los componentes de un gráfico, recorra sus vértices, comenzando una nueva búsqueda de amplitud o profundidad primero siempre que el bucle alcance un vértice que no se haya incluido en un componente encontrado anteriormente. Hopcroft y Tarjan (1973) describen esencialmente este algoritmo y afirman que en ese momento era "bien conocido".
También existen algoritmos eficientes para rastrear dinámicamente los componentes de un gráfico a medida que se agregan vértices y bordes, como una aplicación sencilla de estructuras de datos de conjuntos disjuntos . Estos algoritmos requieren un tiempo amortizado de O ( α ( n )) por operación, donde agregar vértices y aristas y determinar el componente en el que cae un vértice son operaciones, y α ( n ) es una inversa de crecimiento muy lento de la Función de Ackermann . Un problema relacionado es el seguimiento de componentes, ya que todos los bordes se eliminan de un gráfico, uno por uno; existe un algoritmo para resolver esto con tiempo constante por consulta y tiempo O (| V || E |) para mantener la estructura de datos; este es un costo amortizado de O (| V |) por eliminación de borde. Para los bosques , el costo se puede reducir a O ( q + | V | log | V |), o O (log | V |) costo amortizado por eliminación de borde ( Shiloach & Even 1981 ).
Los investigadores también han estudiado algoritmos para encontrar componentes en modelos de cálculo más limitados, como programas en los que la memoria de trabajo está limitada a un número logarítmico de bits (definido por la clase de complejidad L ). Lewis y Papadimitriou (1982) preguntaron si es posible probar en el espacio logs si dos vértices pertenecen al mismo componente de un grafo no dirigido, y definieron una clase de complejidad SL de problemas logspace equivalente a la conectividad. Finalmente Reingold (2008) logró encontrar un algoritmo para resolver este problema de conectividad en el espacio logarítmico, mostrando que L = SL.
Componentes en gráficos aleatorios
En los gráficos aleatorios, los tamaños de los componentes vienen dados por una variable aleatoria que, a su vez, depende del modelo específico.
La El modelo tiene tres regiones con un comportamiento aparentemente diferente:
Subcrítico : Todos los componentes son simples y muy pequeños, el componente más grande tiene un tamaño ;
Crítico : ;
Supercrítico : dónde es la solución positiva de la ecuación
dónde y son respectivamente los componentes más grandes y los segundos más grandes. Todos los demás componentes tienen sus tamaños del pedido.
Ver también
- Componente gigante
- Componente fuertemente conectado , un concepto relacionado para gráficos dirigidos
- Componente biconectado
- Descomposición modular , para una adecuada generalización de componentes en gráficos no dirigidos
- Etiquetado de componentes conectados , una técnica básica en el análisis de imágenes por computadora basada en componentes de gráficos
- Teoría de la filtración , una teoría que describe el comportamiento de los componentes en subgráficos aleatorios de gráficos de cuadrícula.
- Centralidad
- Puente (teoría de grafos)
Referencias
- Hopcroft, J .; Tarjan, R. (1973), "Algoritmo 447: algoritmos eficientes para la manipulación de gráficos", Comunicaciones del ACM , 16 (6): 372–378, doi : 10.1145 / 362248.362272
- Lewis, Harry R .; Papadimitriou, Christos H. (1982), "Computación simétrica delimitada por el espacio", Informática teórica , 19 (2): 161-187, doi : 10.1016 / 0304-3975 (82) 90058-5
- Reingold, Omer (2008), "Conectividad no dirigida en el espacio de registro", Journal of the ACM , 55 (4): Artículo 17, 24 páginas, doi : 10.1145 / 1391289.1391291
- Shiloach, Yossi; Incluso, Shimon (1981), "Un problema de eliminación de bordes en línea", Journal of the ACM , 28 (1): 1–4, doi : 10.1145 / 322234.322235
enlaces externos
- Código MATLAB para encontrar componentes en gráficos no dirigidos , MATLAB File Exchange.
- Componentes conectados , Steven Skiena, The Stony Brook Algorithm Repository