En teoría de grafos , un k -árbol es un gráfico no dirigido formado comenzando con un gráfico completo de ( k + 1)-vértice y luego agregando vértices repetidamente de tal manera que cada vértice agregado v tenga exactamente k vecinos U tales que, juntos, los vértices k +1 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 los gráficos cordales, todos cuyos camarillas máximas son del mismo tamaño k + 1 y todos cuyos separadores de camarilla mínimos también son del mismo tamaño k . [1]
Los gráficos que tienen un ancho de árbol como máximo k son exactamente los subgrafos de k -árboles y por esta razón se llaman k -árboles parciales . [2]
Los gráficos formados por los bordes y vértices de politopos apilados de k dimensiones , politopos formados comenzando desde un simplex y luego pegando repetidamente simples en las caras del politopo, son k -árboles cuando k ≥ 3. [5] Este proceso de pegado imita la construcción de k -trees agregando vértices a una camarilla. [6] Un k -árbol es el gráfico de un politopo apilado si y sólo si no hay tres camarillas de ( k + 1) vértices que tengan k vértices en común. [7]
Referencias
^ ab Patil, HP (1986), "Sobre la estructura de k -trees", Journal of Combinatorics, Information and System Sciences , 11 (2–4): 57–64, MR 0966069.
^ Hwang, Frank; Richards , Dana; Winter, Pawel (1992), The Steiner Tree Problem , Annals of Discrete Mathematics (Estudios de matemáticas de Holanda Septentrional), vol. 53, Elsevier, pág. 177, ISBN978-0-444-89098-6.
^ Distancias en estructuras de redes apolíneas aleatorias Archivado el 21 de julio de 2011 en Wayback Machine , diapositivas de charla 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), "Cobertura de eficiencia de árboles y k -árboles", Actas de la Séptima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Louisiana State Univ., Baton Rouge, Luisiana, 1976) , Utilitas Math., Winnipeg, Man., págs. 391–420. Congreso Numerantium, nº XVII, MR 0457265. Véase en particular la pág. 420.
^ Abajo, Alejandro; De Loera, Jesús A .; Richter-Gebert, Jürgen (febrero de 2004), "La complejidad de encontrar pequeñas triangulaciones de 3 politopos convexos", Journal of Algorithms , 50 (2): 134–167, arXiv : math/0012177 , doi :10.1016/s0196-6774 (03)00092-0
^ Kleinschmidt, Peter (1 de diciembre de 1976), "Eine graphentheoretische Kennzeichnung der Stapelpolytope", Archiv der Mathematik , 27 (1): 663–667, doi :10.1007/BF01224736