Rango de contorno

En la teoría de grafos, el rango de contorno [1] de un grafo no dirigido es el número mínimo de aristas cuya eliminación destruye todos los ciclos del grafo, convirtiéndolo en un árbol o bosque. El rango de contorno también se puede entender como el número de ciclos independientes en un gráfico. En contraste con el problema correspondiente de encontrar un conjunto de arcos de corte de ciclo para gráficos dirigidos , el rango de contorno r se calcula fácilmente mediante la fórmula

,

donde m es el número de aristas del gráfico dado, n es el número de vértices y c es el número de componentes conectados [2] . También es posible construir eficientemente un conjunto de bordes de tamaño mínimo que rompen ciclos utilizando el algoritmo voraz o el complemento del árbol de expansión .

El rango de contorno también se conoce como el número ciclomático de un gráfico. Se puede explicar en términos de teoría algebraica de grafos como la dimensión del espacio cíclico de un gráfico, en términos de matroides usando la noción de corank de matroides de grafos [3] , y en términos de topología como uno de los Betti números de un espacio topológico derivado de un gráfico. El rango de contorno cuenta el número de orejas en una descomposición de orejas de un gráfico, lo que proporciona la base para la noción de complejidad en casi árboles y se usa en métricas de software como parte de la definición de la complejidad ciclomática de una pieza de código. Bajo el nombre de complejidad ciclomática, el concepto fue introducido por Gustav Kirchhoff [4] [5] .

Rango de Matroid y construcción de un conjunto mínimo de corte de ciclo

El rango de contorno de un gráfico G se puede describir utilizando la teoría de matroides como el corank de un gráfico matroid para G [6] . Teniendo en cuenta la propiedad voraz de las matroides, esto significa que es posible encontrar el conjunto mínimo de aristas que destruye todos los ciclos utilizando el algoritmo voraz , que selecciona en cada paso una arista que pertenece a al menos un ciclo del gráfico restante.

Por otro lado, el conjunto mínimo de conjuntos que rompe todos los ciclos se puede encontrar construyendo un bosque expansivo de G y eligiendo un conjunto complementario de aristas que no pertenezcan al bosque expansivo.

Número de ciclos independientes

En la teoría algebraica de gráficos , el rango de contorno es la dimensión del espacio del ciclo de un gráfico . Intuitivamente, el rango de contorno se puede explicar contando el número de ciclos independientes de un gráfico, donde un conjunto de ciclos se considera independiente si es imposible formar un ciclo como la diferencia simétrica de algún subconjunto de otros ciclos [2] .

Esta cuenta de ciclos independientes se puede explicar usando la teoría de la homología , una rama de la topología . Cualquier gráfico G puede verse como un ejemplo de un complejo simplicial unidimensional , un tipo de espacio topológico , formado al representar cada borde del gráfico por un segmento y pegar estos segmentos en los extremos. El número ciclomático es el rango del primer grupo de homología (entero) de este complejo [7] ,

En relación con tal conexión topológica, el número ciclomático del grafo G también se denomina primer número de Betti del grafo G [8] . Más generalmente, el primer número de Betti de cualquier espacio topológico cuenta el número de ciclos independientes en el espacio.

El rango de contorno de un gráfico está relacionado con el rango de su matriz de incidencia a través de la relación .

Aplicaciones

Coeficiente de reticulación

Una variante del rango de contorno de un gráfico plano , normalizado al dividir por el rango de contorno máximo posible de cualquier gráfico plano con el mismo conjunto de vértices, se denomina factor de compensación . Para grafos planos conectados con m aristas y n vértices, el coeficiente de red se puede calcular usando la fórmula [9]

En esta fórmula, el numerador en la fórmula es el rango de contorno del gráfico dado, y el denominador es el rango de contorno más grande posible de un gráfico plano con n vértices. El factor de malla se encuentra entre 0 para árboles y 1 para gráficos planos máximos .

Descomposición del oído

