Componente (teoría de grafos)

En la teoría de grafos, un componente de un gráfico no dirigido es un subgrafo conexo que no forma parte de ningún subgrafo conexo mayor. Los componentes de cualquier gráfico dividen sus vértices en conjuntos disjuntos y son los subgráficos inducidos de esos conjuntos. Un grafo que a su vez es conexo tiene exactamente un componente, que consiste en el grafo completo. Los componentes a veces se denominan componentes conectados.

El número de componentes en un gráfico dado es un gráfico invariante importante y está estrechamente relacionado con los invariantes de matroides, espacios topológicos y matrices. En 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 de borde 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 la teoría de la complejidad computacional, los componentes conectados se han utilizado para estudiar algoritmos con una complejidad espacial limitada, y los algoritmos de tiempo sublineal pueden estimar con precisión el número de componentes.

Definiciones y ejemplos

Un componente de un gráfico no dirigido dado puede definirse como un subgrafo conexo que no forma parte de ningún subgrafo conexo más grande. Por ejemplo, el gráfico que se muestra en la primera ilustración tiene tres componentes. Cada vértice de un grafo pertenece a uno de los componentes del grafo, que se puede encontrar como el subgrafo inducido del conjunto de vértices alcanzable desde . Todo grafo es la unión disjunta de sus componentes. Ejemplos adicionales incluyen los siguientes casos especiales:

• En un gráfico vacío, cada vértice forma un componente con un vértice y cero aristas. Más generalmente, se forma un componente de este tipo para cada vértice aislado en cualquier gráfico.
• En un gráfico conexo, hay exactamente un componente: el gráfico completo.
• En un bosque, cada componente es un árbol.
• En un gráfico de conglomerados, cada componente es una camarilla máxima. Estos gráficos se pueden producir como cierres transitivos de gráficos no dirigidos arbitrarios, para los cuales encontrar el cierre transitivo es una formulación equivalente a identificar los componentes conectados.

Otra definición de componentes implica las clases de equivalencia de una relación de equivalencia definida en los vértices del gráfico. En un grafo no dirigido, se puede llegar a un vértice desde un vértice si hay un camino desde hasta, o de manera equivalente, un paseo (un camino que permite vértices y aristas repetidos). La alcanzabilidad es una relación de equivalencia, ya que:

• Es reflexivo: hay un camino trivial de longitud cero desde cualquier vértice a sí mismo.
• Es simétrico: si hay un camino desde hasta, los mismos bordes en el orden inverso forman un camino desde hasta.
• Es transitivo: si hay un camino de a y un camino de a, los dos caminos pueden concatenarse para formar un camino de a.

Las clases de equivalencia de esta relación dividen los vértices del gráfico en conjuntos disjuntos, subconjuntos de vértices que son todos alcanzables entre sí, sin pares alcanzables adicionales 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. Alternativamente, algunas fuentes definen los componentes como los conjuntos de vértices en lugar de los subgrafos que inducen.

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 y los componentes fuertemente conectados de gráficos dirigidos y los componentes biconectados de gráficos no dirigidos.

Número de componentes

El número de componentes de un grafo finito dado se puede usar para contar el número de aristas en sus bosques expansivos: en un grafo con vértices y componentes, cada bosque expansivo tendrá aristas exactas. 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 deben eliminarse del gráfico para romper todos sus ciclos. En un gráfico con aristas, vértices y componentes, el rango del circuito es .

Un gráfico puede interpretarse como un espacio topológico de múltiples maneras, por ejemplo, colocando sus vértices como puntos en una posición general en un espacio euclidiano tridimensional y representando sus bordes como segmentos de línea entre esos puntos. Los componentes de un gráfico se pueden generalizar a través de estas interpretaciones como los componentes topológicos conectados del espacio correspondiente; estas 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 de Betti cero, el número de componentes de un gráfico es un invariante de gráfico importante, y en la teoría de grafos topológicos puede interpretarse como el número de Betti cero de la gráfica.

