This HTML5 document contains 33 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/
n12https://books.google.com/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
n19https://web.archive.org/web/20070714201213/http:/planetmath.org/encyclopedia/
n7http://www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n18http://www.inf.fu-berlin.de/inst/pubs/
n4http://robertborgersen.info/Presentations/
n8http://planetmath.org/encyclopedia/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n11http://hu.dbpedia.org/resource/Sablon:
n17http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/
provhttp://www.w3.org/ns/prov#
n9https://web.archive.org/web/20110720134637/http:/www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/
xsdhhttp://www.w3.org/2001/XMLSchema#
n16http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Dilworth-tétel
rdfs:label
Dilworth-tétel
dct:subject
n16:Kombinatorikai_tételek n16:Perfekt_gráfok
dbo:wikiPageID
1381742
dbo:wikiPageRevisionID
20257542
dbo:wikiPageExternalLink
n4:GS-05R-1.pdf n7:10.pdf n8:DualOfDilworthsTheorem.html n9:10.pdf n12:books%3Fid=FYV6tGm3NzgC&pg=PA59 n17:VOTMSTOEAS.pdf n18:tr-b-99-05.abstract.html%7C n19:DualOfDilworthsTheorem.html
prop-hu:wikiPageUsesTemplate
n11:Citation n11:Lektor n11:Fordítás n11:Harv n11:Harvs n11:Mathworld n11:Fő n11:Harvtxt
prop-hu:authorlink
Robert P. Dilworth
prop-hu:first
Robert P.
prop-hu:last
Dilworth
prop-hu:title
Dilworth's Lemma
prop-hu:year
1950
prop-hu:urlname
DilworthsLemma
dbo:abstract
A matematika, azon belül a és kombinatorika területén a Dilworth-tétel a véges részbenrendezett halmazok szélességét jellemzi minimális láncfelbontásuk figyelembe vételével. Nevét matematikusról kapta. Egy részbenrendezett halmazban lévő antilánc páronként össze nem hasonlítható elemek alkotta részhalmaz, míg a láncban lévő elemek páronként mind összehasonlíthatók. Maximális antilánc alatt olyan antiláncot értünk, ami nem valódi részhalmaza egyetlen más antiláncnak sem. A maximális antilánc számossága nagyobb vagy egyenlő bármely más antilánc számosságánál. A részbenrendezett halmaz szélessége megegyezik maximális antiláncának számosságával. Mivel bármely antilánc legfeljebb egyetlen közös elemet tartalmaz egy lánccal, ha a halmazt fel tudjuk osztani k láncra, akkor a részbenrendezett halmaz szélességének legfeljebb k-nak kell lennie. Dilworth tétele kimondja, hogy ezt a határt minden esetben el is lehet érni: mindig létezik olyan antilánc, és a halmaz elemeinek olyan láncokra bontása, hogy a láncok száma megegyezik az antilánc elemeinek számával, és ezt a számosságot tekintjük a részbenrendezett halmaz szélességének. Legyen (P,≤) egy véges, részben rendezett halmaz, amelyben van n elemű antilánc, de nincs n+1 elemű antilánc. Ekkor P legkevesebb n darab lánccal fedhető le, azaz léteznek olyan c1, c2, ..., cn ≤ P láncok, hogy P = c1 c2 ... cn, de n-nél kevesebb láncra ez már nem igaz. A Dilworth-tétel így is kimondható: bármely véges részbenrendezett halmazban a maximális antilánc elemeinek száma megegyezik a láncok minimális számával a lehetséges láncfelbontások között. A tétel egy végtelen részbenrendezett halmazokra vonatkozó verziója szerint egy részbenrendezett halmaz szélessége pontosan akkor egyezik meg a véges w számmal, ha a halmaz w láncba felbontható, de kevesebbe nem. Duálisa a .
prov:wasDerivedFrom
wikipedia-hu:Dilworth-tétel?oldid=20257542&ns=0
dbo:wikiPageLength
18653
foaf:isPrimaryTopicOf
wikipedia-hu:Dilworth-tétel
Subject Item
dbpedia-hu:Láncfelbontás
dbo:wikiPageRedirects
dbpedia-hu:Dilworth-tétel
Subject Item
wikipedia-hu:Dilworth-tétel
foaf:primaryTopic
dbpedia-hu:Dilworth-tétel