El rango de contorno refleja el número de orejas en la descomposición de orejas del gráfico, la descomposición de los bordes del gráfico en caminos y ciclos, lo que suele ser útil en los algoritmos de gráficos. En particular, un gráfico está conectado por 2 vértices si y solo si tiene una descomposición de oreja abierta, una secuencia de subgrafos en los que el primer subgrafo es un ciclo simple y los subgrafos restantes son caminos simples y cada camino comienza y termina en los vértices. pertenecientes a subgrafos anteriores, y cada vértice interior del camino aparece por primera vez en ese camino. En cualquier gráfico biconectado con rango de contorno, cualquier descomposición de oreja abierta tiene exactamente orejas [10] .

Casi árboles

Un gráfico con un número ciclomático también se denomina árbol casi r , ya que solo es necesario eliminar los bordes r del gráfico para convertirlo en un árbol o bosque. Un casi 1 árbol es casi un árbol : un casi árbol conectado es un pseudobosque , un ciclo con árboles (posiblemente triviales) enraizados en cada vértice [11] .

Algunos autores han estudiado la complejidad parametrizada de algoritmos sobre árboles casi r con parametrización según [12] [13] .

Generalización para grafos dirigidos

El rango cíclico es un gráfico invariante dirigido que mide el nivel de anidamiento de ciclos en un gráfico. Este invariante tiene una definición más complicada que el rango ciclomático (estrechamente relacionado con la definición de profundidad de árbol para grafos no dirigidos) y es mucho más difícil de calcular. Otro problema para los grafos dirigidos relacionados con el rango ciclomático es la determinación del conjunto mínimo de arcos de corte de ciclo , es decir, el conjunto mínimo de arcos cuya eliminación destruye todos los ciclos dirigidos. Ambos problemas, calcular el rango cíclico y determinar el conjunto mínimo de arcos que cortan ciclos, son NP-difíciles .

También es posible calcular una invariante más simple de gráficos dirigidos ignorando las direcciones de los bordes y calculando el rango cíclico de un gráfico no dirigido. Este principio forma la base para definir la complejidad ciclomática , una medida de la complejidad del programa de computadora para estimar la complejidad de una pieza de código de computadora.

Conceptos relacionados

Otros números definidos en términos de eliminación de bordes de un gráfico no dirigido incluyen conectividad de bordes , la cantidad mínima de bordes cuya eliminación provoca la pérdida de conectividad, y el número de evitación de coincidencias , la cantidad mínima de bordes cuya eliminación hace que cese una coincidencia perfecta existir

Notas

  1. ↑ En la literatura en ruso, tanto el rango de ciclo como el rango de circuito a menudo se traducen de la misma manera: rango cíclico. En la literatura inglesa, el primer término se refiere a gráficos dirigidos, el segundo a gráficos no dirigidos. En este artículo, el término "rango cíclico" se usa para gráficos dirigidos y "rango de contorno" para gráficos no dirigidos.
  2. ↑ 12 Bergé , 2001 , pág. 27–30.
  3. ↑ En la literatura en idioma ruso, también se usa el término matroid gráfico , que es un papel de calco del matroid gráfico inglés y no corresponde del todo a la esencia del concepto.
  4. ↑ Kotiuga, 2010 , pág. veinte.
  5. ↑ Hage, 1996 , pág. 48.
  6. ↑ Bergé, 1976 , pág. 477.
  7. ↑ Serre, 2003 , pág. 23
  8. ↑ Berkolaiko, Kuchment, 2013 , pág. cuatro
  9. ↑ Buhl, Gautrais, Sole et al., 2004 , pág. 123–129.
  10. ↑ Whitney, 1932 , pág. 339–362.
  11. ↑ Brualdi, 2006 , pág. 349.
  12. ↑ Coppersmith, Vishkin, 1985 , p. 27–45.
  13. ↑ Fiala, Kloks, Kratochvíl, 2001 , p. 59–72.

Literatura