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.
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. 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..
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,. 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.Distances in random Apollonian network structures , talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06.
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..
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.. Lásd főleg a 420. oldalt Ez a ragasztási folyamat a k-fák konstrukcióját utánozza, ahol csúcsokat adunk egy klikkhez.. 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.
Fordítás
Jegyzetek
Kategória:Gráfminorok Kategória:Fák (gráfelmélet) Kategória:Perfekt gráfok Kategória:Gráfcsaládok