This HTML5 document contains 14 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n10http://www.theoremoftheday.org/CombinatorialTheory/Panarboreal/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n5http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n7http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Univerzális_gráf
rdfs:label
Univerzális gráf
dct:subject
n7:Végtelen_gráfok n7:Gráfcsaládok
dbo:wikiPageID
1411040
dbo:wikiPageRevisionID
21513521
dbo:wikiPageExternalLink
n10:TotDPanarboreal.pdf
prop-hu:wikiPageUsesTemplate
n5:Mvar n5:Math n5:Reflist
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.
prov:wasDerivedFrom
wikipedia-hu:Univerzális_gráf?oldid=21513521&ns=0
dbo:wikiPageLength
7141
foaf:isPrimaryTopicOf
wikipedia-hu:Univerzális_gráf
Subject Item
wikipedia-hu:Univerzális_gráf
foaf:primaryTopic
dbpedia-hu:Univerzális_gráf