"tipuhulga" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

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. Regulaarses (kõikide tippude aste on sama) kahealuselises graafis, mis pole nullgraaf, leidub täielik kooskõla. [40]. Tasandiline graaf