Gráfelméletben egy adott gráfban fellelhető egymástól diszjunkt fák létezése, keresése közismert probléma. A terület fontosabb eredményeiként gyakran emlegetett példák Tutte és Nash-Williams tételeik k-éldiszjunkt feszítőfa létezéséről, Nash-Williams tétele az élek particionálhatóságáról diszjunkt erdőkre, továbbá több esetben is elmondható, hogy a vizsgált speciális tulajdonságú részgráfok, vagy azok minimális-, esetleg maximális száma algoritmussal kereshető.
Ezek, és ezekhez hasonló kérdések merülhetnek fel hipergráfok esetében is.
A projekt célja az ilyen tételek, állítások megismerése, megértése, lehetséges további kutatási irányok körbejárása.
A témában elérhető eredmények főként gráfelméleti és matroidelméleti alapokra támaszkodnak, ezek egy részének elsajátítása szintén a projekt feladataihoz tartozik.
Hivatkozások
- Bérczi-Kovács, E. and Frank, A. (2026), How to see the forest despite the trees. J. London Math. Soc., 114: e70668. https://doi.org/10.1112/jlms.70668
- A. Frank, T. Király, M. Kriesell, On decomposing a hypergraph into k connected sub-hypergraphs, Discrete Applied Mathematics 131 (2003), 373-383.
- T. Király, Edge-connectivity of undirected and directed hypergraphs, Ph.D. dissertation (2004).