Diferencia entre revisiones de «Grafo cactus»

De Wikipedia, la enciclopedia libre
Ir a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Grafo cactus
(Sin diferencias)

Revisión del 17:26 14 sep 2022

Uno o varios wikipedistas están trabajando actualmente en este artículo o sección. Es posible que a causa de ello haya lagunas de contenido o deficiencias de formato.
Si quieres, puedes ayudar y editar, pero antes de realizar correcciones mayores contáctalos en sus páginas de discusión o en la del artículo para poder coordinar la redacción.
Uso de esta plantilla: {{En desarrollo|nombre de usuario|t={{sust:CURRENTTIMESTAMP}}}} o {{sust:En desarrollo}}
Un grafo cactus

En teoría de grafos, un cactus (a veces llamado árbol de cactus) es un conectividad (teoría de grafos) en el que dos cycle simples tienen como máximo un vertex en común. De manera equivalente, es un grafo conectado en el que cada arista pertenece a un ciclo simple como máximo, o (para cactus no triviales) en el que cada bloque (subgrafo máximo sin cut-vertex) es una arista o un ciclo.

Propiedades

Los cactus son grafo plano exterior. Cada pseudotree es un cactus. Un grafo no trivial es un cactus si y solo si cada block es un simple cycle o un solo borde.

La familia de grafos en los que cada component es un cactus es downwardly closed bajo operaciones menor (teoría de grafos). Esta familia de grafos se puede caracterizar por un solo forbidden minor, el grafo diamante de cuatro vértices formado al eliminar un borde del grafo completo K4.[1]​

Cactus triangular

Grafo de la amistads are triangular cacti

Un cactus triangular es un tipo especial de grafo de cactus en el que cada ciclo tiene una longitud de tres y cada borde pertenece a un ciclo. Por ejemplo, los grafo de la amistad, grafos formados a partir de una colección de triángulos unidos en un solo vértice compartido, son cactus triangulares. Además de ser grafos de cactus, los cactus triangulares también son block graph y locally linear graph.

Los cactus triangulares tienen la propiedad de permanecer unidos si se les quita algún matching; para un número dado de vértices, tienen la menor cantidad posible de aristas con esta propiedad. Cada árbol con un número impar de vértices puede convertirse en un cactus triangular añadiéndole bordes, dando un aumento mínimo con la propiedad de permanecer conectado después de la eliminación de un emparejamiento.[2]​

El cactus triangular más grande en cualquier grafo se puede encontrar en complejidad temporal usando un algoritmo para matroid parity problem. Dado que los grafos de cactus triangulares son grafo plano, el cactus triangular más grande se puede usar como una aproximación al subgrafo plano más grande, un subproblema importante en planarization. Como algoritmo de aproximación, este método tiene algoritmo de aproximación 4/9, el más conocido para el problema del subgrafo planar máximo.[3]​

El algoritmo para encontrar el cactus triangular más grande está asociado con un teorema de Lovász y Plummer que caracteriza el número de triángulos en este cactus más grande.[4]​ Lovász y Plummer consideran pares de particiones de vértices y aristas del grafo dado en subconjuntos, con la propiedad de que cada triángulo del grafo tiene dos vértices en una sola clase de partición de vértices o los tres aristas en una sola clase de grafo. partición de borde; llaman a un par de particiones con esta propiedad "válidas". Entonces el número de triángulos en el cactus triangular más grande es igual al máximo, sobre pares de particiones válidas y , de

,

donde es el número de vértices en el grafo dado y es el número de clases de vértices que cumple la clase de borde .

Recientemente, se probó un límite extremo estrecho[5]​ que mostró que dado cualquier grafo plano , siempre existe un subgrafo de cactus que contiene al menos la fracción de las caras triangulares de . Este resultado implica un análisis directo del algoritmo de aproximación 4/9 para el problema del subgrafo planar máximo sin usar la fórmula min-max anterior.

Conjetura de Rosa

