En teoría de grafos , un componente de un gráfico no dirigido es un subgrafo conectado que no forma parte de ningún subgrafo conectado más grande. Los componentes de cualquier gráfico dividen sus vértices en conjuntos disjuntos y son los subgrafos inducidos de esos conjuntos. Un gráfico que a su vez es conexo tiene exactamente un componente, que consta de todo el gráfico. Los componentes a veces se denominan componentes conectados .
El número de componentes en un gráfico dado es un invariante gráfico importante y está estrechamente relacionado con los invariantes de matroides , espacios topológicos y matrices . En los gráficos aleatorios , un fenómeno que ocurre con frecuencia es la incidencia de un componente gigante , un componente que es significativamente más grande que los demás; y de un umbral de percolación , una probabilidad límite por encima del cual existe un componente gigante y por debajo del cual no.
Los componentes de un gráfico se pueden construir en tiempo lineal , y un caso especial del problema, el etiquetado de componentes conectados , es una técnica básica en el análisis de imágenes . Los algoritmos de conectividad dinámica mantienen los componentes a medida que se insertan o eliminan bordes en un gráfico, en poco tiempo por cambio. En teoría de la complejidad computacional , los componentes conectados se han utilizado para estudiar algoritmos con complejidad espacial limitada , y los algoritmos de tiempo sublineal pueden estimar con precisión el número de componentes.
Un componente de un gráfico no dirigido dado puede definirse como un subgrafo conectado que no forma parte de ningún subgrafo conectado más grande. Por ejemplo, el gráfico que se muestra en la primera ilustración tiene tres componentes. Cada vértice de un gráfico pertenece a uno de los componentes del gráfico, que puede encontrarse como el subgrafo inducido del conjunto de vértices alcanzables desde . [1] Todo grafo es la unión disjunta de sus componentes. [2] Ejemplos adicionales incluyen los siguientes casos especiales:
Otra definición de componentes involucra las clases de equivalencia de una relación de equivalencia definida en los vértices del gráfico. En un gráfico no dirigido, se puede llegar a un vértice desde un vértice si hay un camino desde hasta , o equivalentemente un paseo (un camino que permite vértices y aristas repetidos). La accesibilidad es una relación de equivalencia, ya que:
Las clases de equivalencia de esta relación dividen los vértices del gráfico en conjuntos disjuntos , subconjuntos de vértices a los que se puede acceder entre sí, sin pares adicionales alcanzables fuera de cualquiera de estos subconjuntos. Cada vértice pertenece exactamente a una clase de equivalencia. Los componentes son entonces los subgrafos inducidos formados por cada una de estas clases de equivalencia. [7] Alternativamente, algunas fuentes definen los componentes como conjuntos de vértices en lugar de como los subgrafos que inducen. [8]
Se han utilizado definiciones similares que involucran clases de equivalencia para definir componentes para otras formas de conectividad de gráficos , incluidos los componentes débiles [9] y los componentes fuertemente conectados de gráficos dirigidos [10] y los componentes biconectados de gráficos no dirigidos. [11]
El número de componentes de un gráfico finito dado se puede utilizar para contar el número de aristas en sus bosques que se extienden : en un gráfico con vértices y componentes, cada bosque que se extiende tendrá exactamente aristas. Este número es el rango teórico matroide del gráfico y el rango de su matroide gráfico . El rango de la matroide cográfica dual es igual al rango del circuito del gráfico, el número mínimo de aristas que se deben eliminar del gráfico para romper todos sus ciclos. En un gráfico con aristas, vértices y componentes, el rango del circuito es . [12]
Un gráfico se puede interpretar como un espacio topológico de múltiples maneras, por ejemplo, colocando sus vértices como puntos en posición general en un espacio euclidiano tridimensional y representando sus aristas como segmentos de línea entre esos puntos. [13] Los componentes de un gráfico se pueden generalizar a través de estas interpretaciones como los componentes topológicos conectados del espacio correspondiente; éstas son clases de equivalencia de puntos que no pueden separarse por pares de conjuntos cerrados disjuntos. Así como el número de componentes conectados de un espacio topológico es un invariante topológico importante , el número cero de Betti , el número de componentes de un gráfico es un invariante importante del gráfico , y en teoría de grafos topológicos puede interpretarse como el número cero de Betti de la gráfica. [3]
El número de componentes también surge de otras formas en la teoría de grafos. En teoría algebraica de grafos, es igual a la multiplicidad de 0 como valor propio de la matriz laplaciana de un grafo finito. [14] También es el índice del primer coeficiente distinto de cero del polinomio cromático del gráfico, y el polinomio cromático de todo el gráfico se puede obtener como producto de los polinomios de sus componentes. [15] Los números de componentes juegan un papel clave en el teorema de Tutte que caracteriza a los gráficos finitos que tienen coincidencias perfectas [16] y la fórmula asociada de Tutte-Berge para el tamaño de una coincidencia máxima , [17] y en la definición de dureza del gráfico . [18]
Es sencillo calcular los componentes de un gráfico finito en tiempo lineal (en términos de los números de vértices y aristas del gráfico) utilizando una búsqueda en amplitud o en profundidad . En cualquier caso, una búsqueda que comienza en algún vértice en particular encontrará el componente completo que contiene (y nada más) antes de regresar. Todos los componentes de un gráfico se pueden encontrar recorriendo sus vértices, iniciando una nueva búsqueda en anchura o en profundidad cada vez que el bucle llega a un vértice que aún no se ha incluido en un componente encontrado previamente. Hopcroft y Tarjan (1973) describen esencialmente este algoritmo y afirman que ya era "bien conocido". [19]
El etiquetado de componentes conectados , una técnica básica en el análisis de imágenes por computadora , implica la construcción de un gráfico a partir de la imagen y el análisis de componentes en el gráfico. Los vértices son el subconjunto de los píxeles de la imagen, elegidos como de interés o como probables de formar parte de los objetos representados. Los bordes conectan píxeles adyacentes , con adyacencia definida ortogonalmente según la vecindad de Von Neumann , o tanto ortogonal como diagonalmente según la vecindad de Moore . Identificar los componentes conectados de este gráfico permite un procesamiento adicional para encontrar más estructura en esas partes de la imagen o identificar qué tipo de objeto se representa. Los investigadores han desarrollado algoritmos de búsqueda de componentes especializados para este tipo de gráfico, lo que permite procesarlo en el orden de los píxeles en lugar del orden más disperso que se generaría con la búsqueda primero en amplitud o primero en profundidad. Esto puede resultar útil en situaciones en las que el acceso secuencial a los píxeles es más eficiente que el acceso aleatorio, ya sea porque la imagen se representa de forma jerárquica que no permite un acceso aleatorio rápido o porque el acceso secuencial produce mejores patrones de acceso a la memoria . [20]
También existen algoritmos eficientes para rastrear dinámicamente los componentes de un gráfico a medida que se agregan vértices y aristas, mediante el uso de una estructura de datos de conjuntos disjuntos para realizar un seguimiento de la partición de los vértices en clases de equivalencia, reemplazando dos clases cualesquiera por su unión cuando una Se agrega el borde que los conecta. Estos algoritmos toman tiempo amortizado por operación, donde sumar vértices y aristas y determinar el componente en el que cae un vértice son ambas operaciones, y es una inversa de crecimiento muy lento de la función de Ackermann de crecimiento muy rápido . [21] Una aplicación de este tipo de algoritmo de conectividad incremental es el algoritmo de Kruskal para árboles de expansión mínima , que agrega aristas a un gráfico ordenado por longitud e incluye una arista en el árbol de expansión mínima solo cuando conecta dos componentes diferentes del subgrafo agregado previamente. [22] Cuando se permiten tanto las inserciones como las eliminaciones de bordes, los algoritmos de conectividad dinámica aún pueden mantener la misma información, en tiempo amortizado por cambio y tiempo por consulta de conectividad, [23] o en tiempo esperado aleatorio casi logarítmico . [24]
Los componentes de los gráficos se han utilizado en la teoría de la complejidad computacional para estudiar el poder de las máquinas de Turing que tienen una memoria de trabajo limitada a un número logarítmico de bits, con una entrada mucho mayor accesible sólo mediante acceso de lectura en lugar de ser modificable. Los problemas que pueden resolver las máquinas así limitadas definen la clase de complejidad L. Durante muchos años no estuvo claro si se podían encontrar componentes conectados en este modelo, cuando se formalizó como un problema de decisión de probar si dos vértices pertenecen al mismo componente, y en 1982 se definió una clase de complejidad relacionada, SL , para incluir este problema de conectividad. y cualquier otro problema equivalente bajo reducciones de espacio logarítmico . [25] Finalmente se demostró en 2008 que este problema de conectividad se puede resolver en el espacio logarítmico, y por lo tanto que SL = L. [26]
En un gráfico representado como una lista de adyacencia , con acceso aleatorio a sus vértices, es posible estimar el número de componentes conectados, con probabilidad constante de obtener error aditivo (absoluto) como máximo , en tiempo sublineal . [27]
En los gráficos aleatorios, los tamaños de los componentes están dados por una variable aleatoria , que, a su vez, depende del modelo específico de cómo se eligen los gráficos aleatorios. En la versión del modelo Erdős-Rényi-Gilbert , se genera un gráfico de vértices eligiendo de forma aleatoria e independiente para cada par de vértices si se incluye una arista que conecte ese par, con probabilidad de incluir una arista y probabilidad de dejar esos dos vértices. sin un borde que los conecte. [28] La conectividad de este modelo depende de , y existen tres gamas diferentes de con comportamiento muy diferente entre sí. En el análisis siguiente, todos los resultados ocurren con alta probabilidad , lo que significa que la probabilidad del resultado es arbitrariamente cercana a uno para valores suficientemente grandes de . El análisis depende de un parámetro , una constante positiva independiente del mismo que puede estar arbitrariamente cercana a cero.
En el mismo modelo de gráficos aleatorios, existirán múltiples componentes conectados con alta probabilidad para valores por debajo de un umbral significativamente más alto, y un único componente conectado para valores por encima del umbral . Este fenómeno está estrechamente relacionado con el problema del recolector de cupones : para estar conectado, un gráfico aleatorio necesita suficientes aristas para que cada vértice incida en al menos una arista. Más precisamente, si se agregan aristas aleatorias una por una a un gráfico, entonces con alta probabilidad la primera arista cuya suma conecta todo el gráfico toca el último vértice aislado. [32]
Para diferentes modelos, incluidos los subgrafos aleatorios de los gráficos de cuadrícula, los componentes conectados se describen mediante la teoría de la percolación . Una cuestión clave en esta teoría es la existencia de un umbral de percolación , una probabilidad crítica por encima de la cual existe un componente gigante (o componente infinito) y por debajo de la cual no. [33]