En el área matemática de la teoría de grafos , un gráfico no dirigido G es fuertemente cordal si es un gráfico cordal y cada ciclo de longitud par (≥ 6) en G tiene un acorde impar , es decir, un borde que conecta dos vértices que son impares. distancia (> 1) separadas entre sí en el ciclo.
Caracterizaciones [ editar ]
Los gráficos fuertemente cordales tienen una caracterización de subgrafía prohibida, ya que los gráficos que no contienen un ciclo inducido de longitud mayor que tres o un n- sol ( n ≥ 3) como un subgrafo inducido . [2] Un n -sun es un gráfico cordal con 2 n vértices, dividido en dos subconjuntos U = { u 1 , u 2 , ...} y W = { w 1 , w 2 , ...}, de modo que cada vértice w i en W tiene exactamente dos vecinos, ui y u ( i + 1) mod n . Un n -sun no puede ser fuertemente cordal, porque el ciclo u 1 w 1 u 2 w 2 ... no tiene un acorde extraño.
Los gráficos fuertemente cordales también se pueden caracterizar como gráficos que tienen un orden de eliminación fuerte y perfecto, un orden de los vértices de tal manera que los vecinos de cualquier vértice que vienen más adelante en el orden forman una camarilla y de tal manera que, para cada i < j < k < l , si el vértice i ésimo en el orden es adyacente a los vértices k th y l , y los vértices j th y k th son adyacentes, entonces los vértices j th y l th también deben ser adyacentes. [3]
Un gráfico es fuertemente cordal si y solo si cada una de sus subgrafías inducidas tiene un vértice simple, un vértice cuyos vecinos tienen vecindarios que están ordenados linealmente por inclusión. [4] Además, un gráfico es fuertemente cordal si y solo si es cordal y cada ciclo de longitud cinco o más tiene un triángulo de 2 acordes, un triángulo formado por dos acordes y un borde del ciclo. [5]
Un gráfico es fuertemente cordal si y solo si cada una de sus subgrafías inducidas es un gráfico doblemente cordal . [6]
Los gráficos fuertemente cordales también pueden caracterizarse en términos del número de subgrafías completas en las que participa cada borde. [7] Sin embargo, se da otra caracterización. [8]
Reconocimiento [ editar ]
Es posible determinar si un gráfico es fuertemente cordal en tiempo polinómico , buscando y eliminando repetidamente un vértice simple. Si este proceso elimina todos los vértices en el gráfico, el gráfico debe ser fuertemente cordal; de lo contrario, si este proceso encuentra un subgrafo sin vértices más simples, el gráfico original no puede ser fuertemente cordal. Para un gráfico fuertemente cordal, el orden en que se eliminan los vértices mediante este proceso es un orden de eliminación perfecto y fuerte. [9]
Ahora se conocen algoritmos alternativos que pueden determinar si un gráfico es fuertemente cordal y, si es así, construir una eliminación perfecta fuerte ordenando de manera más eficiente, en el tiempo O (min ( n 2 , ( n + m ) log n )) para un gráfico con n vértices ym aristas. [10]
Subclases [ editar ]
Una subclase importante (basado en la filogenia ) es la clase de k - potencias de la hoja , los gráficos formados a partir de las hojas de un árbol mediante la conexión de dos hojas por un borde cuando su distancia en el árbol es como máximo k . Una potencia de hoja es un gráfico que es una potencia de hoja k para algunos k . Dado que los poderes de los gráficos fuertemente cordales son fuertemente cordales y los árboles son fuertemente cordales, se deduce que los poderes de las hojas son fuertemente cordales. Forman una subclase adecuada de gráficos fuertemente cordales, que a su vez incluye los gráficos de racimo como las potencias de 2 hojas. [11] Otra subclase importante de gráficos fuertemente cordales son los gráficos de intervalos . En[12] se muestra que los gráficos de intervalo y la clase más grande de gráficos de ruta dirigida enraizada son poderes de hoja.
Problemas algorítmicos [ editar ]
Dado que los gráficos son muy acordes ambos gráficos de cuerdas y gráficos doblemente cordales , diversos problemas NP-completos, como Independiente grupo, banda, colorear, cubierta camarilla, dominando Conjunto, y el árbol de Steiner se pueden resolver de manera eficiente para gráficos fuertemente cordales. El isomorfismo de gráficos es isomorfismo completo para gráficos fuertemente cordales. [13] El circuito hamiltoniano sigue siendo NP completo para gráficos divididos fuertemente cordales .
En el área matemática de la teoría de grafos , un gráfico bipartito cordal es un gráfico bipartito B = ( X , Y , E ) en el que cada ciclo de longitud de al menos 6 en B tiene un acorde , es decir, un borde que conecta dos vértices que son una distancia> 1 separada entre sí en el ciclo. [1] Un mejor nombre sería débilmente cordal y bipartito ya que los gráficos bipartitos cordales en general no son cordales como lo muestra el ciclo inducido de longitud 4.
Caracterizaciones [ editar ]
Los gráficos bipartitos cordales tienen varias caracterizaciones en términos de ordenaciones de eliminación perfecta , hipergrafías y matrices . Están estrechamente relacionados con gráficos fuertemente cordales . Por definición, los gráficos bipartitos cordales tienen una caracterización de subgrafía prohibida como los gráficos que no contienen ningún ciclo inducido de longitud 3 o de longitud al menos 5 (los llamados agujeros) como subgrafía inducida . Por lo tanto, un gráfico G es cordal bipartito si y solo si G no tiene triángulos ni agujeros. En Golumbic (1980) , se mencionan otras dos caracterizaciones: Bes cordal bipartito si y solo si cada separador de borde mínimo induce un subgrafo bipartito completo en B si y solo si cada subgrafo inducido es bipartito de eliminación perfecta.
Martin Farber ha demostrado: Un gráfico es fuertemente cordal si y solo si el gráfico de incidencia bipartita de su hipergrafía de camarilla es bipartito cordal. [2]
Una caracterización similar es válida para la hipergrafía de vecindad cerrada: una gráfica es fuertemente cordal si y solo si la gráfica de incidencia bipartita de su hipergrafía de vecindad cerrada es bipartita cordal. [3]
Otro resultado encontrado por Elias Dahlhaus es: Un gráfico bipartito B = ( X , Y , E ) es cordal bipartito si y solo si el gráfico dividido resultante de hacer de X una camarilla es fuertemente cordal. [4]
Un gráfico bipartito B = ( X , Y , E ) es bipartito cordal si y solo si cada subgrafo inducido de B tiene un orden máximo de vecindad X y un orden máximo de vecindad Y. [5]
Varios resultados describen la relación entre los gráficos bipartitos cordales y las hipergrafías vecinas totalmente equilibradas de los gráficos bipartitos. [6]
Se da una caracterización de gráficos bipartitos cordales en términos de gráficos de intersección relacionados con hipergrafías. [7]
Un gráfico bipartito es cordal bipartito si y solo si su matriz de adyacencia está totalmente equilibrada si y solo si la matriz de adyacencia está libre de Gamma. [8]
Reconocimiento [ editar ]
Los gráficos bipartitos cordales se pueden reconocer en el tiempo O (min ( n 2 , ( n + m ) log n )) para un gráfico con n vértices ym bordes. [9]
Complejidad de problemas [ editar ]
Varios problemas como el ciclo hamiltoniano, [10] el árbol de Steiner [11] y la dominación eficiente [12] permanecen NP completos en los gráficos bipartitos cordales.
Varios otros problemas que pueden resolverse eficientemente para gráficos bipartitos pueden resolverse de manera más eficiente para gráficos bipartitos cordales como se discute en [13]
Clases gráficas relacionadas [ editar ]
Cada gráfico bipartito cordal es un gráfico modular . Los gráficos bipartitos cordales incluyen los gráficos bipartitos completos y los gráficos bipartitos de distancia hereditaria .
Un acorde de un círculo es un segmento de línea recta cuyos puntos finales se encuentran en el círculo. Una línea secante , o simplemente secante , es la extensión de línea infinita de un acorde. Más generalmente, un acorde es un segmento de línea que une dos puntos en cualquier curva, por ejemplo, una elipse . Un acorde que pasa a través del punto central de un círculo es el diámetro del círculo. Cada diámetro es un acorde, pero no todos los acordes son un diámetro.
La palabra acorde proviene del latín chorda que significa cuerda de arco .
(como lo es el segmento de diámetro AB ).
En círculos [ editar ]
- Los acordes son equidistantes del centro si y solo si sus longitudes son iguales.
- Los acordes iguales se sostienen por ángulos iguales desde el centro del círculo.
- Un acorde que pasa por el centro de un círculo se llama diámetro y es el acorde más largo.
- Si las extensiones de línea (líneas secantes) de los acordes AB y CD se cruzan en un punto P, entonces sus longitudes satisfacen AP · PB = CP · PD ( potencia de un teorema de puntos ).
En elipses [ editar ]
En trigonometría [ editar ]
Los acordes se usaron ampliamente en el desarrollo temprano de la trigonometría . La primera tabla trigonométrica conocida, compilada por Hipparchus , tabuló el valor de la función de acorde por cada 7.5 grados . En el siglo II dC, Ptolomeo de Alejandría compiló una tabla más extensa de acordes en su libro sobre astronomía , dando el valor del acorde para ángulos que varían de 1/2 grado a 180 grados en incrementos de medio grado. El círculo tenía un diámetro de 120 y las longitudes de los acordes tienen una precisión de dos dígitos de base 60 después de la parte entera. [2]
La función de acorde se define geométricamente como se muestra en la imagen. El acorde de un ángulo es la longitud del acorde entre dos puntos en un círculo unitario separado por ese ángulo central. El ángulo θ se toma en sentido positivo y debe estar en el intervalo 0 < θ ≤ π (medida en radianes). La función de acorde se puede relacionar con la función seno moderna , tomando uno de los puntos como (1,0) y el otro como ( cos θ , sin θ ), y luego utilizando el teorema de Pitágoras para calcular el acorde longitud: [2]
El último paso usa la fórmula de medio ángulo . Al igual que la trigonometría moderna se basa en la función seno, la trigonometría antigua se construyó en la función de acorde. Se dice que Hiparco escribió un trabajo de doce volúmenes sobre acordes, todos ahora perdidos, por lo que presumiblemente se sabía mucho sobre ellos. En la tabla a continuación (donde es la longitud del acorde y el diámetro del círculo) se puede demostrar que la función de acorde satisface muchas identidades análogas a las modernas conocidas:
| Nombre | A base de seno | Basado en acordes |
|---|---|---|
| pitagórico | ||
| Medio ángulo | ||
| Apotema ( a ) | ||
| Ángulo ( θ ) |
La función inversa también existe: [3]
No hay comentarios:
Publicar un comentario