Una conjetura importante relacionada con el cactus triangular es la Conjetura de Rosa, llamada así por Alexander Rosa, que dice que todos los cactus triangulares son graceful o casi elegantes.[6]​ Más precisamente

"Todos los cactus triangulares con t ≡ 0, 1 mod 4 bloques son elegantes, y aquellos con t ≡ 2, 3 mod 4 son casi elegantes".

Algoritmos y aplicaciones

Algunos facility location problem que son NP-hard para grafos generales, así como algunos otros problemas de grafos, pueden resolverse en complejidad temporal para cactus.[7]​[8]​

Dado que los cactus son casos especiales de grafo plano exterior, se pueden resolver varios problemas de optimización combinatoria en grafos en complejidad temporal.[9]​

Los cactus representan circuito que tienen propiedades útiles. Una de las primeras aplicaciones de cactus se asoció con la representación de amplificadores operacionales.[10]​[11]​[12]​

Los cactus también se han utilizado en genómica comparativa como una forma de representar la relación entre diferentes genomas o partes de genomas.[13]​

Si un cactus está conectado, y cada uno de sus vértices pertenece como máximo a dos bloques, entonces se llama cactus de Navidad. Cada grafo poliédrico tiene un subgrafo de cactus navideño que incluye todos sus vértices, un hecho que juega un papel esencial en una prueba de Leighton y Moitra (2010) de que cada grafo poliédrico tiene un greedy embedding en el Bidimensional, una asignación de coordenadas a los vértices para los cuales greedy forwarding logra enrutar mensajes entre todos los pares de vértices.[14]​

En teoría de grafos topológica, los grafos cuyos cellular embeddings son todos planar son exactamente la subfamilia de los grafos de cactus con la propiedad adicional de que cada vértice pertenece como máximo a un ciclo. Estos grafos tienen dos menores prohibidos, el grafo de diamante y el grafo de la amistad de cinco vértices.[15]​

Historia

Los cactus se estudiaron por primera vez con el nombre de árboles Husimi, otorgados por Frank Harary y George Eugene Uhlenbeck en honor al trabajo previo de Kôdi Husimi en estos grafos.[16]​[17]​ El mismo artículo de Harary-Uhlenbeck reserva el nombre de "cactus" para grafos de este tipo en los que cada ciclo es un triángulo, pero ahora se permiten ciclos de cualquier longitud como estándar.

Mientras tanto, el nombre árbol de Husimi comúnmente vino a referirse a grafos en los que cada block es un grafo completo (equivalentemente, los grafos de intersección de los bloques en algún otro grafo). Este uso tuvo poco que ver con el trabajo de Husimi, y ahora se usa el término más pertinente block graph para esta familia; sin embargo, debido a esta ambigüedad, esta frase se usa con menos frecuencia para referirse a los grafos de cactus.[18]​

