Univerzális gráf
A matematika, azon belül a gráfelmélet területén az univerzális gráf olyan végtelen gráf, ami minden véges (vagy megszámlálható) gráfot tartalmaz feszített részgráfjaként. Az első ilyen univerzális gráf konstrukciója R. Rado[1][2] nevéhez fűződik, ezért Rado-gráfnak vagy véletlen gráfnak is nevezik. Újabban[3] [4] az egyes F gráfcsaládokhoz tartozó univerzális gráfok kutatása került előtérbe: tehát olyan, az F-hez tartozó végtelen gráfokról van szó, melyek tartalmazzák az összes F-be tartozó véges gráfot. Például a Henson-gráfok univerzálisak ilyen értelemben az i-klikkmentes gráfokra nézve.
Egy F gráfcsaládhoz tartozó univerzális gráf jelentheti véges gráfok minden F-ben lévő gráfot tartalmazó sorozatának egy tagját; például minden véges fa egy elegendően nagy hiperkockagráf részgráfja,[5] ezért egy hiperkocka tekinthető a fák univerzális gráfjának is. Nem létezik azonban legkisebb ilyen tulajdonságú gráf: tudjuk, hogy létezik egy univerzális gráf az n csúcsú fákhoz, melynek mindössze n csúcsa és O(n log n) éle van, és ez a gráf optimális.[6] Egy a síkgráf-felbontási tételen alapuló konstrukció segítségével megmutatható, hogy az n csúcsú síkgráfoknak vannak univerzális gráfjai O(n3/2) éllel, és hogy a korlátos fokú síkgráfoknak léteznek univerzális gráfjai O(n log n) éllel.[7][8][9] A Sumner-sejtés kimondja, hogy a tournamentek a polifák univerzális gráfjai, abban az értelemben, hogy minden 2n − 2 csúcsú tournament tartalmazza az összes n csúcsú polifát részgráfjaként.[10]
Egy F gráfcsaládnak akkor és csak akkor létezik polinomiális méretű univerzális gráfja, mely minden n csúcsú gráfot feszített részgráfként tartalmaz, ha tartozik hozzá olyan szomszédság-címkézési séma (lásd implicit gráf), melyben a csúcsok úgy címkézhetők O(log n) bites bitfüzérekkel, hogy egy algoritmus a címkék vizsgálatával képes legyen eldönteni, hogy két csúcs szomszédos-e. Ha ilyen univerzális gráf létezik, bármely F-beli gráf csúcsai címkézhetők az univerzális gráf megfelelő csúcsainak identitásaival, és megfordítva, ha egy ilyen címkézési séma létezik, akkor egy univerzális gráf konstruálható, mely minden lehetséges címkéhez rendelkezik egy megfelelő csúccsal.[11]
A korábbi matematikai terminológiában az „univerzális gráf” kifejezésen néha a teljes gráfot értették.
Jegyzetek
[szerkesztés]- ↑ Rado, R. (1964). „Universal graphs and universal functions”. Acta Arithmetica 9, 331–340. o.
- ↑ Rado, R. (1967. december 2.). „Universal graphs”. A Seminar in Graph Theory: 83–85, Holt, Rinehart, and Winston.
- ↑ (1996) „Universal arrow-free graphs”. Acta Mathematica Hungarica 1973 (4), 319–326. o. DOI:10.1007/BF00052907.
- ↑ (1999) „Universal graphs with forbidden subgraphs and algebraic closure”. Advances in Applied Mathematics 22 (4), 454–491. o. DOI:10.1006/aama.1998.0641.
- ↑ Wu, A. Y. (1985). „Embedding of tree networks into hypercubes”. Journal of Parallel and Distributed Computing 2 (3), 238–249. o. DOI:10.1016/0743-7315(85)90026-7.
- ↑ (1983) „On universal graphs for spanning trees”. Journal of the London Mathematical Society 27 (2), 203–211. o. DOI:10.1112/jlms/s2-27.2.203..
- ↑ Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday, Annals of Discrete Mathematics, 21–26. o. (1982)
- ↑ (1989) „Universal graphs for bounded-degree trees and planar graphs”. SIAM Journal on Discrete Mathematics 2 (2), 145. o. DOI:10.1137/0402014.
- ↑ Chung, Fan R. K.. Paths, Flows, and VLSI-Layout, Algorithms and Combinatorics. Springer-Verlag, 17–34. o. (1990). ISBN 978-0-387-52685-0
- ↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
- ↑ Kannan, Sampath; Naor, Moni & Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics 5 (4): 596–603, DOI 10.1137/0405049.
További információk
[szerkesztés]- The panarborial formula, "Theorem of the Day" concerning universal graphs for trees