ITT0030 Diskreetne matemaatika II - eksamikonspekt
d). Korrata protsessi seni, kuni on võimalik leida uusi M-laienevaid ahelaid.
Sellist algoritmi järgides saame lõpptulemuseks kooskõla, mis on igaljuhul maksimumkoos-
kõla (ning võib osutuda ka täielikuks kooskõlaks).
Hall'i teoreem(e. Halli abielu teoreem)- Halli teoreemi rakendatakse graafi teoorias selleks,
et selgitada välja, kas kahealuselises graafis G=(V1+V2, E) leidub täielik kooskõla (e. kõik
tipud on küllastunud) või mitte.
HALLI TEOREEM: Oletamegi, et meil on graaf G=(V1+V2, E), kus X on tipuhulga
V1 mistahes alamhulk. Tipuhulga X naabrus on hulk NG(X) (naabrusesse kuuluvad kõik
sellised graafi tipud, mis on tippude hulga X mistahes elemendist kaugusel 1).
Halli teoreem ütlebki, et täielik kooskõla leidub siis ja ainult siis , kui |X||NG(X)|,
ehk kui tippude hulga V1 mistahes alamhulk X omab iseenda võimsusest rohkem
naabertippe, leidub täielik kooskõla.
annaabi.ee 
