Mühazirə 14. Qraflar və onlar haqqında ümumi məlumatlar Əsas anlayışlar

Tərif 6. Əgər qraf müstəvi üzərində elə realizə oluna bilərsə ki, onun tilləri ancaq təpələrdə kəsişsin, onda belə qrafa planar qraf deyilir.
Şəkil 5-də verilən qraflar planar olmayan qraflardır.
Tərif 7. və qraflarının təpələri və tilləri arasında
qarşılıqlı birqiymətli uyğunluq olarsa və həm də bu uyğunluq elə olarsa ki, uyğun tillər uyğun təpələri birləşdirir, onda və qraflarına izomorf qraflar deyilir.
Bu tərifə əsasən abstrakt qrafla onun həndəsi realizəsi izomorf qraflardır. Teorem 1-in hökmünə görə abstrakt qraf əvəzinə onun həndəsi realizəsinə (təsvirinə) baxmaq olar. Ona görə də qrafa həndəsi obyekt kimi baxmaq olar.
qrafının tillərinin hissələrə bölünməsi əməliyyatını daxil edək. Tutaq ki, - qrafının ixtiyari tilidir, isə -ə daxil olmayan obyektdir. qrafının tilinin hissələrə bölünməsi əməliyyatı qrafının qurulmasından ibarətdir, harada ki,
.
qrafı qrafının tillərinin sonlu sayda hissələrə bölünməsi əməliyyatı vasitəsilə alınırsa, onda qrafı qrafının hissələrə bölünməsi adlandırılır.
Tərif 8. və qraflarının əgər elə hissələrə bölünməsi
mövcuddursa ki, onlar izomorfdurlar, onda və qrafları homoemorf qraf adlanırlar.
Nümunə 4. Şəkil 6-da və 7-də və qrafları təsvir olunub. Bu qraflar izomorf deyildirlər, lakin homoemorfdurlar. Çünki hər iki qraf şəkil 8-də təsvir olunan qrafa kimi hissələrə bölünə bilərlər.

Şəkil 6. Şəkil 7. Şəkil 8.

Tərif 9. Əgər qrafının təpələri və tilləri qrafına məxsusdursa, yəni , onda qrafına qrafının alt qrafı deyilir.
Pontryaqin-Kuratovski teoremi aşağıdakı kimi şərh olunur:
Teorem 2 (müstəvi üzərində realizə olunma kriteriyası). qrafının müstəvi üzərində realizə oluna bilməsi üçün zəruri və kafi şərt onun istənilən alt qrafının şəkil 5-də təsvir olunan qrafların heç biri ilə homoemorf olmamasıdır.