Теорема о свадьбах

Теорема о свадьбах

Теорема о свадьбах (также теорема о мальчиках и девочках, теорема Холла) — утверждение о том, что в двудольном графе для любого натурального любые вершин одной из долей, где не превышает числа вершин доли, связаны по крайней мере с различными вершинами другой доли тогда и только тогда, когда граф разбивается на пары по первой доле.

Доказана в 1935 году Филиппом Холлом.[1]

О доказательствах

  • Одно из доказательств следует немедленно из венгерского алгоритма для поиска максимального паросочетания в графе.
  • Для случая регулярных графов степени теорема легко выводится из существования эйлерова цикла в каждой связной компоненте графа; на этой идее можно построить доказательство для всех регулярных графов.[2]

Вариации и обобщения

  • Из теоремы о свадьбах немедленно следует, что любой регулярный двудольный граф степени допускает совершенное паросочетание.
  • Теорема обобщается на двудольные графы с бесконечным множеством вершин, при условии, что все вершины имеют конечную степень.
Пример бесконечного двудольного графа в котором не выполняется теорема о свадьбах
  • Пример бесконечного двудольного графа, для которого теорема не верна — прямой цилиндрический стакан, который строится следующим образом: первая доля множества вершин — точки верхней окружности стакана и центр нижнего основания; вторая доля — точки окружности нижнего основания; рёбра графа — все радиусы нижнего основания и вертикальные отрезки боковой поверхности.

Примечания

  1. ↑ Hall, Philip (1935), "On Representatives of Subsets", J. London Math. Soc., 10 (1): 26–30, doi:10.1112/jlms/s1-10.37.26
  2. ↑ G. Kalai. The seventeen camels riddle, and Noga Alon’s camel proof and algorithms (англ.). — 2017. Архивировано 28 августа 2020 года.

Ссылки

Read other articles:

Cumberland Line

Rail service in Sydney, New South Wales, Australia Cumberland LineAn M set at Warwick Farm stationOverviewOwnerTransport Asset Holding EntityLocaleSydney, New South WalesTerminiRichmondLeppingtonStations30ServiceTypeCommuter railOperator(s)Sydney TrainsDepot(s)MortdaleRolling stockM, A setsHistoryOpened1996; 28 years ago (1996)TechnicalTrack gauge1,435 mm (4 ft 8+1⁄2 in) standard gauge Sydney Trains services Metro North West North Shore & Wester...

 

Battle of Bunker Hill

Battle of the American Revolutionary War For a list of numerous places and things that are named after this battle, see Bunker Hill. Battle of Bunker HillPart of the American Revolutionary WarDeath of General Warren at the Battle of Bunker Hillby John TrumbullDateJune 17, 1775LocationCharlestown, Massachusetts42°22′34.9″N 71°3′38.8″W / 42.376361°N 71.060778°W / 42.376361; -71.060778Result See AftermathTerritorialchanges The British capture Charlestown Penin...

 

Koreasat 7

South Korean satellite Koreasat 7ArianespaceMission typeCommunications SatelliteOperatorKT SatCOSPAR ID2017-023A SATCAT no.42691 Spacecraft propertiesBusSpacebus-4000B2[1]ManufacturerThales Alenia Space Start of missionLaunch date00:00, April 5, 2017 (UTC) (2017-04-05T00:00Z) UTCRocketArianespace Orbital parametersReference systemGeocentricRegimeGeosynchronousLongitude116° E TranspondersBandKu, KaCoverage areaKorea, Philippines, Indonesia, India  ...

Matías Suárez

Argentine footballer Matías Suárez Suárez playing for Anderlecht in 2016Personal informationFull name Matías Ezequiel SuárezDate of birth (1988-05-09) 9 May 1988 (age 35)[1]Place of birth La Falda, Córdoba, ArgentinaHeight 1.76 m (5 ft 9 in)[2]Position(s) ForwardTeam informationCurrent team BelgranoSenior career*Years Team Apps (Gls)2005–2008 Belgrano 55 (13)2008–2016 Anderlecht 173 (50)2016–2019 Belgrano 57 (10)2019–2024 River Plate 79 (33)20...

 

Carlo Lodovici

