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 en sí mismo conexo tiene exactamente un componente, que consiste en todo el grafo. Los componentes a veces se denominan componentes conexos .

El número de componentes en un grafo dado es un invariante gráfico importante y está estrechamente relacionado con los invariantes de matroides , espacios topológicos y matrices . En grafos 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 otros; y de un umbral de percolación , una probabilidad de borde por encima de la 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 aristas 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 complejidad espacial limitada , y los algoritmos de tiempo sublineal pueden estimar con precisión el número de componentes.

Definiciones y ejemplos

Un gráfico de clúster con siete 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 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 . ^[1] Cada grafo es la unión disjunta de sus componentes. ^[2] Otros ejemplos incluyen los siguientes casos especiales: ${\estilo de visualización v}$ ${\estilo de visualización v}$

En un gráfico 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 gráfico. ^[4]
En un gráfico conexo , hay exactamente un componente: el gráfico completo. ^[4]
En un bosque , cada componente es un árbol . ^[5]
En un grafo de conglomerados , cada componente es una camarilla máxima . Estos grafos pueden generarse como clausuras transitivas de grafos arbitrarios no dirigidos, para los cuales encontrar la clausura transitiva es una formulación equivalente de la identificación de los componentes conectados. ^[6]

Otra definición de componentes implica 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 ${\estilo de visualización v}$ es alcanzable desde un vértice ${\estilo de visualización u}$ si existe un camino desde hasta o , equivalentemente, un camino (un camino que permite vértices y aristas repetidos). La alcanzabilidad es una relación de equivalencia, ya que: ${\estilo de visualización u}$ ${\estilo de visualización v}$

Es reflexivo : existe un camino trivial de longitud cero desde cualquier vértice hasta sí mismo.
Es simétrico : si hay un camino de a , los mismos bordes en el orden inverso forman un camino de a . ${\estilo de visualización u}$ ${\estilo de visualización v}$ ${\estilo de visualización v}$ ${\estilo de visualización u}$
Es transitivo : si hay un camino de a y un camino de a , los dos caminos se pueden concatenar entre sí para formar un camino de a . ${\estilo de visualización u}$ ${\estilo de visualización v}$ ${\estilo de visualización v}$ ${\estilo de visualización w}$ ${\estilo de visualización u}$ ${\estilo de visualización w}$

Las clases de equivalencia de esta relación dividen los vértices del grafo en conjuntos disjuntos , subconjuntos de vértices que son 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. ^[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 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]

Número de componentes

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 vértices y componentes, cada bosque de expansión tendrá exactamente aristas. Este número es el rango matroide -teórico 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 se deben eliminar del grafo para romper todos sus ciclos. En un grafo con aristas, vértices y componentes, el rango de circuito es . ^[12] ${\estilo de visualización n}$ ${\estilo de visualización c}$ ${\estilo de visualización nc}$ ${\estilo de visualización nc}$ ${\estilo de visualización m}$ ${\estilo de visualización n}$ ${\estilo de visualización c}$ $m-n+c$

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ógicos conexos 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 conexos 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 de grafos topológicos puede interpretarse como el número de Betti cero del grafo. ^[3]

El número de componentes también surge de otras maneras en la teoría de grafos. En la teoría de grafos algebraicos 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 grafo, y el polinomio cromático de todo el grafo se puede obtener como el 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 grafos finitos que tienen emparejamientos perfectos ^[16] y la fórmula asociada de Tutte-Berge para el tamaño de un emparejamiento máximo , ^[17] y en la definición de tenacidad de grafos . ^[18]

Algoritmos

