Bröllopssatsen

Bröllopssatsen (även pojke- flicksatsen , Halls sats ) är påståendet att i en tvådelad graf för ett naturligt tal är alla hörn i en av delarna, där inte överstiger antalet hörn av delen, kopplas åtminstone till olika hörn av den andra delen, då och endast när grafen paras ihop med den första andelen. $k$ $k$ $k$ $k$

Bevisad 1935 av Philip Hall . [ett]

Om bevis

Ett bevis följer omedelbart från den ungerska algoritmen för att hitta den maximala matchningen i en graf.

Dessutom är satsen en konsekvens av Ford-Fulkersons sats om skärande transportnätverk .

För fallet med reguljära gradgrafer kan satsen lätt härledas från förekomsten av en Euler-cykel i varje sammankopplad komponent i grafen; på denna idé kan man konstruera ett bevis för alla vanliga grafer. [2] $2^{n}$

Variationer och generaliseringar

Det följer omedelbart av bröllopsteoremet att varje vanlig tvådelad graf av grad medger en perfekt matchning . $r\geqslant 1$

Teoremet generaliserar till tvådelade grafer med ett oändligt antal hörn, förutsatt att alla hörn har en ändlig grad.

Ett exempel på en oändlig tvådelad graf för vilken satsen inte stämmer är ett rakt cylindriskt glas, som är konstruerat enligt följande: den första delen av uppsättningen av hörn är punkterna för den övre omkretsen av glaset och mitten av den nedre bas; den andra delen är punkterna på omkretsen av den nedre basen; kanterna på grafen är alla radierna för den nedre basen och de vertikala segmenten av sidoytan.

Tutts matchningssats är en generalisering av vigselsatsen till fallet med godtyckliga ändliga, men inte nödvändigtvis tvådelade, grafer.

Koenigs teorem är ett nära uttalande som handlar om att hitta den största matchningen och den minsta vertextäckningen i finita grafer.

Anteckningar

↑ Hall, Philip (1935), Om representanter för undergrupper , J. London Math. soc. V. 10 (1): 26–30 , DOI 10.1112/jlms/s1-10.37.26
↑ G. Kalai. De sjutton kamelerna gårtan, och Noga Alons kamelbevis och algoritmer . - 2017. Arkiverad den 28 augusti 2020.

Länkar

N. Kostyukova, Kurs "Graphs and their applications", Föreläsning 15: Matchning och bröllop : "Hall's wedding theorem" // Intuit.ru , 07/25/2006
A. Yu. Evnin. Around the Hall theorem // Matematisk utbildning . - 2005. - T. 3 (34) . - S. 2-23 . (ryska)