Teorema dell'accoppiamento di Hall
Inviato: 13 mar 2006, 08:02
Teorema dell'accoppiamento di Hall (o lemma del matrimonio)
Siano dati un insieme di uomini e un insieme di donne. Alcune coppie (uomo, donna) sono "compatibili", ovvero si piacciono reciprocamente e non disdegnerebbero sposarsi. Un uomo può essere compatibile con più donne o con nessuna donna, e viceversa. Vorremmo poter organizzare dei matrimoni tra persone compatibili, in modo che ogni uomo risulti sposato (e ovviamente che ogni donna sia sposata con al più un uomo). Questo è possibile se e solo se, preso un qualunque insieme di n uomini, le donne compatibili con almeno uno di essi sono almeno n.
Dimostrare...
Siano dati un insieme di uomini e un insieme di donne. Alcune coppie (uomo, donna) sono "compatibili", ovvero si piacciono reciprocamente e non disdegnerebbero sposarsi. Un uomo può essere compatibile con più donne o con nessuna donna, e viceversa. Vorremmo poter organizzare dei matrimoni tra persone compatibili, in modo che ogni uomo risulti sposato (e ovviamente che ogni donna sia sposata con al più un uomo). Questo è possibile se e solo se, preso un qualunque insieme di n uomini, le donne compatibili con almeno uno di essi sono almeno n.
Dimostrare...