Componente (teoría de grafos)

Subgrafo máximo cuyos vértices pueden alcanzarse entre sí.

Un gráfico con tres componentes.

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.

Definiciones y ejemplos

Un gráfico de conglomerados con siete 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: ${\displaystyle v}$ ${\displaystyle 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, un componente de este tipo se forma 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 gráfico de conglomerados , cada componente es una camarilla máxima . Estos gráficos pueden producirse como cierres transitivos de gráficos arbitrarios no dirigidos, para los cuales encontrar el cierre transitivo es una formulación equivalente a identificar los componentes conectados. ^[6]

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 ${\displaystyle v}$ 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: ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle v}$

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

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]

Número de componentes

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] ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle n-c}$ ${\displaystyle n-c}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle m-n+c}$

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]

Algoritmos

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 ${\displaystyle v}$ en particular encontrará el componente completo que contiene ${\displaystyle v}$ (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] ${\displaystyle O(\alpha (n))}$ ${\displaystyle \alpha }$ ${\displaystyle O(\log ^{2}n/\log \log n)}$ ${\displaystyle O(\log n/\log \log n)}$

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] ${\displaystyle \varepsilon n}$ ${\displaystyle O(\varepsilon ^{-2}\log \varepsilon ^{-1})}$

En gráficos aleatorios

Un gráfico aleatorio de Erdős-Rényi-Gilbert con 1000 vértices con probabilidad de arista (en el rango crítico), que muestra un componente grande y muchos pequeños ${\displaystyle p=1/(n-1)}$

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. ${\displaystyle G(n,p)}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle 1-p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle \varepsilon }$ ${\displaystyle n}$

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

En esta gama , todos los componentes son simples y muy pequeños. El componente más grande tiene 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 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 aparece linealmente muchas veces. ^[29] ${\displaystyle p}$

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

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

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

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

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] ${\displaystyle p}$ ${\displaystyle p<(1-\varepsilon )(\log n)/n}$ ${\displaystyle p>(1+\varepsilon )(\log n)/n}$

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]

Referencias

