Hääteoreema

Häälause (myös poika-tyttö -lause , Hallin lause ) on väite, että minkä tahansa luonnollisen luvun kaksiosaisessa graafissa minkä tahansa osan pisteet, joissa ei ylitä osan kärkien lukumäärää, ovat kytkettynä ainakin toisen osan eri kärkipisteisiin, silloin ja vain silloin, kun graafi on paritettu ensimmäisellä osuudella. $k$ $k$ $k$ $k$

Todisti vuonna 1935 Philip Hall . [yksi]

Tietoja todisteista

Yksi todistus seuraa välittömästi unkarilaisesta algoritmista maksimivastaavuuden löytämiseksi graafista.

Lause on myös seuraus Ford-Fulkersonin lauseesta kuljetusverkkojen leikkaamisesta .

Säännöllisten astegraafien tapauksessa lause on helppo päätellä Eulerin syklin olemassaolosta graafin jokaisessa yhdistetyssä komponentissa; tällä idealla voidaan rakentaa todistus kaikille säännöllisille kaavioille. [2] $2^{n}$

Muunnelmia ja yleistyksiä

Häälauseesta seuraa välittömästi, että mikä tahansa säännöllinen kaksiosainen astekaavio sallii täydellisen vastaavuuden . $r\geqslant 1$

Lause yleistyy kaksiosaisiin graafisiin, joissa on ääretön määrä pisteitä, edellyttäen, että kaikilla pisteillä on äärellinen aste.

Esimerkki äärettömästä kaksiosaisesta graafista, jonka lause ei pidä paikkaansa, on suora sylinterimäinen lasi, joka on rakennettu seuraavasti: kärkijoukon ensimmäinen osa on lasin yläkehän pisteet ja alemman kehän keskipiste. pohja; toinen osuus on alemman pohjan kehän pisteet; kaavion reunat ovat kaikki alapohjan säteet ja sivupinnan pystysegmentit.

Tuttin sovituslause on yleistys häälauseesta mielivaltaisten äärellisten, mutta ei välttämättä kaksiosaisten graafien tapaukseen.

Koenigin lause on läheinen väite, joka liittyy suurimman yhteensopivuuden ja pienimmän kärjen peitteen löytämiseen äärellisistä graafista.

Muistiinpanot

↑ Hall, Philip (1935), On Representatives of Subsets , J. London Math. soc. V. 10 (1): 26–30 , DOI 10.1112/jlms/s1-10.37.26
↑ G. Kalai. Seitsemäntoista kamelin arvoitus ja Noga Alonin kamelin todisteet ja algoritmit . - 2017. Arkistoitu 28. elokuuta 2020.

Linkit

N. Kostyukova, Kurssi "Grafit ja niiden sovellukset", Luento 15: Sovitus ja häät : "Hallin häälause" // Intuit.ru , 25.07.2006
A. Yu. Evnin. Hallin ympäri -lause // Matemaattinen koulutus . - 2005. - T. 3 (34) . - S. 2-23 . (Venäjän kieli)