Componente (teoría de grafos)

En teoría de grafos , un componente de un grafo no dirigido es un subgrafo conexo que no forma parte de ningún subgrafo conexo mayor. Los componentes de cualquier grafo dividen sus vértices en conjuntos disjuntos , y son los subgrafos inducidos de esos conjuntos. Un grafo que es conexo tiene exactamente un componente, que consiste en el grafo completo. A los componentes a veces se les llama componentes conexas .

El número de componentes en un grafo dado es un invariante importante y está estrechamente relacionado con los invariantes de matroides , espacios topológicos y matrices . En grafos aleatorios , un fenómeno frecuente es la aparición de un componente gigante , un componente significativamente mayor que los demás; y de un umbral de percolación , una probabilidad de arista por encima de la cual existe un componente gigante y por debajo de la cual no existe.

Los componentes de un grafo se pueden construir en tiempo lineal , y un caso particular 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 aristas en un grafo, en un tiempo reducido por cambio. En la 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 grafo no dirigido dado puede definirse como un subgrafo conexo que no forma parte de ningún subgrafo conexo mayor. Por ejemplo, el grafo que se muestra en la primera ilustración tiene tres componentes. Cada vértice${\displaystyle v}$de un grafo pertenece a uno de los componentes del grafo, que puede encontrarse como el subgrafo inducido del conjunto de vértices alcanzables desde${\displaystyle v}$. ^{[ 1 ]} Todo grafo es la unión disjunta de sus componentes. ^{[ 2 ]} Ejemplos adicionales incluyen los siguientes casos especiales:

• En un grafo vacío , cada vértice forma un componente con un vértice y cero aristas. ^{[ 3 ]} De manera más general, se forma un componente de este tipo para cada vértice aislado en cualquier grafo. ^{[ 4 ]}
• En un grafo conectado , hay exactamente un componente: el grafo completo. ^{[ 4 ]}
• En un bosque , cada componente es un árbol . ^{[ 5 ]}
• En un grafo de clúster , cada componente es una camarilla maximal . Estos grafos pueden generarse como cierres transitivos de grafos no dirigidos arbitrarios, para los cuales encontrar el cierre transitivo es una formulación equivalente a identificar los componentes conexos. ^{[ 6 ]}

Otra definición de componentes involucra las clases de equivalencia de una relación de equivalencia definida en los vértices del grafo. En un grafo no dirigido, un vértice${\displaystyle v}$es alcanzable desde un vértice${\displaystyle u}$si hay un camino desde${\displaystyle u}$a${\displaystyle v}$o , equivalentemente, un recorrido (un camino que permite vértices y aristas repetidos). La alcanzabilidad es una relación de equivalencia, ya que:

• Es reflexivo : existe un camino trivial de longitud cero desde cualquier vértice hasta sí mismo.
• Es simétrico : si hay un camino desde${\displaystyle u}$a${\displaystyle v}$, los mismos bordes en orden inverso forman un camino desde${\displaystyle v}$a${\displaystyle u}$.
• Es transitivo : Si hay un camino desde${\displaystyle u}$a${\displaystyle v}$y un camino desde${\displaystyle v}$a${\displaystyle w}$, los dos caminos pueden concatenarse para formar un paseo desde${\displaystyle u}$a${\displaystyle w}$.

Las clases de equivalencia de esta relación dividen los vértices del grafo en conjuntos disjuntos , subconjuntos de vértices que son todos alcanzables entre sí, sin pares alcanzables adicionales fuera de ninguno de estos subconjuntos. Cada vértice pertenece a exactamente 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 los 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 grafos , incluyendo los componentes débiles ^{[ 9 ]} y los componentes fuertemente conectados de grafos dirigidos ^{[ 10 ]} y los componentes biconectados de grafos no dirigidos. ^{[ 11 ]}

El número de componentes de un grafo finito dado se puede utilizar para contar el número de aristas en sus bosques de expansión : En un grafo con${\displaystyle n}$vértices y${\displaystyle c}$componentes, cada bosque extenso tendrá exactamente${\displaystyle nc}$bordes. Este número${\displaystyle nc}$es el rango teórico de matroides del grafo, y el rango de su matroide gráfico . El rango del matroide cográfico dual es igual al rango de circuito del grafo, el número mínimo de aristas que deben eliminarse del grafo para romper todos sus ciclos. En un grafo con${\displaystyle m}$bordes,${\displaystyle n}$vértices y${\displaystyle c}$componentes, el rango del circuito es${\displaystyle m-n+c}$. ^{[ 12 ]}

