This HTML5 document contains 23 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/
n13http://home.cc.umanitoba.ca/~umborger/Presentations/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n14http://hu.dbpedia.org/resource/Sablon:
owlhttp://www.w3.org/2002/07/owl#
n6http://www.cut-the-knot.org/arithmetic/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n5http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Hall-tétel
rdfs:label
Hall-tétel
owl:sameAs
freebase:m.019kt3
dct:subject
n5:Kombinatorika n5:Kombinatorikai_tételek n5:Matematikai_tételek n5:Párosítás
dbo:wikiPageID
327735
dbo:wikiPageRevisionID
20997491
dbo:wikiPageExternalLink
n6:marriage.shtml n6:elegant.shtml n13:GS-05R-1.pdf
prop-hu:wikiPageUsesTemplate
n14:Halott_link n14:Planetmath n14:Portál
prop-hu:date
2019
prop-hu:id
3059
prop-hu:title
proof of Hall's marriage theorem
prop-hu:url
n13:GS-05R-1.pdf
dbo:abstract
A matematikában a Hall-tétel (1935, ) egy kombinatorikai állítás, ami feltételt ad arra, hogy mikor lehet kiválasztani egy adott halmaz valahány nem feltétlenül diszjunkt részhalmazából különböző elemeket. Legyen S = {S1, S2, … } egy (nem feltétlenül megszámlálható) halmaza egy M halmaz véges részhalmazainak. A diszjunkt reprezentáns rendszer (innentől DRR) egy olyan X = {x1, x2, …} halmaza M-beli páronként diszjunkt elemeknek, melyekre |X| = |S|, és minden i-re xi eleme Si-nek teljesül. Az S halmaz teljesíti a Hall-feltételt, ha S minden T = {Ti } részhalmazára: (vagyis bármely n részhalmaz együtt legalább n elemből áll) A Hall-tétel azt állítja, hogy akkor és csak akkor létezik diszjunkt reprezentáns rendszer X = {xi}, ha S teljesíti a Hall-feltételt. Például: Legyen S1 = {1, 2, 3}, S2 = {1, 4, 5}, S3 = {3, 5}. Erre az S = {S1, S2, S3} halmazra, egy megfelelő DRR az {1, 4, 5} (Nem csak ez az egy DRR lehetséges: a {2, 1, 3} ugyanúgy jó lenne). A leggyakoribb példa a Hall-tétel alkalmazására, ha elképzelünk egy-egy n tagú férfiakból, illetve nőkből álló csoportot. Minden nő boldogan hozzámenne a férfiak egy bizonyos részhalmazához, és minden férfi boldogan elvenne bármely nőt, aki hozzá akarna menni. Gondoljuk meg, mikor lenne lehetséges úgy összeházasítani a férfiakat a nőkkel, hogy mindenki boldog legyen. Ha Mi lesz az a halmaza a férfiaknak, akikkel az i-edik nő boldogan összeházasodna, akkor a tétel állítása szerint akkor és csak akkor tudna minden nő boldogan férjhez menni, ha az {Mi} halmazok halmaza kielégíti a Hall-feltételt. A Hall-feltétel jelen esetben bármely részhalmazára a nőknek, azon férfiak száma, akik az -beli nők közül legalább egyet elvennének legyen legalább akkora, mint a nők ezen részhalmazának elemszáma, . Az természetes, hogy a feltétel szükséges, hiszen enélkül nem lenne elég az -beli nők között szétosztható férfi. Annál érdekesebb, hogy a feltétel elégséges is. A tételnek vannak egyéb alkalmazásai is. Például vegyünk egy csomag francia kártyát, és osszuk szét őket 13 darab csoportba, minden csoportba 4-et téve. Ezek után a Hall-tételt használva láthatjuk, hogy lehetséges minden csoportból 1-1 kártyát úgy kiválasztani, hogy a 13 kiválasztott kártya közül minden kártyaértékből pontosan 1 szerepeljen (ász, 2, 3, …, dáma, király). Absztraktabb példaként legyen G egy csoport és H egy véges részcsoportja G-nek. Ekkor a tétel segítségével megmutathatjuk, hogy létezik olyan X halmaz, ami egyaránt DRR-je a H G-beli jobb és bal oldali mellékosztályainak. A tétel a megbízatási problémára is alkalmazható: Adott n alkalmazott halmaza, és mindhez egy lista, hogy kit mire lehet alkalmazni. Akkor és csak akkor tudunk mindenkinek a képességeihez megfelelő munkát adni, ha k (1…n) minden értékére bármely k db lista összesen legalább k db munkát tartalmaz. A még általánosabb problémára, melyben (nem feltétlenül különböző) elemeket kell kiválasztani halmazok egy halmazából, általában csak a csoportaxiómákat feltéve alkalmazhatjuk.
prov:wasDerivedFrom
wikipedia-hu:Hall-tétel?oldid=20997491&ns=0
dbo:wikiPageLength
9223
foaf:isPrimaryTopicOf
wikipedia-hu:Hall-tétel
Subject Item
wikipedia-hu:Hall-tétel
foaf:primaryTopic
dbpedia-hu:Hall-tétel