En la teoría de grafos , un árbol k es un grafo no dirigido formado al comenzar con un grafo completo de vértice ( k + 1) y luego agregar vértices repetidamente de tal manera que cada vértice agregado v tenga exactamente k vecinos U tales que, juntos, los k + 1 vértices formados por v y U forman una camarilla . [1] [2]
Caracterizaciones
Los k -árboles son exactamente los gráficos máximos con un ancho de árbol de k ("máximo" significa que no se pueden agregar más bordes sin aumentar su ancho de árbol). [2] También son exactamente las gráficas cordales, todas cuyas camarillas máximas son del mismo tamaño k + 1 y todos cuyos separadores de camarillas mínimas también son del mismo tamaño k . [1]
Clases de grafos relacionados
Los árboles 1 son lo mismo que los árboles sin raíz . 2-árboles son gráficos de series paralelas máximas , [3] e incluyen también los gráficos planos externos máximos . Los árboles planos 3 también se conocen como redes apolíneas . [4]
Los gráficos que tienen treewidth como máximo k son exactamente los subgrafos de k -Los árboles, y por esta razón se les llama parciales k -Los árboles . [2]
Los gráficos formados por los bordes y vértices de politopos apilados k -dimensionales , politopos formados partiendo de un simplex y luego pegando repetidamente simples en las caras del politopo, son k -árboles cuando k ≥ 3. [5] Este proceso de encolado imita la construcción de k -árboles agregando vértices a una camarilla. [6] Un árbol k es la gráfica de un politopo apilado si y solo si no hay tres camarillas de vértices ( k + 1) que tengan k vértices en común. [7]
Referencias
- ↑ a b Patil, HP (1986), "Sobre la estructura de los árboles k ", Journal of Combinatorics, Information and System Sciences , 11 (2-4): 57-64, MR 0966069.
- ^ a b c Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2008), "Propiedades estructurales de los gráficos dispersos" (PDF) , en Grötschel, Martin ; Katona, Gyula OH (eds.), Building Bridges: between Mathematics and Computer Science , Bolyai Society Mathematical Studies, 19 , Springer-Verlag, p. 390, ISBN 978-3-540-85218-6.
- ^ Hwang, Frank; Richards, Dana; Winter, Pawel (1992), El problema del árbol de Steiner , Annals of Discrete Mathematics (Estudios de matemáticas de Holanda Septentrional), 53 , Elsevier, p. 177, ISBN 978-0-444-89098-6.
- ^ Distancias en estructuras de red apolínea aleatorias Archivado el21 de julio de 2011en la Wayback Machine , diapositivas de charlas de Olivier Bodini, Alexis Darrasse y Michèle Soria de una charla en FPSAC 2008, consultado el 6 de marzo de 2011.
- ^ Koch, Etan; Perles, Micha A. (1976), "Cubriendo la eficiencia de los árboles y k -trees", Actas de la Séptima Conferencia Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Louisiana State Univ., Baton Rouge, La., 1976) , Utilitas Math., Winnipeg, Man., Págs. 391–420. Congressus Numerantium, No. XVII, MR 0457265. Ver en particular la p. 420.
- ^ Abajo, Alejandro; De Loera, Jesús A .; Richter-Gebert, Jürgen. "La complejidad de encontrar pequeñas triangulaciones de 3-politopos convexos". arXiv : matemáticas / 0012177 ..
- ^ Kleinschmidt, Peter (1 de diciembre de 1976). "Eine graphentheoretische Kennzeichnung der Stapelpolytope". Archiv der Mathematik . 27 (1): 663–667. doi : 10.1007 / BF01224736 .