| dbo:abstract
|
- 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 vagy véletlen gráfnak is nevezik. Újabbanaz 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, ezért egy hiperkockát tekinthetünk 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. 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. A kimondja, hogy a a 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. 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 ), 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. A korábbi matematikai terminológiában az „univerzális gráf” kifejezésen néha a teljes gráfot értették. (hu)
- 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 vagy véletlen gráfnak is nevezik. Újabbanaz 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, ezért egy hiperkockát tekinthetünk 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. 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. A kimondja, hogy a a 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. 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 ), 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. A korábbi matematikai terminológiában az „univerzális gráf” kifejezésen néha a teljes gráfot értették. (hu)
|
