stringtranslate.com

Componente (teoría de grafos)

Un gráfico con tres componentes

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 demás; 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:

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 es alcanzable desde un vértice 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:

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]

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 particular encontrará el componente completo que contiene (y no más) antes de regresar. Todos los componentes de un grafo pueden encontrarse 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 ha sido 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]

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]

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

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.

Subcrítico
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]
Crítico
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]
Supercrítico
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]

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]

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

  1. ^ 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
  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 (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
  3. ^ 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
  4. ^ 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
  5. ^ 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
  6. ^ 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
  7. ^ 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
  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. 97-98
  9. ^ 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
  10. ^ 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
  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 8 de enero de 2022 , consultado el 8 de enero de 2022
  12. ^ 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
  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, ISBN 978-3-642-27848-8, archivado (PDF) del original el 8 de enero de 2022 , consultado el 8 de enero de 2022
  14. ^ 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.
  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; véase el teorema 2, pág. 59, y el corolario, pág. 65
  16. ^ 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
  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 , MR  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), Aspects of Incremental Computing (tesis doctoral), Universidad de Yale, pág. 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 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
  24. ^ 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
  25. ^ 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
  26. ^ 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
  27. ^ 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
  28. ^ 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
  29. ^ 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
  30. ^ Frieze y Karoński (2016), 2.3 Transición de fase, págs. 39-45
  31. ^ Frieze y Karoński (2016), 2.2 Fase supercrítica, págs. 33; véase especialmente el teorema 2.14, págs. 33-39
  32. ^ Frieze y 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