Gráfico sin triángulos
En el área matemática de la teoría de grafos , un grafo sin triángulos es un grafo no dirigido en el que no hay tres vértices que formen un triángulo de aristas. Los gráficos sin triángulos se pueden definir de manera equivalente como gráficos con un número de camarilla ≤ 2, gráficos con circunferencia ≥ 4, gráficos sin 3 ciclos inducidos o gráficos localmente independientes .
Por el teorema de Turán , el grafo libre de triángulos de n vértices con el máximo número de aristas es un grafo bipartito completo en el que el número de vértices a cada lado de la bipartición es lo más igual posible.
El problema de encontrar triángulos es el problema de determinar si un gráfico está libre de triángulos o no. Cuando el gráfico contiene un triángulo, a menudo se requieren algoritmos para generar tres vértices que forman un triángulo en el gráfico.
Es posible probar si un gráfico con m aristas está libre de triángulos en el tiempo O( m 1.41 ). [1] Otro enfoque es encontrar la traza de A 3 , donde A es la matriz de adyacencia del gráfico. La traza es cero si y solo si el gráfico no tiene triángulos. Para gráficos densos , es más eficiente usar este algoritmo simple que se basa en la multiplicación de matrices , ya que reduce la complejidad del tiempo a O ( n 2.373 ), donde n es el número de vértices.
Como demostraron Imrich, Klavžar y Mulder (1999) , el reconocimiento de gráficos sin triángulos es equivalente en complejidad al reconocimiento de gráficos medianos ; sin embargo, los mejores algoritmos actuales para el reconocimiento de gráficos medianos usan la detección de triángulos como una subrutina en lugar de viceversa.
La complejidad del árbol de decisión o complejidad de consulta del problema, donde las consultas son a un oráculo que almacena la matriz de adyacencia de un gráfico, es Θ( n 2 ). Sin embargo, para los algoritmos cuánticos , el límite inferior más conocido es Ω( n ), pero el algoritmo más conocido es O( n 5/4 ). [2]
