Hispanopedia Wiki
Articulo de referencia

Número ciclomático

Este grafo tiene un número ciclomático r = 2 porque se puede convertir en un árbol eliminando dos aristas, por ejemplo las aristas 1-2 y 2-3, pero al eliminar cualquier arista q...

Hispanopedia WikiContenido en espanolLectura gratuita
Este grafo tiene un número ciclomático r = 2 porque se puede convertir en un árbol eliminando dos aristas, por ejemplo las aristas 1-2 y 2-3, pero al eliminar cualquier arista queda un ciclo en el grafo.

En la teoría de grafos , una rama de las matemáticas , el número ciclomático , rango de circuito , rango de ciclo , corango o nulidad de un grafo no dirigido es el número mínimo de aristas que deben eliminarse del grafo para romper todos sus ciclos , convirtiéndolo en un árbol o bosque .

El concepto fue introducido y denominado número ciclomático por Gustav Kirchhoff . [ 1 ] [ 2 ]

Fórmula

El número ciclomático de un grafo es igual al número de ciclos independientes en el grafo, es decir, al tamaño de una base de ciclos . A diferencia del problema del conjunto de arcos de retroalimentación correspondiente para grafos dirigidos , el número ciclomático r se calcula fácilmente mediante la fórmula: r=mi−v+do,{\displaystyle r=e-v+c,} donde e es el número de aristas en el grafo dado, v es el número de vértices y c es el número de componentes conexas . [ 3 ]

Es posible construir un conjunto de aristas de tamaño mínimo que rompa todos los ciclos de manera eficiente, ya sea utilizando un algoritmo voraz o complementando un bosque de expansión .

El número ciclomático puede explicarse en términos de teoría algebraica de grafos como la dimensión del espacio de ciclos del grafo, en términos de teoría de matroides como el rango dual de su matroide gráfico , y en términos de topología como uno de los números de Betti de un espacio topológico derivado del grafo. Cuenta las orejas en una descomposición en orejas del grafo, constituye la base de la complejidad parametrizada en casi-árboles, y se ha aplicado en métricas de software como parte de la definición de complejidad ciclomática de un fragmento de código.

Para hipergrafos

El número ciclomático de un hipergrafo se puede derivar de su grafo de Levi , con el mismo número ciclomático pero reducido a un grafo simple. Es r=gramo−(v+mi)+do,{\displaystyle r=g-(v+e)+c,} donde g es la suma de grados (y el número de aristas en el grafo de Levi), e es el número de hiperaristas en el hipergrafo dado, v es el número de vértices y c es el número de componentes conexas .

La suma de grados de un hipergrafo es la suma de los grados de todos sus vértices, reduciéndose a 2e para un grafo simple o a ke para un hipergrafo k -uniforme. Esta fórmula es simétrica entre vértices y aristas , lo que demuestra que un hipergrafo y su hipergrafo dual tienen el mismo número ciclomático.

Clasificación de matroides y construcción de un conjunto mínimo de aristas de retroalimentación.

El número ciclomático de un grafo G puede describirse utilizando la teoría de matroides como el rango dual del matroide gráfico de G. [ 4 ] Utilizando la propiedad voraz de los matroides, esto significa que se puede encontrar un conjunto mínimo de aristas que rompa todos los ciclos utilizando un algoritmo voraz que en cada paso elige una arista que pertenece al menos a un ciclo del grafo restante.

Alternativamente, se puede encontrar un conjunto mínimo de aristas que rompa todos los ciclos construyendo un bosque maximal de G y eligiendo el conjunto complementario de aristas que no pertenecen al bosque maximal.

El número de ciclos independientes

En la teoría algebraica de grafos , el número ciclomático es también la dimensión del espacio de ciclos deGRAMO{\displaystyle G}Intuitivamente, esto puede explicarse como que el número ciclomático cuenta el número de ciclos independientes en el grafo, donde una colección de ciclos es independiente si no es posible formar uno de los ciclos como la diferencia simétrica de algún subconjunto de los demás. [ 3 ]

