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 nevéhez fűződik, ezért Rado-gráfnak vagy véletlen gráfnak is nevezik.  Újabban

az egyes  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 -be tartozó véges gráfot. Például a Henson-gráfok univerzálisak ilyen értelemben az -klikkmentes gráfokra nézve.

Egy  gráfcsaládhoz tartozó univerzális gráf jelentheti véges gráfok minden -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, 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  csúcsú fákhoz, melynek mindössze  csúcsa és  éle van, és ez a gráf optimális. Egy a síkgráf-felbontási tételen alapuló konstrukció segítségével megmutatható, hogy az  csúcsú síkgráfoknak vannak univerzális gráfjai  éllel, és hogy a korlátos fokú síkgráfoknak léteznek univerzális gráfjai  éllel. A Sumner-sejtés kimondja, hogy a tournamentek a polifák univerzális gráfjai, abban az értelemben, hogy minden  csúcsú tournament tartalmazza az összes  csúcsú polifát részgráfjaként.

Egy  gráfcsaládnak akkor és csak akkor létezik polinomiális méretű univerzális gráfja, mely minden  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  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 -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.

A korábbi matematikai terminológiában az „univerzális gráf” kifejezésen néha a teljes gráfot értették.

Jegyzetek

További információk
The panarborial formula, "Theorem of the Day" concerning universal graphs for trees

Gráfcsaládok
Végtelen gráfok
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 nevéhez fűződik , ezért Rado-gráfnak vagy véletlen gráfnak is nevezik . Újabban az egyes 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 -be tartozó véges gráfot . Például a Henson-gráfok univerzálisak ilyen értelemben az -klikkmentes gráfokra nézve . Egy gráfcsaládhoz tartozó univerzális gráf jelentheti véges gráfok minden -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 , 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 csúcsú fákhoz , melynek mindössze csúcsa és éle van , és ez a gráf optimális . Egy a síkgráf-felbontási tételen alapuló konstrukció segítségével megmutatható , hogy az csúcsú síkgráfoknak vannak univerzális gráfjai éllel , és hogy a korlátos fokú síkgráfoknak léteznek univerzális gráfjai éllel . A Sumner-sejtés kimondja , hogy a tournamentek a polifák univerzális gráfjai , abban az értelemben , hogy minden csúcsú tournament tartalmazza az összes csúcsú polifát részgráfjaként . Egy gráfcsaládnak akkor és csak akkor létezik polinomiális méretű univerzális gráfja , mely minden 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 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 -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 . A korábbi matematikai terminológiában az „ univerzális gráf” kifejezésen néha a teljes gráfot értették . Jegyzetek További információk The panarborial formula , " Theorem of the Day " concerning universal graphs for trees Gráfcsaládok Végtelen gráfok