En teoría de grafos , una rama de las matemáticas , el rango de circuito , número ciclomático , rango de ciclo o nulidad de un grafo no dirigido es el número mínimo de aristas que se deben eliminar del grafo para romper todos sus ciclos , convirtiéndolo en un árbol o bosque . Es igual al número de ciclos independientes en el grafo (el tamaño de una base de ciclo ). A diferencia del problema de conjunto de arcos de retroalimentación correspondiente para grafos dirigidos , el rango de circuito r se calcula fácilmente utilizando la fórmula
donde m es el número de aristas en el gráfico dado, n es el número de vértices y c es el número de componentes conectados . [1] También 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 codicioso o complementando un bosque de expansión .
El rango del circuito se puede explicar en términos de la teoría de grafos algebraicos como la dimensión del espacio de ciclos de un grafo, en términos de la teoría de matroides como el corank de un 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 de orejas del grafo, forma 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. Con el nombre de número ciclomático, el concepto fue introducido por Gustav Kirchhoff . [2] [3]
El rango del circuito de un grafo G puede describirse utilizando la teoría de matroides como el corank del matroide gráfico de G. [4] Utilizando la propiedad codiciosa de los matroides , esto significa que uno puede encontrar un conjunto mínimo de aristas que rompe todos los ciclos utilizando un algoritmo codicioso que en cada paso elige una arista que pertenece al menos a un ciclo del grafo restante.
Como alternativa, se puede encontrar un conjunto mínimo de aristas que rompa todos los ciclos construyendo un bosque de expansión de G y eligiendo el conjunto complementario de aristas que no pertenecen al bosque de expansión.
En la teoría de grafos algebraicos , el rango del circuito es también la dimensión del espacio de ciclos de . Intuitivamente, esto se puede explicar como que el rango del circuito 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 otros. [1]
Este recuento de ciclos independientes también se puede explicar 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 de línea en sus puntos finales. El número ciclomático es el rango del primer grupo de homología ( entero ) de este complejo, [5]
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.
Una variante del rango de circuito para grafos planares , normalizado al dividir por el rango de circuito máximo posible de cualquier grafo planar con el mismo conjunto de vértices, se denomina coeficiente de mallado . Para un grafo planar conectado con m aristas y n vértices, el coeficiente de mallado se puede calcular mediante la fórmula [7]
Aquí, el numerador de la fórmula es el rango de circuito del grafo dado, y el denominador es el rango de circuito más grande posible de un grafo plano de n vértices. El coeficiente de malla varía entre 0 para árboles y 1 para grafos planos máximos .
El rango de circuito controla el número de orejas en una descomposición de 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 conexo por 2 vértices si y solo si tiene una descomposición de orejas abiertas. 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 circuito , cada descomposición de orejas abiertas tiene exactamente orejas. [8]
Un grafo con número ciclomático también se denomina 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 : un casi-árbol conexo 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 árboles cercanos a r , parametrizados por . [10] [11]
El rango de ciclo es un invariante de los grafos dirigidos que mide el nivel de anidamiento de los ciclos en el grafo. Tiene una definición más complicada que el rango de circuito (estrechamente relacionado con la definición de profundidad de árbol para grafos no dirigidos) y es más difícil de calcular. Otro problema para los grafos dirigidos relacionado con el rango de circuito es el conjunto de arcos de retroalimentación mínimos , el conjunto más pequeño de aristas cuya eliminación rompe todos los ciclos dirigidos. Tanto el rango de ciclo como el conjunto de arcos de retroalimentación mínimos son NP-difíciles de calcular.
También es posible calcular un invariante más simple de grafos dirigidos ignorando las direcciones 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 cuán complicada es una parte del código informático.
En los campos de la química y la quimioinformática , el rango de circuito de un gráfico 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]
Algunos problemas computacionales en grafos son NP-hard en general, pero pueden resolverse en tiempo polinomial para grafos con un rango de circuito pequeño. Un ejemplo es el problema de reconfiguración de trayectorias. [15]
Otros números definidos en términos de eliminar cosas de los gráficos son:
![{\displaystyle r=\operatorname {rango} \left[H_{1}(G,\mathbb {Z} )\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33317573927c3cd825b3db1110427c8a94dc8641)