Este recuento de ciclos independientes también puede explicarse utilizando la teoría de homología , una rama de la topología. Cualquier grafo G puede considerarse un ejemplo de un complejo simplicial unidimensional , un tipo de espacio topológico formado al representar cada arista del grafo mediante un segmento de línea y unir estos segmentos en sus extremos. El número ciclomático es el rango del primer grupo de homología ( entero ) de este complejo, [ 5 ].r=rango⁡[H1(GRAMO,Z)].{\displaystyle r=\operatorname {rank} \left[H_{1}(G,\mathbb {Z} )\right].} Debido a esta conexión topológica, el número ciclomático de un grafo G también se denomina primer número de Betti de G. [ 6 ] De manera más general, el primer número de Betti de cualquier espacio topológico, definido de la misma manera, cuenta el número de ciclos independientes en el espacio.

Aplicaciones

coeficiente de mallado

Una variante del número ciclomático para grafos planares , normalizada dividiéndola por el número ciclomático máximo posible de cualquier grafo planar con el mismo conjunto de vértices, se denomina coeficiente de mallado . Para un grafo planar conexo con m aristas y n vértices, el coeficiente de mallado se puede calcular mediante la fórmula [ 7 ].

metro−norte+12norte−5.{\displaystyle {\frac {m-n+1}{2n-5}}.}

Aquí, el numeradormetro−norte+1{\displaystyle m-n+1}de la fórmula es el número ciclomático de la gráfica dada, y el denominador2norte−5{\displaystyle 2n-5}es el mayor número ciclomático posible de un grafo planar de n vértices. El coeficiente de mallado varía entre 0 para árboles y 1 para grafos planares máximos .

Descomposición del oído

El número ciclomático controla el número de orejas en una descomposición en orejas de un grafo, una partición de las aristas del grafo en caminos y ciclos que es útil en muchos algoritmos de grafos. En particular, un grafo es 2-vértice-conexo si y solo si tiene una descomposición en orejas abierta. Esta es una secuencia de subgrafos, donde el primer subgrafo es un ciclo simple, los subgrafos restantes son todos caminos simples, cada camino comienza y termina en vértices que pertenecen a subgrafos anteriores, y cada vértice interno de un camino aparece por primera vez en ese camino. En cualquier grafo biconexo con rango de circuitor{\displaystyle r}, cada descomposición de oído abierto tiene exactamenter{\displaystyle r}orejas. [ 8 ]

Casi árboles

Un gráfico con número ciclomáticor{\displaystyle r}También se le llama r -casi-árbol , porque solo es necesario eliminar r aristas del grafo para convertirlo en un árbol o bosque. Un 1-casi-árbol es un casi-árbol , y un casi-árbol conectado es un pseudoárbol , un ciclo con un árbol (posiblemente trivial) enraizado en cada vértice. [ 9 ]

Varios autores han estudiado la complejidad parametrizada de algoritmos de grafos en r -near-trees, parametrizados porr{\displaystyle r}. [ 10 ] [ 11 ]

Generalizaciones a grafos dirigidos

El rango de ciclos es un invariante de los grafos dirigidos que mide el grado de anidamiento de los ciclos en el grafo. Su definición es más compleja que la del número ciclomático (estrechamente relacionada con la definición de profundidad de árbol para grafos no dirigidos) y su cálculo es más difícil. Otro problema para los grafos dirigidos, relacionado con el número ciclomático, es el conjunto mínimo de arcos de retroalimentación , el conjunto más pequeño de aristas cuya eliminación rompe todos los ciclos dirigidos. Tanto el rango de ciclos como el conjunto mínimo de arcos de retroalimentación son problemas NP-difíciles de calcular.

También es posible calcular un invariante más simple de grafos dirigidos ignorando la dirección de las aristas y calculando el rango del circuito del grafo no dirigido subyacente. Este principio constituye la base de la definición de complejidad ciclomática , una métrica de software para estimar la complejidad de un fragmento de código informático.

Química computacional

En los campos de la química y la quimioinformática , el número ciclomático de un grafo molecular (el número de anillos en el conjunto más pequeño de anillos más pequeños ) a veces se denomina número de Frèrejacque . [ 12 ] [ 13 ] [ 14 ]

Complejidad parametrizada

Algunos problemas computacionales sobre grafos son NP-difíciles en general, pero pueden resolverse en tiempo polinomial para grafos con un número ciclomático pequeño. Un ejemplo es el problema de reconfiguración de caminos. [ 15 ]

Otros números definidos en términos de eliminar elementos de los gráficos son:

