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

2. Qrafların həndəsi təsvirləri. Pontryaqin-Kuratovski teoremi. Qrafların yuxarıda verilən tərifi həddindən çox abstraktdır. Əyanilik üçün qrafın həndəsi interpretasiyasına baxıla bilər, yəni qraflar Evklid fəzasında müəyyən fiqurlar kimi təsvir oluna bilər. Belə fiqurları müxtəlif təpələrindən və hər biri müəyyən bir təpələp cütünü (trivial halda ola bilər) birləşdirən çevrə qövslərindən və ya düz xətt parçalarından ibarət olan xətlərdən (əyrilərdən) ibarət olur. Hesab olunur ki, fiqurunun heç bir daxili nöqtəsi başqa belə fiqurların təpə və ya daxili nöqtəsi ola bilməz. Qeyd edək ki, şəkil 1, şəkil 2 və şəkil 3-də təsvir olunan fiqurlar da uyğun qrafların həndəsi təsvirləridir.
Tərif 5. Əgər fiqurunun təpələri ilə qrafının təpələri və fiqurunun əyriləri və qrafının tilləri arasında elə qarşılıqlı birqiymətli uyğunluq mövcuddursa və əgər olduqda (uyğun əyrilər və tillər uyğun təpələri birləşdirir) olarsa, onda fiquruna qrafının həndəsi realizə edilməsi deyilir.
Nümunə 2. Nümunə 1-də verilən qrafının həndəsi realizəsi şəkil 4-də verilən fiqurudur.

Şəkil 4

Şəkil 4-dən göründüyü kimi qrafı multi qrafdır.
Nümunə 3. Şəkil 5-də iki qraf təsvir olunub. Bu qraflardan birincisi məşhur üç ev və üç quyu məsələsinin həlli ilə bağlı olan qrafdır. Qeyd edək ki, bu məsələ aşağıdakı kimidir: hər bir evdən hər quyuya elə yol çəkmək lazımdır ki, bu yollar bir-birini kəsməsin. İkinci qraf isə beş təpəyə malik tam qrafdır. Qeyd edək ki, tam qraf dedikdə bütün , , şəklində tillərə malik qraf nəzərdə tutulur. Şəkil 5-də verilən qraflar müstəvi üzərində realizə oluna bilmirlər.

Şəkil 5.

Qrafların müstəvi üzərində realizə olunması şərtini müəyyən etmək üçün L.S.Pontryaqin və Kuratovski maraqlı nəticə almışdırlar. O nəticəni şərh etməzdən əvvəl bəzi anlayışları verək.