Carlo Lodovici nel film Le scarpe al sole (1935) Carlo Lodovici (Pistoia, 1912 – Parma, 1982) è stato un regista, sceneggiatore e attore italiano. Fratello dell'attrice Laura Nucci. Indice 1 Filmografia 1.1 Regista 1.1.1 Televisione 1.1.2 Serie TV 1.2 Regista e sceneggiatore 1.2.1 Cinema 1.2.2 Televisione 1.3 Sceneggiatore 1.3.1 Cinema 1.4 Attore 1.4.1 Cinema 2 Note 3 Altri progetti 4 Collegamenti esterni Filmografia Regista Televisione Il ventaglio, co-regia di Franco Enriquez (1954) La f...

 

Association pour un conservatoire de l'informatique et de la télématique

Pour les articles homonymes, voir Aconit. ACONITRécolement dans les réserves.Informations généralesType Organisation à but non lucratifOuverture 24 Janvier 1985 (il y a 39 ans)Site web www.aconit.orgCollectionsCollections informatique, télématiqueLocalisationPays FranceDivision administrative Auvergne-Rhône-AlpesCommune GrenobleAdresse 12, rue Joseph-ReyCoordonnées 45° 11′ 09,96″ N, 5° 43′ 01,34″ ELocalisation sur la carte de GrenobleLocalisat...

Yana Bay

Yana BayЯнский залив (Russian)Yana BayMap showing the location of Yana BayLocationFar NorthCoordinates72°0′N 136°30′E / 72.000°N 136.500°E / 72.000; 136.500River sourcesYana, ChondonOcean/sea sourcesLaptev SeaBasin countriesRussia Islands at the eastern end of the Yana Bay. The Yana Bay (Russian: Янский залив; Yanskiy Zaliv) is a body of water in the Sakha Republic (Yakutia), Russian Federation. It is the most important gulf of t...

 

Cat's Cradle

1963 novel by Kurt Vonnegut This article is about the Kurt Vonnegut novel. For the string figure, see Cat's cradle. For other uses, see Cat's cradle (disambiguation). Cat's Cradle First edition hardback coverAuthorKurt VonnegutOriginal titleCat's CradleCountryUnited StatesLanguageEnglishGenreSatire, science fictionPublisherHolt, Rinehart and WinstonPublication date1963Media typePrint (hardcover and paperback)Pages304ISBN0-385-33348-XOCLC40067116Preceded byMother Night Foll...

 

Bernardino Cirillo

