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

Tərif 2. Tutaq ki, və -in obyektləri arasında və həm də və yığımlarının obyektləri arasında elə qarşılıqlı birqiymətli uyğunluq yaratmaq olur ki, aşağıdakı şərtlər ödənir:
1) və -in uyğun yığımları uyğun obyektlərdən (onların daxil olma sayları da nəzərə alınmaqla) ibarətdir;
2) və -in yığımları bir-birinə uyğun gəlir.
Onda və şəbəkələrinə izomorf şəbəkələr deyilir.
Aydındır ki, abstrakt şəbəkə öz həndəsi realizəsilə izomorfdur. Şəbəkələr izomorf dəqiqliklə baxıldığından, abstrakt şəbəkə əvəzinə onların həndəsi realizasiyasına baxmaq olar. Bu mənada şəbəkələr həndəsi obyektlər kimi təsvir olunurlar.
3. Şəbəkələrin bəzi növləri. Aydındır ki, şəbəkədə olduqda və hər bir yığımı çoxluğunun iki obyektindən ibarət olduqda şəbəkə qrafa çevrilir.
Şəbəkələri başqa bir növü ağaclardır. Ağac dedikdə dövrə malik olmayan əlaqəli qraf başa düşülür. Ağacda bir təpə ayrılır və kök adlandırılır. Aydındır ki, ağac bir qütbdən ibarət olan şəbəkədir, yəni .
Ağacın başqa bir tərəfini verək. Bu tərif induktiv tərifdir və birinci tərifə ekvivalentdir. Tərifi həndəsi şəkildə verək.
İnduksiya bazisi. Şəkil 3-də verilən fiqur kökünə malik ağac adlanır.
İnduksiya keçidi. Tutaq ki, (şəkil 4, a) kökünə malik ağac və (şəkil 4,b) kökünə malik ağacdır. Onda fiquru (şəkil 5, a) kökünə malik ağac olar, harada ki, bu fiqur -dan kökünə təzə til «qoşmaqla» alınır. Sonra, fiquru, harada ki, və -dən köklərin birləşdirilməsi vasitəsi ilə alınır, köklü ağac olar.

a) b) a) b)

Şəkil 3. Şəkil 4. Şəkil 5.

Asanlıqla görmək olar ki, ağacların induktiv təyinini abstrakt şəbəkələr terminində də vermək olar:
İnduksiya bazisi. kökünə malik ağacdır, harada ki, , .
İnduksiya keçidi. Tutaq ki, və uyğun olaraq və köklərinə malik ağaclardır, harada ki, və . Əgər , olarsa, onda
ağacı kökünə malik ağacdır, harada ki, - təzə obyektdir. Sonra, əgər isə və (uyğun olaraq ) yığımı yığımından simvolunun hər daxil olmalarını ilə əvəzləməklə alınırsa, onda ağacı təpəsində kökə malik ağac olur, harada ki, -yeni obyektdir.
A ğacın həndəsi təyini onun müstəvi üzərində həndəsi realizəsini həyata keçirməyə imkan verir. Ağacın tillərinin düz xətt parçaları, kökünün ox əlavə olunmuş təpə kimi (şəkil 6) təsvir olunduğu müstəvi üzərində həndəsi realizəsinə ağacın düzümü, yaxud döşənməsi deyilir.
Nümunə 3. Tutaq ki, Şəkil 6.
.
Burada ,
.
Aydındır ki, ağacdır. Şəkil 7-də bu ağacın bir düzümü verilmişdir. Bu ağacın başqa düzümləri də mümkündür.

Şəkil 7.
şəbəkəsinə baxaq. yığımında obyektlərin sayını ilə işarə edək. Əgər olarsa, onda belə şəbəkə iki qütblü, iki obyektli şəbəkə adlanır. Tutaq ki, . Bu halda iki qütblü şəbəkəni ilə işarə edək. Aydındır ki, şəbəkəsi iki təpəsi ayrılmış (qütblər) sonlu qraflarla üst-üstə düşür.