Un grafo puede interpretarse como un espacio topológico de múltiples maneras, por ejemplo, colocando sus vértices como puntos en posición general en el espacio euclidiano tridimensional y representando sus aristas como segmentos de línea entre esos puntos. ^{[ 13 ]} Los componentes de un grafo pueden generalizarse a través de estas interpretaciones como los componentes topológicamente conexos del espacio correspondiente; estos son clases de equivalencia de puntos que no pueden separarse mediante pares de conjuntos cerrados disjuntos. Así como el número de componentes conexas de un espacio topológico es un invariante topológico importante, el número de Betti cero , el número de componentes de un grafo es un invariante de grafo importante , y en la teoría topológica de grafos puede interpretarse como el número de Betti cero del grafo. ^{[ 3 ]}

El número de componentes surge también de otras maneras en la teoría de grafos. En la teoría algebraica de grafos, es igual a la multiplicidad de 0 como autovalor de la matriz laplaciana de un grafo finito. ^{[ 14 ]} También es el índice del primer coeficiente no nulo del polinomio cromático del grafo, y el polinomio cromático de todo el grafo se puede obtener como el producto de los polinomios de sus componentes. ^{[ 15 ]} El número de componentes juega un papel clave en el teorema de Tutte sobre emparejamientos perfectos que caracteriza a los grafos finitos que tienen emparejamientos perfectos ^{[ 16 ]} y la fórmula de Tutte-Berge asociada para el tamaño de un emparejamiento máximo , ^{[ 17 ]} y en la definición de la tenacidad del grafo . ^{[ 18 ]}

Es sencillo calcular los componentes de un grafo finito en tiempo lineal (en términos del número de vértices y aristas del grafo) utilizando una búsqueda en anchura o una búsqueda en profundidad . En cualquier caso, una búsqueda que comienza en algún vértice particular${\displaystyle v}$encontrará el componente completo que contiene${\displaystyle v}$(y nada más) antes de regresar. Todos los componentes de un grafo se pueden encontrar recorriendo sus vértices, iniciando una nueva búsqueda en amplitud o en profundidad cada vez que el bucle alcanza un vértice que 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 grafo a partir de la imagen y el análisis de componentes sobre dicho grafo. Los vértices son el subconjunto de píxeles de la imagen, elegidos por ser de interés o por tener mayor probabilidad de formar parte de los objetos representados. Las aristas conectan píxeles adyacentes , con una adyacencia definida ortogonalmente según el vecindario de Von Neumann , o tanto ortogonal como diagonalmente según el vecindario de Moore . La identificación de los componentes conectados de este grafo 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 grafo, lo que permite procesarlo en orden de píxeles en lugar del orden más disperso que se generaría mediante la búsqueda en amplitud o en profundidad. Esto puede ser útil en situaciones donde el acceso secuencial a los píxeles es más eficiente que el acceso aleatorio, ya sea porque la imagen está representada de forma jerárquica, lo 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 grafo a medida que se agregan vértices y aristas, utilizando una estructura de datos de conjuntos disjuntos para realizar un seguimiento de la partición de los vértices en clases de equivalencia, reemplazando cualesquiera dos clases por su unión cuando se agrega una arista que las conecta. Estos algoritmos toman un tiempo amortizado.${\displaystyle O(\alpha (n))}$por operación, donde agregar vértices y aristas y determinar el componente en el que cae un vértice son ambas operaciones, y${\displaystyle \alpha }$ 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 se encuentra en el algoritmo de Kruskal para árboles de expansión mínima , que agrega aristas a un grafo en orden ordenado por longitud e incluye una arista en el árbol de expansión mínima solo cuando conecta dos componentes diferentes del subgrafo previamente agregado. ^{[ 22 ]} Cuando se permiten tanto inserciones como eliminaciones de aristas, los algoritmos de conectividad dinámica aún pueden mantener la misma información, en tiempo amortizado.${\displaystyle O(\log ^{2}n/\log \log n)}$por cambio y tiempo${\displaystyle O(\log n/\log \log n)}$por consulta de conectividad, ^{[ 23 ]} o en un tiempo esperado aleatorio casi logarítmico . ^{[ 24 ]}

