K-albero
Nella teoria dei grafi, un k-albero è un grafo non orientato formato partendo da un grafo completo con (k+1) vertici e quindi aggiungendo ripetutamente vertici in modo tale che ogni vertice aggiunto v abbia esattamente k vicini U tali che, insieme, i k+1 vertici formati da v e U costituiscano una cricca.[1][2]
Caratterizzazioni
I k-alberi sono esattamente i grafi massimali con una treewidth pari a k ("massimale" significa che non è possibile aggiungere altri archi senza aumentare la loro treewidth).[3] Essi sono anche esattamente i grafi cordali le cui cricche massimali hanno tutte la stessa dimensione k + 1 e anche quelli per i quali tutti separatori di cricca minimi hanno anche la stessa dimensione k.[1]
Classi di grafi correlate
Gli 1-alberi sono alberi. I 2-alberi sono grafi serie-paralleli massimali,[3] e includono anche i grafi planari esterni massimali. Gli 3-alberi planari sono anche noti come reti apollinee.[4]
I grafi che hanno treewidth massima pari a k sono esattamente i sottografi di k-alberi e per tale motivo sono chiamati k-alberi parziali.[2]
I grafi formati dagli archi e dai vertici di politopi impilati k-dimensionali, politopi formati partendo da un simplesso e poi incollando ripetutamente i simplessi sulle facce del politopo, sono k-alberi quando k ≥ 3.[5] Questo processo di incollaggio imita la costruzione di k-alberi aggiungendo vertici a una cricca.[6] Un k -albero è il grafo di un politopo impilato se e solo se non ci sono tre (k + 1) cricche di vertici che hanno k vertici in comune.[7]
Note
- 1 2 Patil, H. P., On the structure of k-trees, in Journal of Combinatorics, Information and System Sciences, vol. 11, n. 2-4, 1986, pp. 57–64, MR 966069.
- 1 2 Nešetřil, Jaroslav e Ossona de Mendez, Patrice, Building Bridges: Between Mathematics and Computer Science, collana Bolyai Society Mathematical Studies, vol. 19, Springer, 2010, p. 390, ISBN 978-3-540-85218-6.
- 1 2 Frank Hwang, Dana Richards e Pawel Winter, The Steiner tree problem: a tour through graphs, algorithms, and complexity (PDF), collana Advanced lectures in mathematics, vol. 53, North-Holland, 1992, ISBN 0 444 89098 X.
- ↑ Olivier Bodini, Alexis Darrasse e Michèle Soria, Distances in random Apollonian network structures, 14 dicembre 2007, DOI:10.48550/arXiv.0712.2129.
- ↑ Koch, Etan e Perles, Micha A, Covering efficiency of trees and k-trees, in Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1976, p. 420.
- ↑ (EN) Alexander Below, Jesús A. De Loera e Jürgen Richter-Gebert, The complexity of finding small triangulations of convex 3-polytopes, in Journal of Algorithms, vol. 50, n. 2, 2004-02, pp. 134–167, DOI:10.1016/S0196-6774(03)00092-0.
- ↑ (DE) Peter Kleinschmidt, Eine graphentheoretische Kennzeichnung der Stapelpolytope, in Archiv der Mathematik, vol. 27, n. 1, 1º dicembre 1976, pp. 663–667, DOI:10.1007/BF01224736.
Collegamenti esterni
- (EN) Eric W. Weisstein, k-Tree, su MathWorld, Wolfram Research.