This HTML5 document contains 18 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#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n8http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n11http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Erdős–Pósa-tétel
rdfs:label
Erdős–Pósa-tétel
dct:subject
n11:Erdős_Pál n11:Gráfelméleti_tételek
dbo:wikiPageID
1592880
dbo:wikiPageRevisionID
20707492
prop-hu:wikiPageUsesTemplate
n8:Mvar n8:Math n8:Fordítás n8:Refend n8:Refbegin n8:Cite_journal n8:Harvtxt
dbo:abstract
A matematika, azon belül a gráfelmélet területén az Erdős Pálról és Pósa Lajosról elnevezett Erdős–Pósa-tétel kimondja, hogy létezik egy f(k) függvény, hogy minden k pozitív egész számra minden gráf vagy tartalmaz k csúcsdiszjunkt kört, vagy f(k) méretű körlefogó csúcshalmazt, ami a gráf minden köréből tartalmaz csúcsot. Továbbá, f(k) = O(k log k) az O jelölés szerint. A tétel miatt szokás azt mondani körökre, hogy „rendelkeznek az Erdős–Pósa-tulajdonsággal”. A tétel állítása szerint bármely véges k számra létezik olyan (legkisebb) f(k) érték, amire igaz, hogy minden, k csúcsdiszjunkt kört nem tartalmazó gráf körei lefedhetők f(k) csúccsal. Ez Bollobás Béla publikálatlan eredményét általánosította, ami szerint f(2) = 3. az általános esetre a c1k log k < f(k) < c2k log k korlátokat bizonyították. Az eredményből következik, hogy bár végtelen sok különböző gráf van, amiben nincsen k diszjunkt kör, ezek mégis véges sok, egyszerűen leírható osztályba sorolhatók. A k = 2 esetre teljes leírást adott. bizonyította, hogy f(3) = 6 és 9 ≤ f(4) ≤ 12.
prov:wasDerivedFrom
wikipedia-hu:Erdős–Pósa-tétel?oldid=20707492&ns=0
dbo:wikiPageLength
3644
foaf:isPrimaryTopicOf
wikipedia-hu:Erdős–Pósa-tétel
Subject Item
dbpedia-hu:Erdős–Pósa-tulajdonság
dbo:wikiPageRedirects
dbpedia-hu:Erdős–Pósa-tétel
Subject Item
wikipedia-hu:Erdős–Pósa-tétel
foaf:primaryTopic
dbpedia-hu:Erdős–Pósa-tétel