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.




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.
- 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]

Variationer och generaliseringar
- Det följer omedelbart av bröllopsteoremet att varje vanlig tvådelad graf av grad medger en perfekt matchning .

- 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.
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