"naabertippe" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

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. Euleri valem: seos tasandilise graafi tippude, servade ja tahkude arvude vahel. Euleri valemi rakendusi. Tasandiline(planaarne) graaf- graaf on tasandiline e. planaarne, kui teda saab tasandile joonistada nii, et tema servad väljaspool tippe ei lõikuks. Graafi tahud- graafi joonis tükeldab alati tasandi