Los componentes de los grafos se han utilizado en la teoría de la complejidad computacional para estudiar la potencia 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 solo mediante acceso de lectura en lugar de ser modificable. Los problemas que pueden ser resueltos por máquinas limitadas de esta manera definen la clase de complejidad L. Durante muchos años no estuvo claro si los componentes conectados podían encontrarse en este modelo, cuando se formalizaba como un problema de decisión para comprobar 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 en el espacio logarítmico . ^{[ 25 ]} Finalmente, en 2008 se demostró que este problema de conectividad puede resolverse en el espacio logarítmico y, por lo tanto, que SL = L. ^{[ 26 ]}

En un grafo representado como una lista de adyacencia , con acceso aleatorio a sus vértices, es posible estimar el número de componentes conexas, con probabilidad constante de obtener un error aditivo (absoluto) como máximo${\displaystyle \varepsilon n}$, en tiempo sublineal${\displaystyle O(\varepsilon ^{-2}\log \varepsilon ^{-1})}$. ^{[ 27 ]}

En los grafos aleatorios, los tamaños de los componentes vienen dados por una variable aleatoria que, a su vez, depende del modelo específico de cómo se eligen los grafos aleatorios.${\displaystyle G(n,p)}$versión del modelo Erdős-Rényi-Gilbert , un gráfico sobre${\displaystyle n}$Los vértices se generan eligiendo aleatoria e independientemente para cada par de vértices si se incluye o no una arista que conecte ese par, con probabilidad${\displaystyle p}$de incluir un borde y probabilidad${\displaystyle 1-p}$de dejar esos dos vértices sin una arista que los conecte. ^{[ 28 ]} La conectividad de este modelo depende de${\displaystyle p}$y hay tres rangos diferentes de${\displaystyle p}$con comportamientos muy diferentes 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${\displaystyle n}$El análisis depende de un parámetro${\displaystyle \varepsilon }$, una constante positiva independiente de${\displaystyle n}$que puede ser arbitrariamente cercano a cero.

Subcrítico${\displaystyle p<(1-\varepsilon )/n}$

En este rango de${\displaystyle p}$Todos los componentes son simples y muy pequeños. El componente más grande tiene un tamaño logarítmico. El grafo es un pseudobosque . La mayoría de sus componentes son árboles: el número de vértices en los componentes que tienen ciclos crece más lentamente que cualquier función no acotada del número de vértices. Cada árbol de tamaño fijo aparece linealmente muchas veces. ^{[ 29 ]}

Crítico${\displaystyle p\approx 1/n}$

El componente conectado más grande tiene un número de vértices proporcional a${\displaystyle n^{2/3}}$. Puede haber varios otros componentes grandes; sin embargo, el número total de vértices en componentes que no son árboles es nuevamente proporcional a${\displaystyle n^{2/3}}$. ^{[ 30 ]}

Supercrítico${\displaystyle p>(1+\varepsilon )/n}$

Hay un único componente gigante que contiene un número lineal de vértices. Para valores grandes de${\displaystyle p}$Su tamaño se aproxima a todo el gráfico:${\displaystyle |C_{1}|\approx yn}$dónde${\displaystyle y}$es la solución positiva de la ecuación${\displaystyle e^{-pny}=1-y}$. Los componentes restantes son pequeños, con tamaño logarítmico. ^{[ 31 ]}

En el mismo modelo de grafos aleatorios, existirán múltiples componentes conexas con alta probabilidad para valores de${\displaystyle p}$por debajo de un umbral significativamente más alto,${\displaystyle p<(1-\varepsilon )(\log n)/n}$y un único componente conectado para valores superiores al umbral,${\displaystyle p>(1+\varepsilon )(\log n)/n}$Este fenómeno está estrechamente relacionado con el problema del coleccionista de cupones : para que un grafo aleatorio esté conectado, necesita suficientes aristas para que cada vértice sea incidente a al menos una arista. Más precisamente , si se añaden aristas aleatorias una a una a un grafo, entonces con alta probabilidad la primera arista cuya adición conecta todo el grafo toca el último vértice aislado. ^{[ 32 ]}

Para diferentes modelos, incluidos los subgrafos aleatorios de grafos 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 un componente infinito) y por debajo de la cual no existe. ^{[ 33 ]}

• Código MATLAB para encontrar componentes en grafos no dirigidos , MATLAB File Exchange.
• Componentes conectados , Steven Skiena, El repositorio de algoritmos de Stony Brook