Teorema dei matrimoni

Il teorema dei matrimoni è un risultato fondamentale della combinatoria. Tale teorema è stato dimostrato dal matematico inglese Philip Hall nel 1935 ed è noto anche come teorema dei rappresentanti distinti o come teorema di Hall.

Enunciato ed esempi

La seguente esemplificazione giustifica il nome del teorema.

Supponiamo di avere due insiemi uno ${\scriptstyle D}$ di donne e uno ${\scriptstyle U}$ di uomini e supponiamo non vi sia poligamia; supponiamo, inoltre, che ciascuna donna abbia una propria lista di uomini con i quali desidererebbe sposarsi. Detto ${\textstyle {\scriptstyle D'}}$ un qualsiasi sottoinsieme di ${\scriptstyle D}$ e detto ${\scriptstyle U'}$ il sottoinsieme di ${\scriptstyle U}$ formato dagli appartenenti alle liste delle donne di ${\scriptstyle D'}$ , la seguente condizione risulta necessaria affinché ciascuna donna possa sposarsi con un uomo dei suoi desideri:

$|D'|\leq |U'|$

Il teorema dei matrimoni afferma che tale condizione è anche sufficiente.

Per introdurre la formulazione insiemistica del teorema si deve definire cosa si intende per sistema di rappresentanti distinti.

Dati n insiemi finiti $S_{1},.......,S_{n}$ un sistema di rappresentanti distinti (SRD) per gli insiemi considerati è una sequenza di elementi distinti $s_{1},.....,s_{n}$ con $s_{i}\in S_{i}$ .

Il teorema assume allora la seguente forma: dati n insiemi $S_{1},.......,S_{n}$ è possibile determinare un sistema di rappresentanti distinti se e solo se è verificata la seguente condizione:

$|S_{i1}\cup .....\cup S_{ik}|\geq k$ qualunque sia $k\in \left\{1,...,n\right\}$ .

Un esempio è il seguente:

siano $S_{1}=\{a,b,c\}$ , $S_{2}=\{a,b\}$ , $S_{3}=\{a,c,d,e,f\}$ , $S_{4}=\{c,d,e\}$ , $S_{5}=\{c,d,e,f\}$ .

Allora $\{a,b,c,d,e\}$ è un SRD, ma non è l'unico, ad esempio lo è anche $\{c,b,d,e,f\}$ .

Enunciato nella Teoria dei Grafi

Il teorema è spesso formulato in termini di grafo bipartito, cioè un grafo non orientato tale che l'insieme dei suoi vertici si può partizionare in due sottoinsiemi tali che ogni vertice di una di queste due parti è collegato solo a vertici dell'altra.

Dato un grafo bipartito con sottoinsiemi $V_{1}$ e $V_{2}$ , si dice accoppiamento completo di $V_{1}$ in $V_{2}$ un insieme di archi senza estremi in comune, aventi la caratteristica di collegare ciascun elemento di $V_{1}$ con un elemento di $V_{2}$ .

Il teorema di Hall si può formulare così:

In un grafo bipartito $G=\left(V_{1}\cup V_{2};E\right)$ esiste un accoppiamento completo di $V_{1}$ in $V_{2}$ se e solo se $\forall A\subseteq V_{1}$ risulta

$|A|\leq |R(A)|$ dove $R(A)\subseteq V_{2}$ è costituito dai vertici adiacenti a elementi di $A$ .

Bibliografia

(EN) P. Hall (1935): “On Representatives of Subsets” J. London Math. Soc. vol. 10
(EN) J. H. Van Lint, R. M. Wilson (1992): “A Course in Combinatorics” Cambridge University Press

Collegamenti esterni

(EN) Hall’s theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
(EN) Eric W. Weisstein, Teorema dei matrimoni, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica

Read other articles:

Chapultepec

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

Lentvaris

Peta lokasi Lambang 54°39′0″N 25°4′0″E / 54.65000°N 25.06667°E / 54.65000; 25.06667 Istana Tyszkiewicz di Lentvaris Lentvaris (dengarkanⓘ, bahasa Polandia: Landwarów), adalah sebuah kota Lithuania timur, 9 km di timur Trakai, pusat transportasi penting, karena banyak jalan raya dan rel KA yang melintas di sini. Danau Lentvaris terletak dekat kota. Sejarah Pada abad ke-19 keluarga Tyszkiewicz memiliki sebuah istana bergaya Neo-Gothik yang dibangu...

Aspergillus versicolor

Aspergillus versicolor TaksonomiDivisiAscomycotaSubdivisiPezizomycotinaKelasEurotiomycetesSubkelasEurotiomycetidaeOrdoEurotialesFamiliTrichocomaceaeGenusAspergillusSpesiesAspergillus versicolor Tirab. Tata namaSinonim takson Sterigmatocystis versicolor Vuillemin (1903) lbs Aspergillus versicolor adalah jamur berfilamen yang sering ditemukan dalam ruangan yang lembap atau dalam produk makanan.[1][2] Jamur ini memiliki bau khas yang sering diasosiasikan dengan rumah yang berudar...

روح السياسة

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يونيو 2022) روح السياسة Psychologie Politique معلومات الكتاب المؤلف غوستاف لوبون اللغة الفرنسية عام 1910 العربية عام 1947 الناشر مؤسسة هنداوي 2012 تاريخ النشر 2012 الموضوع الروح السياسي�...

Nuova Guinea tedesca

Nuova Guinea tedesca (dettagli) (dettagli) Nuova Guinea tedesca - Localizzazione Dati amministrativiNome ufficialeDeutsch-Neuguinea Lingue ufficialitedesco Lingue parlateLingue austronesianeLingue papuasicheCreolo tedesco di Rabaul CapitaleSimpsonhafen dal 1910 al 1919 Altre capitali 1885–1891: Finschhafen 1891–1892: Stephansort 1892–1899: Friedrich-Wilhelms-Hafen 1899–1910: Herbertshöhe Dipendente da Germania PoliticaForma di governocolonia Nascita1884 con Gustav von Oertzen (C...

Pterygotus

PterygotusRentang fosil: Pertengahan Silur - akhir devon, 428–372.2 jtyl PreЄ Є O S D C P T J K Pg N Fosil Pterygotus anglicus Klasifikasi ilmiah Domain: Eukaryota Kerajaan: Animalia Filum: Arthropoda Subfilum: Chelicerata Kelas: Incertae sedis Ordo: Eurypterida (punah) Superfamili: Pterygotioidea (punah) Famili: Pterygotidae (punah) Genus: Pterygotus (punah)Agassiz, 1849 Spesies tipe Pterygotus anglicusAgassiz, 1849 Spesies 17 spesies valid P. anglicus Agassiz, 1849 P. arcuatus Sal...

Acrylonitrile

Acrylonitrile Identification Nom UICPA 2-propènenitrile Synonymes cyanure de vinyle, cyanure vinylique, nitrile acrylique, propène nitrile, vinyl cyanide, cyanoéthylène[1] No CAS 107-13-1 No ECHA 100.003.152 No CE 203-466-5 PubChem 7855 ChEBI 28217 SMILES C=CC#N PubChem, vue 3D InChI Std. InChI : vue 3D InChI=1S/C3H3N/c1-2-3-4/h2H,1H2 Std. InChIKey : NLHHRLWOUZZQLW-UHFFFAOYSA-N Apparence liquide incolore ou jaune pâle, d'odeur âcre[2] Propriétés chimiques Formule C3H3N&...

Iptables

iptables Informations Créateur Rusty Russell (en) Développé par Projet Netfilter Première version 1998 Dernière version 1.8.10 (10 octobre 2023)[1] Dépôt git.netfilter.org/iptables, git.netfilter.org/iptables et git://git.netfilter.org/iptables Écrit en C Système d'exploitation GNU/Linux Environnement Linux Type Filtrage de paquets Licence GNU GPL Site web www.netfilter.org modifier - modifier le code - voir Wikidata (aide) iptables est un logiciel libre de l'espace utilisateur Linu...

Edílson

Edílson Nazionalità Brasile Altezza 168 cm Peso 60 kg Calcio Ruolo Attaccante Termine carriera 2010 Carriera Squadre di club1 1990 Industrial-RJ0 (0)1991-1992 Tanabi0 (0)1992 Guarani33 (11)1993-1994 Palmeiras20 (8)1994-1995 Benfica17 (9)1995 Palmeiras21 (10)1996-1997 Kashiwa Reysol54 (44)1997-2000 Corinthians65 (21)2000-2001 Flamengo33 (5)2002 Cruzeiro20 (11)2002-2003 Kashiwa Reysol16 (7)2003-2004 Flamengo27 (13)2004 Vi...

Merzig

Merzig Balai kota di Merzig BenderaLambang kebesaranLetak Merzig di Merzig-Wadern Merzig Tampilkan peta JermanMerzig Tampilkan peta SaarlandKoordinat: 49°27′N 6°37′E / 49.450°N 6.617°E / 49.450; 6.617Koordinat: 49°27′N 6°37′E / 49.450°N 6.617°E / 49.450; 6.617NegaraJermanNegara bagianSaarlandKreisMerzig-Wadern Subdivisions17Pemerintahan • MayorMarcus Hoffeld[1] (CDU)Luas • Total108,79 km2 (4,2...

London Midland

This article is about the former train operating company. For the former railway company, see London, Midland and Scottish Railway. For the former British Railways region, see London Midland Region (British Railways). Former train operating company in the United Kingdom London MidlandClass 350 Desiro at Watford Junction in 2011OverviewFranchise(s)West Midlands11 November 2007 – 10 December 2017Main region(s)West Midlands, LondonOther region(s)North West, East MidlandsStations called at178St...

Interrupteur

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (mai 2014). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». En pratique : Quelles sources sont attendues ? Comme...

Guy Ryder

Guy RyderCBEGuy Ryder (2014). Direktur-Jenderal Organisasi Buruh Internasional ke-10PetahanaMulai menjabat 1 Oktober 2012PendahuluJuan SomavíaPenggantiPetahanaSekretaris Jenderal Konfederasi Serikat Perdagangan Internasional ke-1Masa jabatanNovember 2006 – Juni 2010Pendahuluorganisasi baruPenggantiSharan BurrowSekretaris Jenderal Konfederasi Serikat Perdagangan Bebas InternasionalMasa jabatanFebruari 2002 – Oktober 2006PendahuluLord JordanPenggantiorganisasi dibubar...

Caucasian race

Obsolete racial classification of humans This article is about the outdated race concept. For the peoples of the Caucasus Mountains, see Peoples of the Caucasus. For the US racial classification White or Caucasian, see White Americans. The Caucasian race (also Caucasoid,[a] Europid, or Europoid)[2] is an obsolete racial classification of humans based on a now-disproven theory of biological race.[3][4][5] The Caucasian race was historically regarded as a...

Singapore Civil Service

Permanent bureaucracy of the Singaporean state This article is part of a series onPolitics of Singapore Government Constitution of Singapore Law Human rights Legislature Parliament Speaker Seah Kian Peng (PAP) Leader of the House Indranee Rajah (PAP) Leader of the Opposition Pritam Singh (WP) 14th Parliament Constituencies Executive President of Singapore Tharman Shanmugaratnam (I) Prime Minister of Singapore Lee Hsien Loong (PAP) Cabinet Ministries The Reserves Judiciary Supreme Court of Sin...

Leica M2

Leica M2 Тип дальномерный фотоаппарат Производитель Leica Camera (Германия) Год выпуска 1957-1968 Объектив сменный Крепление объектива байонет Leica M Фотоматериал Плёнка типа 135 Размер кадра 24×36 мм. Фокусировка ручная, база дальномера 65 мм Экспозиция ручная Затвор Шторно-щелевой, механ...

Tinju pada Pekan Olahraga Nasional XIX – Kelas bulu putri

Tinju padaPekan Olahraga Nasional XIX Putra Putri 46 kg 48 kg 49 kg 51 kg 52 kg 54 kg 56 kg 57 kg 60 kg 60 kg 64 kg 64 kg 69 kg 75 kg 81 kg 91 kg Tinju kelas bulu putri pada Pekan Olahraga Nasional XIX akan dilaksanakan di GSG Tinju Pelabuhan Ratu, Kabupaten Sukabumi, Jawa Barat.[1] Jadwal Seluruh waktu menggunakan Waktu Indonesia Barat (UTC+07:00) Tanggal Babak 19 September 2016 Babak 16 besar 22 September 2016 Perempat final 25 September 2016 Semifinal 2...

Phoenix Suns 2020-2021

Voce principale: Phoenix Suns. Phoenix SunsStagione 2020-2021Sport pallacanestro Squadra Phoenix Suns Head CoachMonty Williams ProprietarioRobert Sarver General managerJames Jones NBA51–21 (70,8%)Division: 1ª (Pacific)Conference: 2ª (Western) PlayoffFinali NBA(perso vs Milwaukee 2–4) StadioPhoenix Suns Arena 2019-2020 2021-2022 Dati aggiornati al 21 luglio 2021 La stagione 2020-2021 dei Phoenix Suns è stata la 53ª stagione della franchigia nella NBA. Indice 1 Draft 2 Roster ...

بول بوير

بول بوير (بالإنجليزية: Paul D. Boyer)‏ معلومات شخصية اسم الولادة (بالإنجليزية: Paul Delos Boyer)‏ الميلاد 31 يوليو 1918 [1][2][3] بروفو[4][5] الوفاة 2 يونيو 2018 (99 سنة) [6][2][3] لوس أنجلوس سبب الوفاة فشل تنفسي مواطنة الولايات المتحدة عضو ...

Geoffrey W. Crawford

American judge (born 1954) Geoffrey W. CrawfordCrawford in 2014Chief Judge of the United States District Court for the District of VermontIn officeDecember 21, 2017 – July 20, 2024Preceded byChristina ReissSucceeded byChristina ReissJudge of the United States District Court for the District of VermontIncumbentAssumed office August 4, 2014Appointed byBarack ObamaPreceded byWilliam K. Sessions IIIAssociate Justice of the Vermont Supreme CourtIn officeOctober 2013 – Aug...

Kizuna AI

/profillengkap.com/index.php/article/French Forces of the Interior

/profillengkap.com/index.php/article/Chapultepec

/profillengkap.com/index.php/article/Exothermic reaction

/profillengkap.com/index.php/article/Lawnton, Queensland

/profillengkap.com/index.php/article/1999 NCAA Division I baseball tournament