Referencias

  1. ↑ El-Mallah, Ehab; Colbourn, Charles J. (1988), «The complexity of some edge deletion problems», IEEE Transactions on Circuits and Systems 35 (3): 354-362, doi:10.1109/31.1748 .
  2. ↑ Farley, Arthur M.; Proskurowski, Andrzej (1982), «Networks immune to isolated line failures», Networks 12 (4): 393-403, MR 686540, doi:10.1002/net.3230120404 .
  3. ↑ Călinescu, Gruia; Fernandes, Cristina G; Finkler, Ulrich; Karloff, Howard (2002), «A Better Approximation Algorithm for Finding Planar Subgraphs», Journal of Algorithms, 2 27 (2): 269-302, S2CID 8329680, doi:10.1006/jagm.1997.0920, «citeseerx: 10.1.1.47.4731» .
  4. ↑ Lovász, L.; Plummer, M.D. (2009), Matching Theory, AMS Chelsea Publishing Series, ISBN 9780821847596 .
  5. ↑ Chalermsook, Parinya; Schmid, Andreas; Uniyal, Sumedha (2019), «A tight extremal bound on the Lovász cactus number in planar graphs», en Niedermeier, Rolf; Paul, Christophe, eds., 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, LIPIcs 126, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 19:1-19:14, arXiv:1804.03485, doi:10.4230/LIPIcs.STACS.2019.19 .
  6. ↑ Rosa, A. (1988), «Cyclic Steiner Triple Systems and Labelings of Triangular Cacti», Scientia 1: 87-95 ..
  7. ↑ Ben-Moshe, Boaz; Bhattacharya, Binay; Shi, Qiaosheng (2005), «Efficient algorithms for the weighted 2-center problem in a cactus graph», Algorithms and Computation, 16th Int. Symp., ISAAC 2005, Lecture Notes in Computer Science 3827, Springer-Verlag, pp. 693-703, ISBN 978-3-540-30935-2, doi:10.1007/11602613_70 .
  8. ↑ Zmazek, Blaz; Zerovnik, Janez (2005), «Estimating the traffic on weighted cactus networks in linear time», Ninth International Conference on Information Visualisation (IV'05), pp. 536-541, ISBN 978-0-7695-2397-2, S2CID 15963409, doi:10.1109/IV.2005.48 .
  9. ↑ Korneyenko, N. M. (1994), «Combinatorial algorithms on a class of graphs», Discrete Applied Mathematics 54 (2–3): 215-217, doi:10.1016/0166-218X(94)90022-1. . Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109-111 (en ruso)
  10. ↑ Nishi, Tetsuo; Chua, Leon O. (1986), «Topological proof of the Nielsen-Willson theorem», IEEE Transactions on Circuits and Systems 33 (4): 398-405, doi:10.1109/TCS.1986.1085935 .
  11. ↑ Nishi, Tetsuo; Chua, Leon O. (1986), «Uniqueness of solution for nonlinear resistive circuits containing CCCS's or VCVS's whose controlling coefficients are finite», IEEE Transactions on Circuits and Systems 33 (4): 381-397, doi:10.1109/TCS.1986.1085934 .
  12. ↑ Nishi, Tetsuo (1991), «On the number of solutions of a class of nonlinear resistive circuit», Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore, pp. 766-769 .
  13. ↑ Paten, Benedict; Diekhans, Mark; Earl, Dent; St. John, John; Ma, Jian; Suh, Bernard; Haussler, David (2010), «Cactus Graphs for Genome Comparisons», Research in Computational Molecular Biology, Lecture Notes in Computer Science 6044, pp. 410–425, ISBN 978-3-642-12682-6, doi:10.1007/978-3-642-12683-3_27 .
  14. ↑ Leighton, Tom; Moitra, Ankur (2010), «Some Results on Greedy Embeddings in Metric Spaces», Discrete & Computational Geometry 44 (3): 686-705, S2CID 11186402, doi:10.1007/s00454-009-9227-6 ..
  15. ↑ Nordhaus, E. A.; Ringeisen, R. D.; Stewart, B. M.; White, A. T. (1972), «A Kuratowski-type theorem for the maximum genus of a graph», Journal of Combinatorial Theory, Series B 12 (3): 260-267, MR 0299523, doi:10.1016/0095-8956(72)90040-8 .
  16. ↑ Harary, Frank; Uhlenbeck, George E. (1953), «On the number of Husimi trees, I», Proceedings of the National Academy of Sciences 39 (4): 315-322, Bibcode:1953PNAS...39..315H, MR 0053893, PMC 1063779, PMID 16589268, doi:10.1073/pnas.39.4.315 .
  17. ↑ Husimi, Kodi (1950), «Note on Mayers' theory of cluster integrals», Journal of Chemical Physics 18 (5): 682-684, Bibcode:1950JChPh..18..682H, MR 0038903, doi:10.1063/1.1747725 .
  18. ↑ See, e.g., MR 0659742, a 1983 review by Robert E. Jamison of a paper using the other definition, which attributes the ambiguity to an error in a book by Mehdi Behzad and Gary Chartrand.

Enlaces externos

Obtenido de «https://es.wikipedia.org/w/index.php?title=Grafo_cactus&oldid=145964629»