K-fa

Egy síkbarajzolható 3-fa, a Goldner–Harary-gráf.

A matematika, azon belül a gráfelmélet területén egy k-fa olyan irányítatlan gráf, ami megkapható egy (k + 1) csúcsú teljes gráfból kiindulva csúcsok ismételt hozzáadásával úgy, hogy minden hozzáadott v csúcsnak egy U csúcshalmazt alkotó pontosan k szomszédja van, melyre igaz, hogy a v és U által együtt alkotott k + 1 csúcs egy klikket alkot.[1][2]

Karakterizációk

A k-fák megegyeznek az adott faszélességű maximális gráfokkal, tehát azokkal a gráfokkal, melyekhez nem adható hozzá új él a faszélességük növelése nélkül.[2] Megegyeznek továbbá azokkal a merev körű gráfokkal, melyek maximális klikkjei szintén k + 1 méretűek, minimális klikkszeparátoraik pedig mind k méretűek.[1]

Kapcsolódó gráfcsaládok

Az 1-fák ugyanazok, mint a gyökér nélküli fák. A 2-fák a maximális soros-párhuzamos gráfok,[3] melyek közé tartoznak a maximális külsíkgráfok is. A síkba rajzolható 3-fákat Apollóniusz-hálózatoknak is nevezik.[4]

A legfeljebb k faszélességű gráfok megegyeznek a k-fák részgráfjaival, ezért részleges k-fáknak nevezik őket.[2]

A k-dimenziós halmozott politópok (stacked polytopes, egy szimplexből kiindulva a politóp hiperlapjaihoz ismételten szimplexek ragasztásával kapott politópok) éleiből és csúcsaiból álló gráfok k-fák, amennyiben k ≥ 3.[5] Ez a ragasztási folyamat a k-fák konstrukcióját utánozza, ahol csúcsokat adunk egy klikkhez.[6] Egy k-fa pontosan akkor a gráfja egy halmozott politópnak, ha a gráf semelyik három (k + 1)-csúcsú klikkjének nincs k közös csúcsa.[7]

Fordítás

• Ez a szócikk részben vagy egészben a K-tree című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences 11 (2-4): 57–64.
2. Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2008), "Structural Properties of Sparse Graphs", Building Bridges: between Mathematics and Computer Science, vol. 19, Bolyai Society Mathematical Studies, Springer-Verlag, p. 390, ISBN 978-3-540-85218-6.
3. Hwang, Frank; Richards, Dana & Winter, Pawel (1992), The Steiner Tree Problem, vol. 53, Annals of Discrete Mathematics (North-Holland Mathematics Studies), Elsevier, p. 177, ISBN 978-0-444-89098-6.
4. Distances in random Apollonian network structures Archiválva 2011. július 21-i dátummal a Wayback Machine-ben, talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06.
5. Koch, Etan & Perles, Micha A. (1976), "Covering efficiency of trees and k-trees", Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., pp. 391–420. Congressus Numerantium, No. XVII. Lásd főleg a 420. oldalt
6. Below, Alexander; De Loera, Jesús A.; Richter-Gebert, Jürgen. "The Complexity of Finding Small Triangulations of Convex 3-Polytopes". arXiv:math/0012177..
7. Kleinschmidt, Peter (1976. december 1.). „Eine graphentheoretische Kennzeichnung der Stapelpolytope”. Archiv der Mathematik 27 (1), 663–667. o. DOI:10.1007/BF01224736.