1. Clark, Juan; 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
2. 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 (0.8-r1991 ed.), Google, págs. 34-35, archivado desde el original el 16 de enero , 2016 , consultado el 8 de enero de 2022.
3. Tutte, WT (1984), Teoría de grafos, Enciclopedia de las 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
4. Thulasiraman, K.; Swamy, MNS (2011), Gráficos: teoría y algoritmos, John Wiley & Sons, p. 9, ISBN 978-1-118-03025-7, archivado desde el original el 7 de enero de 2022 , consultado el 7 de enero de 2022
5. Bollobás, Béla (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas, vol. 184, Nueva York: Springer-Verlag, pág. 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
6. McColl, WF; Noshita, K. (1986), "Sobre el número de aristas en el cierre transitivo de un gráfico", Matemáticas Aplicadas Discretas , 15 (1): 67–73, doi :10.1016/0166-218X(86)90020-X, Señor  0856101
7. Foldes, Stephan (2011), Estructuras fundamentales de álgebra y matemáticas discretas, John Wiley & Sons, p. 199, ISBN 978-1-118-03143-8, archivado desde el original el 7 de enero de 2022 , consultado el 7 de enero de 2022
8. 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.
9. Knuth, Donald E. (15 de enero de 2022), "Componentes débiles", El arte de la programación informática, volumen 4, prefascículo 12A: componentes y recorrido (PDF) , págs. 11-14, archivado (PDF) de el original el 18 de enero de 2022 , recuperado el 1 de marzo de 2022
10. Lewis, Harry ; Zax, Rachel (2019), Matemáticas discretas esenciales para la informática, Princeton University Press, p. 145, ISBN 978-0-691-19061-7, archivado desde el original el 8 de enero de 2022 , consultado el 8 de enero de 2022
11. 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, págs. 20-22, doi :10.1007/978-1 -4612-4400-4, ISBN 0-387-97687-6, MR  1139767, S2CID  27747202, archivado desde el original el 2022-01-08 , consultado el 2022-01-08
12. Wilson, RJ (1973), "Una introducción a la teoría matroide", The American Mathematical Monthly , 80 (5): 500–525, doi :10.1080/00029890.1973.11993318, JSTOR  2319608, MR  0371694
13. 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, archivado (PDF) desde el original el 2022-01-08 , consultado el 2022-01-08
14. Cioabă, Sebastian M. (2011), "Algunas aplicaciones de valores propios de gráficos", en Dehmer, Matthias (ed.), Análisis estructural de redes complejas , Nueva York: Birkhäuser/Springer, págs. 357–379, doi :10.1007 /978-0-8176-4789-6_14, SEÑOR  2777924; ver prueba del Lema 5, p. 361 Archivado el 8 de enero de 2022 en Wayback Machine.
15. Read, Ronald C. (1968), "Una introducción a los polinomios cromáticos", Journal of Combinatorial Theory , 4 : 52–71, doi : 10.1016/S0021-9800(68)80087-0 , MR  0224505; ver Teorema 2, pág. 59, y corolario, pág. sesenta y cinco
16. Tutte, WT (1947), "La factorización de gráficas lineales", The Journal of the London Mathematical Society , 22 (2): 107–111, doi :10.1112/jlms/s1-22.2.107, MR  0023048
17. 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
18. 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 , SEÑOR  0316301
19. 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
20. 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 
21. Bengelloun, Safwan Abdelmajid (diciembre de 1982), Aspectos de la computación incremental (tesis doctoral), Universidad de Yale, p. 12, ProQuest  303248045
22. 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
23. Wulff-Nilsen, Christian (2013), "Conectividad de gráficos totalmente dinámicos y deterministas más rápidos", en Khanna, Sanjeev (ed.), Actas del vigésimo cuarto simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2013, Nueva Orleans, Luisiana, EE. UU., 6 al 8 de enero de 2013 , págs. 1757–1769, arXiv : 1209.5608 , doi :10.1137/1.9781611973105.126, S2CID  13397958
24. Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth (2017), "Fully Dynamic Connectivity in Amortized Expected Time", 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 ${\displaystyle O{\bigl (}\log n(\log \log n)^{2}{\bigr )}}$
25. Lewis, Harry R .; Papadimitriou, Christos H. (1982), "Computación simétrica delimitada por el espacio", Ciencias de la Computación Teórica , 19 (2): 161–187, doi : 10.1016/0304-3975(82)90058-5 , SEÑOR  0666539
26. Reingold, Omer (2008), "Conectividad no dirigida en el espacio de registro", Journal of the ACM , 55 (4): A17:1–A17:24, doi :10.1145/1391289.1391291, MR  2445014, S2CID  207168478
27. Berenbrink, Petra; Krayenhoff, Bruce; Mallmann-Trenn, Frederik (2014), "Estimación del número de componentes conectados en tiempo sublineal", Cartas de procesamiento de información , 114 (11): 639–642, doi :10.1016/j.ipl.2014.05.008, MR  3230913
28. Friso, 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, señor  3675279
29. Frieze & Karoński (2016), 2.1 Fase subcrítica, págs. 20-33; véase especialmente el teorema 2.8, p. 26, Teorema 2.9, pág. 28, y Lema 2.11, p. 29
30. Frieze & Karoński (2016), 2.3 Transición de fase, págs. 39–45
31. Frieze & Karoński (2016), 2.2 Fase supercrítica, págs.33; ver especialmente el Teorema 2.14, p. 33–39
32. Frieze & Karoński (2016), 4.1 Conectividad, págs. 64–68
33. 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 buscar componentes en gráficos no dirigidos, MATLAB File Exchange.
• Componentes conectados, Steven Skiena, The Stony Brook Algorithm Repository