ITT0030 Diskreetne matemaatika II - eksamikonspekt
Konstrueerime graafi G tarvis kooskõla M, lisades sellele servi, millel
puuduvad kahekaupa võetuna ühised otspunktid.
b). Järgmisena püüan graafis leida M-laienevat ahelat P.
c).Kui selline M-laienev ahel P ka leidub, koostada uus ning suurem kooskõla,
mis elimineeriks ahela P.
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
annaabi.ee 
