stringtranslate.com

árbol K

El gráfico de Goldner-Harary , un ejemplo de árbol plano de 3.

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]

Clases de gráficos relacionados

1-los árboles son lo mismo que los árboles . Los 2 árboles son gráficos de series paralelas máximas , [3] e incluyen también los gráficos planos externos máximos . Los 3 árboles planos también se conocen como redes apolíneas . [4]

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

  1. ^ ab Patil, HP (1986), "Sobre la estructura de k -trees", Journal of Combinatorics, Information and System Sciences , 11 (2–4): 57–64, MR  0966069.
  2. ^ abc Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2008), "Propiedades estructurales de gráficos dispersos" (PDF) , en Grötschel, Martin ; Katona, Gyula OH (eds.), Construyendo puentes: entre las matemáticas y la informática , Estudios Matemáticos de la Sociedad Bolyai, vol. 19, Springer-Verlag, pág. 390, ISBN 978-3-540-85218-6.
  3. ^ 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, ISBN 978-0-444-89098-6.
  4. ^ 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.
  5. ^ 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.
  6. ^ 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
  7. ^ Kleinschmidt, Peter (1 de diciembre de 1976), "Eine graphentheoretische Kennzeichnung der Stapelpolytope", Archiv der Mathematik , 27 (1): 663–667, doi :10.1007/BF01224736