K-fa
A k -fa egy irányítatlan gráf , amelyet egy teljes gráfból alakítanak ki ( k + 1) csúcsokkal, csúcsok egymás utáni összeadásával úgy, hogy minden hozzáadott v csúcsnak pontosan k szomszédja van U , így k + 1 csúcs ( v + U csúcsok ) klikket alkotnak [1] [2] .
Leírások
k -Fák pontosan a maximális gráfok adott faszélességgel , vagyis olyan gráfok, amelyekhez nem adható él a gráf faszélességének növelése nélkül [2] . Ezek is pontosan akkordgráfok , amelyeknek mindegyik maximális klikkje azonos méretű , és mindegyik minimális klikkelválasztója is azonos méretű k [1] .
![k+1](https://wikimedia.org/api/rest_v1/media/math/render/svg/552a558062ed4c0486297b5b5531c5ee044dbd9b)
Grafikonok összekapcsolt osztályai
1-A fák ugyanazok, mint a gyökerezetlen fák . A 2-fák maximális párhuzamos-szekvenciális gráfok [3] , és tartalmaznak maximális külső síkbeli gráfokat is . A sík 3-fákat Apollonius-hálózatoknak is nevezik [4] .
A legfeljebb k faszélességű gráfok pontosan k -fák részgráfjai , ezért ezeket részleges k -fáknak nevezzük [2] .
A k -dimenziós blokkpoliéderek éleiből és csúcsaiból alkotott gráfok , vagyis az egyszerűségek lapjainak egymás utáni ragasztásával szimplexből kiinduló poliéderek , k -fák, ha [5] . Ez a ragasztási folyamat a k -fák felépítését utánozza azáltal, hogy csúcsokat ad egy klikkhez [6] . A k -fa akkor és csak akkor blokkpoliéder gráf, ha nincs három ( k + 1) csúcsú klikknek k közös csúcsa [7] .
![k \geqslant 3](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab03963b958a4370995ed27175f011a1b5ec6608)
Jegyzetek
- ↑ 12. Patil , 1986 , p. 57–64.
- ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2008 , p. 390.
- ↑ Hwang, Richards, Winter, 1992 .
- ↑ Távolságok véletlenszerű apollóni hálózati struktúrákban Archiválva 2011. július 21-én a Wayback Machine -nél , Olivier Bodini, Alexis Darrasse, Michèle Soria beszéddiái a 2008-as FPSAC-on elhangzott előadásból, elérve: 2011-03-06
- ↑ Koch és Perles, 1976 , p. 420.
- ↑ Lent, De Loera, Richter-Gebert .
- ↑ Kleinschmidt, 1976 , p. 663–667.
Irodalom
- Patil HP A k -trees szerkezetéről // Journal of Combinatorics, Information and System Sciences. - 1986. - T. 11 , sz. 2-4 . – 57–64 .
- Frank Hwang, Dana Richards, Pawel Winter. A Steiner-fa probléma. - 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 Mendez. A ritka gráfok szerkezeti tulajdonságai // Hidak építése: matematika és számítástechnika között / Martin Grötschel, Katona Gyula OH. - Springer-Verlag, 2008. - V. 19. - P. 390. - (Bolyai Társaság Matematikai Tanulmányai). — ISBN 978-3-540-85218-6 .
- Etan Koch, Micha A. Perles. A fák és a k -fák hatékonyságának lefedése // Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1976). - Utilitas Math., Winnipeg, Man., 1976. - P. 391-420. Congressus Numerantium, sz. A XVII.
- Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. Konvex 3-politópok kis háromszögleteinek megtalálásának bonyolultsága.
- Kleinschmidt Péter. Eine graphentheoretische Kennzeichnung der Stapelpolytope // Archiv der Mathematik. - 1976. - December ( 27. évf. , 1. szám ). – S. 663–667 . - doi : 10.1007/BF01224736 .