Bryllupssætningen

Bryllupssætningen (også drenge-pige- sætningen , Halls sætning ) er påstanden om, at i en todelt graf for ethvert naturligt tal , er ethvert hjørne af en af delene, hvor det ikke overstiger antallet af hjørner af delen, forbundet i det mindste med forskellige hjørner af den anden del, da og kun når grafen er parret af den første andel. $k$ $k$ $k$ $k$

Bevist i 1935 af Philip Hall . [en]

Om beviser

Et bevis følger umiddelbart fra den ungarske algoritme til at finde den maksimale matchning i en graf.

Sætningen er også en konsekvens af Ford-Fulkerson-sætningen om at skære transportnetværk .

I tilfælde af regulære gradgrafer udledes sætningen let fra eksistensen af en Euler-cyklus i hver forbundne komponent af grafen; på denne idé kan man konstruere et bevis for alle almindelige grafer. [2] $2^{n}$

Variationer og generaliseringer

Det følger umiddelbart af bryllupssætningen, at enhver regulær todelt graf af grad indrømmer en perfekt matchning . $r\geqslant 1$

Sætningen generaliserer til todelte grafer med et uendeligt antal toppunkter, forudsat at alle toppunkter har en endelig grad.

Et eksempel på en uendelig todelt graf, for hvilken sætningen ikke er sand, er et lige cylindrisk glas, som er opbygget som følger: den første del af sættet af toppunkter er punkterne for den øvre omkreds af glasset og midten af den nederste grundlag; den anden del er punkterne på omkredsen af den nedre base; kanterne af grafen er alle radierne af den nederste base og de lodrette segmenter af sidefladen.

Tutts matchende teorem er en generalisering af bryllupssætningen til tilfældet med vilkårlige endelige, men ikke nødvendigvis todelte grafer.

Koenigs sætning er et tæt udsagn om at finde det største matchende og det mindste toppunktsdæksel i endelige grafer.

Noter

↑ 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. De sytten kameler gårder, og Noga Alons kamelbevis og algoritmer . - 2017. Arkiveret den 28. august 2020.

Bryllupssætningen

Om beviser

Variationer og generaliseringer

Noter

Links