Cactus (teoría de grafos)

En la teoría de grafos, un "cactus" (a veces llamado árbol de cactus ) es un gráfico conectado en el que dos ciclos simples tienen como máximo un vértice común. De manera equivalente, cualquier borde en dicho gráfico pertenece como máximo a un ciclo simple. De manera equivalente (para un cactus no trivial), cualquier bloque (subgrafo máximo sin bisagras ) es un borde o un ciclo.

Propiedades

Los cactus son grafos planos exteriores . Cualquier pseudo-árbol es un cactus.

La familia de grafos en la que cada componente es un cactus se cierra bajo las operaciones de tomar el menor del grafo . Esta familia de grafos se puede describir especificando el único menor prohibido , un "diamante" con cuatro vértices, formado al quitar una arista del grafo completo K 4 [1] .

Algoritmos y aplicaciones

Algunos problemas de colocación de objetos que son NP-difíciles para gráficos generales, como otros problemas de gráficos, pueden resolverse en tiempo polinomial para cactus [2] [3] .

Debido a que los cactus son casos especiales de grafos planos exteriores , muchos problemas de optimización combinatoria en grafos se pueden resolver en tiempo polinomial [4] .

Los cactus representan circuitos eléctricos que tienen propiedades útiles. Una de las primeras aplicaciones de los cactus se asoció con la introducción de amplificadores operacionales [5] [6] [7] .

Los cactus también se han utilizado recientemente en genómica comparativa.como medio de representar relaciones entre diferentes genomas o partes de genomas [8] .

Si un cactus está conectado y cada uno de sus vértices pertenece a no más de dos bloques, se le llama decembrista [9] . Cualquier grafo poliédrico tiene como subgrafo un "decembrista" que incluye todos los vértices del grafo, hecho que juega un papel esencial en la demostración de Leighton y Moitra [10] de que cualquier grafo poliédrico tiene una incrustación codiciosaen el plano euclidiano , en el que se asignan coordenadas a los vértices para que el algoritmo de referencia codiciosologra enviar mensajes entre todos los pares de vértices [11] .

Historia

Los cactus se estudiaron por primera vez con el nombre de árboles Husimi , que les dieron Frank Harari y George Eugene Uhlenbeck en honor al físico japonés que trabajó con estos gráficos, miembro extranjero de la Academia Rusa de Ciencias [12] Koji Fushimi[13] [14] (en la literatura en ruso sobre gráficos, el apellido se transcribe como Husimi [15] [16] ). El mismo artículo usa el nombre "cactus" para gráficos de este tipo, en los que cualquier ciclo es un triángulo, pero ahora se permiten ciclos de cualquier longitud.

Mientras tanto, el nombre de árbol Husimi comenzó a usarse para gráficos en los que cada bloque es un gráfico completo . Este nombre tiene poca semejanza con el trabajo de Husimi, y ahora se usa el término más apropiado " gráfico de bloques " para los gráficos de esta familia, y el término árbol de Husimi se usa con menos frecuencia.

Notas

  1. ↑ El-Mallah, Colbourn, 1988 , pág. 354–362.
  2. ↑ Ben-Moshe, Bhattacharya, Shi, 2005 , pág. 693–703.
  3. ↑ Zmazek, Zerovnik, 2005 , pág. 536–541.
  4. ↑ Korneenko, 1984 , pág. 215–217.
  5. ↑ Nishi, Chua [2], 1986 , pág. 398–405.
  6. ↑ Nishi, Chua [1], 1986 , pág. 381–397.
  7. ↑ Nishi, 1991 , pág. 766–769.
  8. ↑ Paten, Diekhans et al., 2010 , pág. 410–425.
  9. ↑ Decembrista : un popular tipo de cactus de interior
  10. ↑ Leighton, Moitra, 2010 .
  11. ↑ Leighton, Moitra, 2010 , pág. 686–705.
  12. ↑ Fushimi Koji. | ES ARAN . Consultado el 1 de julio de 2022. Archivado desde el original el 4 de junio de 2021.
  13. ↑ Harary, Uhlenbeck, 1953 , pág. 315–322.
  14. ↑ Husimi, 1950 , pág. 682–684.
  15. ↑ K. A. Zaretsky, “Sobre los árboles Husimi”, Matem. notas, 9:3 (1971), 253–262; Matemáticas. Notas, 9:3 (1971), 150–154 . Consultado el 27 de agosto de 2020. Archivado desde el original el 4 de junio de 2021.
  16. ↑ Algoritmo de Rasin O. V. para comprobar el isomorfismo de los árboles de Husimi / O. V. Rasin // Noticias de la Universidad Estatal de los Urales. - 2004. - Nº 30. - S. 126-136 . Consultado el 27 de agosto de 2020. Archivado desde el original el 4 de junio de 2021.

Literatura

Enlaces