Bernardino Cirillo Bernardino Cirillo (L'Aquila, 20 maggio 1500 – Roma, 19 giugno 1575) è stato uno scrittore, storico e religioso italiano. Indice 1 Biografia 2 Opere 3 Note 4 Bibliografia 5 Voci correlate 6 Collegamenti esterni Biografia Nacque all'Aquila nel 1500 da Pietro Sarti de' Cirilli e Gemma Bucci,[1] di estrazione popolare, primogenito di sette figli.[2] Alla morte prematura del padre poté proseguire gli studi grazie all'aiuto economico di un mecenate locale ma,...

African wild ass

Species of wild ass African wild ass Somali wild ass subspecies (Equus africanus somaliensis) Conservation status Critically Endangered  (IUCN 3.1)[1] CITES Appendix I (CITES)[1][note 1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Mammalia Order: Perissodactyla Family: Equidae Genus: Equus Subgenus: Asinus Species: E. africanus Binomial name Equus africanus(von Heuglin & Fitzinger, 1866)[2] Subspecies...

 

Anna Gunn

American actress (born 1968) Anna GunnGunn in 2018Born (1968-08-11) August 11, 1968 (age 55)Cleveland, Ohio, U.S.Alma materNorthwestern UniversityOccupationActressYears active1992–presentHeight5 ft 10 in (1.77 m)Spouse Alastair Duncan ​ ​(m. 1990; div. 2009)​Children2 Anna Gunn (born August 11, 1968)[1] is an American actress. She played Skyler White on the AMC drama series Breaking Bad (2008–2013), for ...

 

2020年夏季奥林匹克运动会科索沃代表团

2020年夏季奥林匹克运动会科索沃代表團科索沃国旗IOC編碼KOSNOC科索沃奧林匹克委員會網站www.noc-kosovo.org（英文）（阿爾巴尼亞文）（塞爾維亞文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員11參賽項目6个大项旗手开幕式：阿基爾·賈科瓦（英语：Akil Gjakova）和瑪琳達·開爾門蒂（柔道）[1]闭幕式�...

Jack Concannon

Jack Concannon Nazionalità  Stati Uniti Altezza 191 cm Peso 93 kg Football americano Ruolo Quarterback CarrieraGiovanili  Boston College EaglesSquadre di club 1964-1966 Philadelphia Eagles1967-1971 Chicago Bears1972-1973 Dallas Cowboys1974 Green Bay Packers1975 Detroit Lions Statistiche aggiornate al 21 novembre 2013 Modifica dati su Wikidata · Manuale Jack Concannon, vero nome John Joseph Concannon Jr. (Boston, 25 febbraio 1943 – Waltham, 28 n...

 

خاليدو كوليبالي

خاليدو كوليبالي (بالفرنسية: Kalidou Koulibaly)‏    معلومات شخصية الميلاد 20 يونيو 1991 (33 سنة)[1]  سينت ديه دي فوج  الطول 188 سنتيمتر[2]  مركز اللعب قلب الدفاع  الجنسية السنغال فرنسا  المسيرة الاحترافية  سنواتفريقمبارياتأهداف2009–2011 متز 31 (2)2010–2012 متز 41 (1)2012–2...

 

Fanno Creek

River in Oregon, United States Fanno CreekFanno Creek in Greenway Park, BeavertonFanno Creek watershedLocation of the mouth of Fanno Creek in OregonEtymologyAugustus Fanno, early settlerLocationCountryUnited StatesStateOregonCountyMultnomah and WashingtonPhysical characteristicsSourceTualatin Mountains (West Hills) • locationPortland, Multnomah County, Oregon • coordinates45°28′44″N 122°42′00″W / 45.47889°N 122.70000°W /...

Email

Mail sent using electronic means For the former company, see Email Limited. Reply all redirects here. For the podcast, see Reply All (podcast). This screenshot shows the Inbox page of an email client; users can see new emails and take actions, such as reading, deleting, saving, or responding to these messages. When a robot on Wikipedia makes changes to image files, the uploader receives an email about the changes made. Electronic mail (email or e-mail) is a method of transmitting and receivin...

 

Emma Gatewood

Emma Rowena Nenek GatewoodLahir(1887-10-25)25 Oktober 1887Mercerville, Guyan Township, Gallia County, Ohio, Amerika SerikatMeninggal4 Juni 1973(1973-06-04) (umur 85)Gallipolis, Ohio, Amerika SerikatMakamOhio Valley Memory GardensTahun aktif1955 hingga 1973 (mendaki gunung)Dikenal atasMendaki Appalachian Trail dan tempat lainnyaSuami/istriPerry Clayton Gatewood [menikah 5 Mei 1907, bercerai Sept. 1940]Catatan Gallipolis Daily Tribune, June 4, 1973 Emma Rowena Gatewood, dikenal juga ...

 

.50 BMG

Rifle cartridge designed by John Moses Browning .50 BMGFrom left: .50 BMG, .300 Win Mag, .308 Winchester, 7.62×39mm, 5.56×45mm NATO, .22 Long RifleTypeAnti-materiel rifle, heavy machine gunPlace of originUnited StatesService historyIn service1921–presentUsed byNATO and many other countries[vague]WarsWorld War IIKorean WarVietnam WarCambodian Civil WarFalklands WarPersian Gulf WarThe TroublesGlobal War on TerrorismIraq WarWar in AfghanistanMexican drug warSyrian Civil War...

Coroneo

This article needs to be updated. Please help update this article to reflect recent events or newly available information. (September 2021)City & Municipality in Guanajuato, MexicoCoroneoCity & MunicipalityBridge overlooking a portion of the cityLocation of Coroneo in GuanajuatoCoordinates: 20°08′N 100°20′W / 20.133°N 100.333°W / 20.133; -100.333Country MexicoState GuanajuatoArea • Total122.90 km2 (47.45 sq mi)Popula...

 

Pantone

U.S. corporation This article is about the corporation and its color space. For other uses, see Pantone (disambiguation). Pantone LLCFounderLawrence HerbertHeadquartersCarlstadt, New JerseyParentX-RiteWebsitepantone.com Pantone LLC (stylized as PANTONE) is an American limited liability company headquartered in Carlstadt, New Jersey,[1] and best known for its Pantone Matching System (PMS), a proprietary color space used in a variety of industries, notably graphic design, fashion design...