Árbol K

Un k -árbol es un grafo no dirigido formado a partir de un grafo completo con ( k  + 1) vértices, con sumas sucesivas de vértices tales que cada vértice v agregado tiene exactamente k vecinos U tales que k  + 1 vértices (vértice v + vértices U ) formar una camarilla [1] [2] .

Descripciones

k -Trees son exactamente los gráficos máximos con un ancho de árbol dado , es decir, gráficos a los que no se les puede agregar un borde sin aumentar el ancho de árbol del gráfico [2] . Estos son también grafos exactamente cordales , todos cuyos cliques máximos son del mismo tamaño y todos cuyos separadores de clique mínimos también son del mismo tamaño k [1] .

Clases conectadas de grafos

1-Los árboles son lo mismo que los árboles sin raíz . Los 2 árboles son gráficos secuenciales paralelos máximos [3] y también incluyen gráficos planos exteriores máximos . Los 3 árboles planos también se conocen como redes de Apolonio [4] .

Los grafos que tienen un ancho de árbol como máximo k son exactamente subgrafos de k -árboles, y por esta razón se denominan k -árboles parciales [2] .

Los grafos formados por aristas y vértices de poliedros de bloques k -dimensionales , es decir, poliedros formados, a partir de un simplex , por pegado sucesivo de caras de simples, son k -trees si [5] . Este proceso de pegado imita la construcción de k -árboles al agregar vértices a una camarilla [6] . Un árbol k es un grafo de poliedro de bloques si y solo si no hay tres cliques con ( k  + 1) vértices que tengan k vértices comunes [7] .

Notas

1. ↑ 12 Patil , 1986 , pág. 57–64.
2. ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2008 , p. 390.
3. ↑ Hwang, Richards, Invierno, 1992 .
4. ↑ Distancias en estructuras de red apolíneas aleatorias Archivado el 21 de julio de 2011 en Wayback Machine , diapositivas de charlas de Olivier Bodini, Alexis Darrasse, Michèle Soria de una charla en FPSAC 2008, consultado el 6 de marzo de 2011
5. ↑ Koch y Perles, 1976 , pág. 420.
6. ↑ A continuación, De Loera, Richter-Gebert .
7. ↑ Kleinschmidt, 1976 , pág. 663–667.

Literatura

• Patil HP Sobre la estructura de k -trees // Journal of Combinatorics, Information and System Sciences. - 1986. - T. 11 , núm. 2-4 . — págs. 57–64 .
• Frank Hwang, Dana Richards, Pawel Winter. El problema del árbol de Steiner. - Elsevier, 1992. - V. 53. - P. 177. - (Annals of Discrete Mathematics (North-Holland Mathematics Studies)). - ISBN 978-0-444-89098-6 .
• Jaroslav Nešetřil, Patrice Ossona de Méndez. Propiedades estructurales de gráficos dispersos // Construyendo puentes: entre las matemáticas y la informática / Martin Grötschel, Gyula OH Katona. - Springer-Verlag, 2008. - V. 19. - P. 390. - (Estudios Matemáticos de la Sociedad Bolyai). — ISBN 978-3-540-85218-6 .
• Etan Koch, Micha A. Perles. Cobertura de la eficiencia de árboles y árboles k // Actas de la Séptima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad del Estado de Luisiana, Baton Rouge, Luisiana, 1976). - Utilitas Math., Winnipeg, Man., 1976. - P. 391-420. Congreso Numerantium, n. XVII.
• Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. La complejidad de encontrar pequeñas triangulaciones de 3-politopos convexos.
• Peter Kleinschmidt. Eine graphentheoretische Kennzeichnung der Stapelpolytope // Archiv der Mathematik. - 1976. - Diciembre ( vol. 27 , número 1 ). — S. 663–667 . -doi : 10.1007/ BF01224736 .