Es sencillo calcular los componentes de un grafo finito en tiempo lineal (en términos de los números de vértices y aristas del grafo) utilizando una búsqueda en amplitud o una búsqueda en profundidad . En cualquier caso, una búsqueda que comienza en un vértice ${\estilo de visualización v}$ particular encontrará el componente completo que contiene ${\estilo de visualización v}$ (y no más) antes de regresar. Todos los componentes de un grafo se pueden encontrar haciendo un bucle a través de sus vértices, iniciando una nueva búsqueda en amplitud o en profundidad cada vez que el bucle llega a un vértice que no se ha incluido ya 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 ser parte de los objetos representados. Los bordes conectan píxeles adyacentes , con adyacencia definida ortogonalmente de acuerdo con el vecindario de Von Neumann , o tanto ortogonalmente como diagonalmente de acuerdo con el vecindario 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 orden de píxeles en lugar de en el orden más disperso que se generaría mediante una búsqueda en amplitud o en profundidad. Esto puede ser ú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 está representada de una manera 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, utilizando 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 se agrega una arista que las conecta. Estos algoritmos toman tiempo amortizado por operación, donde agregar 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 está en el algoritmo de Kruskal para árboles de expansión mínima , que agrega aristas a un gráfico en orden ordenado por longitud e incluye una arista en el árbol de expansión mínima solo cuando conecta dos componentes diferentes del subgráfico 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] $O(\alpha (n))$ ${\estilo de visualización \alpha}$ $O(\log ^{2}n/\log \log n)$ $O(\log n/\log \log n)$

Los componentes de 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 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 los componentes conectados podrían encontrarse en este modelo, cuando se formaliza como un problema de decisión para 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 a él bajo reducciones del espacio logarítmico . ^[25] Finalmente se demostró en 2008 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 conexos, con probabilidad constante de obtener un error aditivo (absoluto) como máximo , en tiempo sublineal . ^[27] $\varepsilon n$ $O(\varepsilon ^{-2}\log \varepsilon ^{-1})$

En gráficos aleatorios

En los grafos 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 grafos aleatorios. En la versión del modelo Erdős–Rényi–Gilbert , un grafo sobre vértices se genera eligiendo aleatoriamente e independientemente para cada par de vértices si se incluye una arista que conecta ese par, con probabilidad de incluir una arista y probabilidad de dejar esos dos vértices sin una arista que los conecte. ^[28] La conectividad de este modelo depende de , y hay tres rangos diferentes de con 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 que puede ser arbitrariamente cercana a cero. $G(n,p)$ ${\estilo de visualización n}$ ${\estilo de visualización p}$ ${\estilo de visualización 1-p}$ ${\estilo de visualización p}$ ${\estilo de visualización p}$ ${\estilo de visualización n}$ ${\estilo de visualización \varepsilon}$ ${\estilo de visualización n}$

Subcrítico $p<(1-\varepsilon )/n$: En este rango de , todos los componentes son simples y muy pequeños. El componente más grande tiene un tamaño logarítmico. El gráfico 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 ocurre linealmente muchas veces. ^[29] ${\estilo de visualización p}$
Crítico $p\aprox 1/n$: El componente conectado 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 componentes que no son árboles es nuevamente proporcional a . ^[30] ${\estilo de visualización n^{2/3}}$ ${\estilo de visualización n^{2/3}}$
Supercrítico $p>(1+\varepsilon )/n$: Hay un único componente gigante que contiene un número lineal de vértices. Para valores grandes de su tamaño se aproxima a todo el grafo: donde es la solución positiva de la ecuación . Los componentes restantes son pequeños, con tamaño logarítmico. ^[31] ${\estilo de visualización p}$ $|C_{1}|\aproximadamente yn$ ${\estilo de visualización y}$ $e^{-pny}=1-y$

En el mismo modelo de grafos aleatorios, existirán múltiples componentes conectados con alta probabilidad para valores de 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 ser conectado, un grafo 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 grafo, entonces con alta probabilidad la primera arista cuya adición conecta todo el grafo toca el último vértice aislado. ^[32] ${\estilo de visualización p}$ $p<(1-\varepsilon )(\log n)/n$ $p>(1+\varepsilon )(\log n)/n$

En los distintos modelos, incluidos los subgrafos aleatorios de los 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]

Referencias