Referencias

  1. ↑ Peter Robert Kotiuga (2010), A Celebration of the Mathematical Legacy of Raoul Bott , American Mathematical Soc., p.  20, ISBN 978-0-8218-8381-5
  2. ↑ Per Hage (1996), Redes insulares: Comunicación, parentesco y estructuras de clasificación en Oceanía , Cambridge University Press, pág. 48, ISBN  978-0-521-55232-5
  3. 1 2 Berge, Claude (2001), "Número ciclomático", La teoría de los grafos , Courier Dover Publications, pp. 27–30 , ISBN  9780486419756.
  4. ↑ Berge, Claude (1976), Graphs and Hypergraphs , North-Holland Mathematical Library, vol. 6, Elsevier, p. 477, ISBN   9780720424539.
  5. ↑ Serre, Jean-Pierre (2003), Árboles , Monografías de Springer en Matemáticas, Springer, pág. 23, ISBN  9783540442370.
  6. ↑ Gregory Berkolaiko; Peter Kuchment (2013), Introducción a los grafos cuánticos , American Mathematical Soc., pág. 4, ISBN  978-0-8218-9211-4
  7. ↑ Buhl, J.; Gautrais, J.; Sole, RV; Kuntz, P.; Valverde, S.; Deneubourg, JL; Theraulaz, G. (2004), "Eficiencia y robustez en redes de galerías de hormigas", The European Physical Journal B , 42 (1), Springer-Verlag: 123– 129, Bibcode : 2004EPJB...42..123B , doi : 10.1140/epjb/e2004-00364-9.
  8. ↑ Whitney, H. (1932), "Grafos no separables y planares", Transactions of the American Mathematical Society , 34 (2): 339–362 , doi : 10.2307/1989545 , JSTOR 1989545 , PMC 1076008 , PMID 16587624   . Véanse en particular los teoremas 18 (que relaciona la descomposición de orejas con el rango del circuito) y 19 (sobre la existencia de descomposiciones de orejas).
  9. ↑ Brualdi, Richard A. (2006), Combinatorial Matrix Classes , Encyclopedia of Mathematics and Its Applications, vol. 108, Cambridge: Cambridge University Press , p. 349 , ISBN   0-521-86565-4, Zbl 1106.05001 
  10. ↑ Coppersmith, Don ; Vishkin, Uzi (1985), "Resolución de problemas NP-difíciles en 'casi árboles': cobertura de vértices", Discrete Applied Mathematics , 10 (1): 27–45 , doi : 10.1016/0166-218X(85)90057-5 , Zbl 0573.68017 .
  11. ↑ Fiala, Jiří; Kloks, tonelada; Kratochvíl, Jan (2001), "Complejidad de parámetros fijos de etiquetas λ", Matemáticas aplicadas discretas , 113 (1): 59– 72, doi : 10.1016/S0166-218X(00)00387-5 , Zbl 0982.05085 .
  12. ↑ May, John W.; Steinbeck, Christoph (2014), "Percepción eficiente de anillos para el kit de desarrollo químico", Journal of Cheminformatics , 6 (3): 3, doi : 10.1186/1758-2946-6-3 , PMC 3922685 , PMID 24479757  
  13. ↑ Downs, GM; Gillet, VJ; Holliday, JD; Lynch, MF (1989), "Una revisión de los algoritmos de percepción de anillos para grafos químicos ", J. Chem. Inf. Comput. Sci. , 29 (3): 172–187 , doi : 10.1021/ci00063a007
  14. ↑ Frèrejacque, Marcel (1939), "N° 108-Condensation d'une molecula organique" [ Condensación de una molécula orgánica ] , Bull. Soc. Chim. P. , 5 : 1008-1011​
  15. ↑ Demaine, Erik D. ; Eppstein, David ; Hesterberg, Adam; Jain, Kshitij; Lubiw, Anna ; Uehara, Ryuhei; Uno, Yushi (2019), "Reconfigurando rutas no dirigidas", en Friggstad, Zachary; Sack, Jörg-Rüdiger ; Salavatipour, Mohammad R. (eds.), Algoritmos y estructuras de datos – 16.º Simposio Internacional, WADS 2019, Edmonton, AB, Canadá, 5-7 de agosto de 2019, Actas , Lecture Notes in Computer Science, vol. 11646, Springer, págs. 353–365 , arXiv : 1905.00518 , doi : 10.1007/978-3-030-24766-9_26 , ISBN   978-3-030-24765-2