El número de componentes también surge de otras maneras 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. 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 el producto de los polinomios de sus componentes. Los números de componentes juegan un papel clave en el teorema de Tutte que caracteriza los gráficos finitos que tienen coincidencias perfectas y la fórmula asociada de Tutte-Berge para el tamaño de una coincidencia máxima, y ​​en la definición de la dureza del gráfico.

Algoritmos

Es sencillo calcular los componentes de un gráfico finito 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 primero en profundidad. En cualquier caso, una búsqueda que comience en algún vértice en particular encontrará el componente completo que contiene (y no más) antes de regresar. Todos los componentes de un gráfico se pueden encontrar recorriendo sus vértices, iniciando una nueva búsqueda primero en anchura o en profundidad siempre que el bucle alcance un vértice que aún no se haya incluido en un componente encontrado previamente. Hopcroft y Tarjan (1973) describen esencialmente este algoritmo y afirman que ya era "bien conocido".

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 ser parte de los objetos representados. Los bordes conectan píxeles adyacentes, con adyacencia definida ortogonalmente según la vecindad de Von Neumann, o ortogonal y diagonalmente según la vecindad de Moore. La identificación de 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 que se procese en orden de píxeles en lugar de en el orden más disperso que se generaría mediante la búsqueda primero en anchura o en profundidad. Esto puede ser útil en situaciones en las que el acceso secuencial a los píxeles es más eficaz 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.

También existen algoritmos eficientes para realizar un seguimiento dinámico de los componentes de un gráfico a medida que se agregan vértices y aristas, mediante el uso de una estructura de datos de conjunto disjunto 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 un se agrega el borde que los conecta. Estos algoritmos toman tiempo amortizado por operación, donde agregar vértices y bordes y determinar el componente en el que cae un vértice son ambas operaciones, y es un inverso de crecimiento muy lento de la función de Ackermann de crecimiento muy rápido.Una aplicación de este tipo de algoritmo de conectividad incremental se encuentra en el algoritmo de Kruskal para árboles de expansión mínimos, que agrega bordes a un gráfico ordenados por longitud e incluye un borde en el árbol de expansión mínimo solo cuando conecta dos componentes diferentes de los agregados previamente. subgrafo 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, o en tiempo esperado aleatorio casi logarítmico.

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 más grande accesible solo a través del 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 se podían encontrar componentes conectados en este modelo, cuando se formaliza 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.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.

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 error aditivo (absoluto) como máximo , en tiempo sublineal .

En gráficos aleatorios

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 de 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 incluir 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. La conectividad de este modelo depende de , y existen tres gamas diferentes decon un comportamiento muy diferente entre sí. En el análisis a continuación, 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 de la que puede ser arbitrariamente cercana a cero.subcríticoEn esta gama de , todos los componentes son simples y muy pequeños. El componente más grande tiene 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 ilimitada del número de vértices. Cada árbol de tamaño fijo ocurre linealmente muchas veces.CríticoEl componente conexo más grande tiene un número de vértices proporcional a . Puede haber varios otros componentes grandes; sin embargo, el número total de vértices en los componentes que no son de árbol es nuevamente proporcional a .SupercríticoHay un solo componente gigante que contiene un número lineal de vértices. Para valores grandes de su tamaño se aproxima a la gráfica completa: donde es la solución positiva de la ecuación . Los componentes restantes son pequeños, con tamaño logarítmico.

En el mismo modelo de grafos aleatorios existirán múltiples componentes conectadas con alta probabilidad para valores por debajo de un umbral significativamente mayor , y una única componente conectada para valores por encima del umbral, . Este fenómeno está estrechamente relacionado con el problema del coleccionista de cupones: para estar conectado, un grafo aleatorio necesita suficientes aristas para que cada vértice incida en al menos una arista. Más precisamente, si los bordes aleatorios se agregan uno por uno a un gráfico, entonces con alta probabilidad el primer borde cuya suma conecta todo el gráfico toca el último vértice aislado.

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 una componente gigante (o componente infinita) y por debajo de la cual no.