^ Clark, John; Holton, Derek Allan (1995), Una primera mirada a la teoría de grafos, Allied Publishers, pág. 28, ISBN 9788170234630, archivado desde el original el 8 de enero de 2022 , consultado el 7 de enero de 2022
^ Joyner, David; Nguyen, Minh Van; Phillips, David (10 de mayo de 2013), "1.6.1 Unión, intersección y unión", Algorithmic Graph Theory and Sage (edición 0.8-r1991), Google, pp. 34–35, archivado desde el original el 16 de enero de 2016 , consultado el 8 de enero de 2022
^ ab Tutte, WT (1984), Teoría de grafos, Enciclopedia de matemáticas y sus aplicaciones, vol. 21, Reading, Massachusetts: Addison-Wesley, pág. 15, ISBN 0-201-13520-5, MR 0746795, archivado desde el original el 7 de enero de 2022 , consultado el 7 de enero de 2022
^ ab Thulasiraman, K.; Swamy, MNS (2011), Gráficos: teoría y algoritmos, John Wiley & Sons, pág. 9, ISBN 978-1-118-03025-7, archivado desde el original el 7 de enero de 2022 , consultado el 7 de enero de 2022
^ Bollobás, Béla (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas, vol. 184, Nueva York: Springer-Verlag, p. 6, doi :10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR 1633290, archivado desde el original el 8 de enero de 2022 , consultado el 8 de enero de 2022
^ McColl, WF; Noshita, K. (1986), "Sobre el número de aristas en el cierre transitivo de un grafo", Discrete Applied Mathematics , 15 (1): 67–73, doi :10.1016/0166-218X(86)90020-X, MR 0856101
^ Foldes, Stephan (2011), Estructuras fundamentales del álgebra y las matemáticas discretas, John Wiley & Sons, pág. 199, ISBN 978-1-118-03143-8, archivado desde el original el 7 de enero de 2022 , consultado el 7 de enero de 2022
^ Siek, Jeremy; Lee, Lie-Quan; Lumsdaine, Andrew (2001), "7.1 Componentes conectados: definiciones", The Boost Graph Library: Guía del usuario y manual de referencia , Addison-Wesley, págs. 97-98
^ Knuth, Donald E. (15 de enero de 2022), "Componentes débiles", The Art of Computer Programming, Volumen 4, Prefascículo 12A: Componentes y recorrido (PDF) , pp. 11–14, archivado (PDF) del original el 18 de enero de 2022 , consultado el 1 de marzo de 2022
^ Lewis, Harry ; Zax, Rachel (2019), Matemáticas discretas esenciales para la informática, Princeton University Press, pág. 145, ISBN 978-0-691-19061-7, archivado desde el original el 8 de enero de 2022 , consultado el 8 de enero de 2022
^ Kozen, Dexter C. (1992), "4.1 Componentes biconectados", El diseño y análisis de algoritmos , Textos y monografías en informática, Nueva York: Springer-Verlag, pp. 20-22, doi :10.1007/978-1-4612-4400-4, ISBN 0-387-97687-6, MR 1139767, S2CID 27747202, archivado desde el original el 8 de enero de 2022 , consultado el 8 de enero de 2022
^ Wilson, RJ (1973), "Una introducción a la teoría de matroides", The American Mathematical Monthly , 80 (5): 500–525, doi :10.1080/00029890.1973.11993318, JSTOR 2319608, MR 0371694
^ Wood, David R. (2014), "Dibujo de gráficos tridimensionales", en Kao, Ming-Yang (ed.), Enciclopedia de algoritmos (PDF) , Springer, págs. 1–7, doi :10.1007/978-3-642-27848-8_656-1, ISBN 978-3-642-27848-8, archivado (PDF) del original el 8 de enero de 2022 , consultado el 8 de enero de 2022
^ Cioabă, Sebastian M. (2011), "Algunas aplicaciones de los valores propios de los grafos", en Dehmer, Matthias (ed.), Structural Analysis of Complex Networks , Nueva York: Birkhäuser/Springer, pp. 357–379, doi :10.1007/978-0-8176-4789-6_14, ISBN 978-0-8176-4788-9, Sr. 2777924; ver prueba del Lema 5, p. 361 Archivado el 8 de enero de 2022 en Wayback Machine.
^ Read, Ronald C. (1968), "Introducción a los polinomios cromáticos", Journal of Combinatorial Theory , 4 : 52–71, doi : 10.1016/S0021-9800(68)80087-0 , MR 0224505; véase el teorema 2, pág. 59, y el corolario, pág. 65
^ Tutte, WT (1947), "La factorización de gráficos lineales", The Journal of the London Mathematical Society , 22 (2): 107–111, doi :10.1112/jlms/s1-22.2.107, MR 0023048
^ Berge, Claude (1958), "Sur le couplage maxime d'un graphe", Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences , 247 : 258–259, SEÑOR 0100850
^ Chvátal, Václav (1973), "Gráficos difíciles y circuitos hamiltonianos", Matemáticas discretas , 5 (3): 215–228, doi : 10.1016/0012-365X(73)90138-6 , MR 0316301
^ Hopcroft, John ; Tarjan, Robert (junio de 1973), "Algoritmo 447: algoritmos eficientes para la manipulación de gráficos", Communications of the ACM , 16 (6): 372–378, doi : 10.1145/362248.362272 , S2CID 14772567
^ Dillencourt, Michael B.; Samet, Hanan ; Tamminen, Markku (1992), "Un enfoque general para el etiquetado de componentes conectados para representaciones de imágenes arbitrarias", Journal of the ACM , 39 (2): 253–280, CiteSeerX 10.1.1.73.8846 , doi :10.1145/128749.128750, MR 1160258, S2CID 1869184
^ Bengelloun, Safwan Abdelmajid (diciembre de 1982), Aspectos de la computación incremental (tesis doctoral), Universidad de Yale, p. 12, ProQuest 303248045
^ Skiena, Steven (2008), "6.1.2 Algoritmo de Kruskal", Manual de diseño de algoritmos , Springer, págs. 196-198, Bibcode :2008adm..book.....S, doi :10.1007/978-1-84800-070-4, ISBN 978-1-84800-069-8, archivado desde el original el 7 de enero de 2022 , consultado el 7 de enero de 2022
^ Wulff-Nilsen, Christian (2013), "Conectividad gráfica completamente dinámica y determinista más rápida", en Khanna, Sanjeev (ed.), Actas del vigésimo cuarto simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2013, Nueva Orleans, Luisiana, EE. UU., 6-8 de enero de 2013 , págs. 1757-1769, arXiv : 1209.5608 , doi : 10.1137/1.9781611973105.126, ISBN 978-1-61197-251-1, Número de identificación del sujeto 13397958
^ Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth (2017), "Conectividad completamente dinámica en tiempo esperado amortizado", en Klein, Philip N. (ed.), Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2017, Barcelona, España, Hotel Porta Fira, 16-19 de enero , págs. 510–520, arXiv : 1609.05867 , doi : 10.1137/1.9781611974782.32, S2CID 15585534 $O{\bigl (}\log n(\log \log n)^{2}{\bigr )}$
^ Lewis, Harry R. ; Papadimitriou, Christos H. (1982), "Computación simétrica limitada en el espacio", Theoretical Computer Science , 19 (2): 161–187, doi : 10.1016/0304-3975(82)90058-5 , MR 0666539
^ Reingold, Omer (2008), "Conectividad no dirigida en el espacio logarítmico", Journal of the ACM , 55 (4): A17:1–A17:24, doi :10.1145/1391289.1391291, MR 2445014, S2CID 207168478
^ Berenbrink, Petra; Krayenhoff, Bruce; Mallmann-Trenn, Frederik (2014), "Estimación del número de componentes conectados en tiempo sublineal", Information Processing Letters , 114 (11): 639–642, doi :10.1016/j.ipl.2014.05.008, MR 3230913
^ Frieze, Alan ; Karoński, Michał (2016), "1.1 Modelos y relaciones", Introducción a los gráficos aleatorios , Cambridge University Press, Cambridge, págs. 3–9, doi :10.1017/CBO9781316339831, ISBN 978-1-107-11850-8, Sr. 3675279
^ Frieze & Karoński (2016), 2.1 Fase subcrítica, págs. 20–33; véase especialmente el Teorema 2.8, pág. 26, el Teorema 2.9, pág. 28, y el Lema 2.11, pág. 29
^ Frieze y Karoński (2016), 2.3 Transición de fase, págs. 39-45
^ Frieze & Karoński (2016), 2.2 Fase supercrítica, págs. 33; véase especialmente el Teorema 2.14, págs. 33–39
^ Frieze y Karoński (2016), 4.1 Conectividad, págs. 64-68
^ Cohen, Reuven; Havlin, Shlomo (2010), "10.1 Percolación en redes complejas: Introducción", Redes complejas: Estructura, robustez y función , Cambridge University Press, págs. 97–98, ISBN 978-1-139-48927-0, archivado desde el original el 10 de enero de 2022 , consultado el 10 de enero de 2022

Enlaces externos

Código MATLAB para encontrar componentes en gráficos no dirigidos, intercambio de archivos MATLAB.
Componentes conectados, Steven Skiena, Repositorio de algoritmos de Stony Brook