Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

2.3. Alqoritmlərin qurulmasında şəbəkə, qraf və ağacların tətbiqinin xüsusiyyətləri

Şək. 2.11. Qraf


Düyünlərdən və bunları birləşdirən tillərdən ibarət həndəsi fiqura qraf deyilir [2,3,4]. Şəkil 2.11-də x_i ilə düyünlər, _i ilə tillər işarə olunub. Bu işarələrdən göründüyü kimi, tillərin işarələnməsi həm sərbəst surətdə, həm də hər bir tilə insident olan düyünlərin işarələrindən istifadə etməklə yerinə yetirilə bilər. Hər hansı tilin uclarında yerləşən düyünlər bir-birinə qonşu hesab olunur, məsələn, x₁ və x₂. Ümumi bir düyünə birləşən tillər də bir-birinə qonşu hesab olunur, məsələn,(x_1,х₃₎ və (x₃,x₄). Əgər hər hansı düyün hər hansı tilin bir ucuna aiddirsə, onda bu düyünlə bu til bir-birinə insident hesab olunur. Qraflar istiqamətlənmiş və ya istiqamətlənməmiş ola bilər. Birinci halda hər bir til ox ilə qeyd olunur.
Şəkil 2.11-də təsvir olunan qraf istiqamətlənməmiş qrafdır.

İstiqamətlənməmiş qrafda qəbul edilir, ammа istiqamətlənmiş qrafda belə deyil, yəni . Adətən qrafda qonşu düyünlər 1 tillə birləşmiş olur, ancaq bəzi hallarda iki və daha artıq tillərlə birləşə bilir. Belə qraflara multiqraf deyilir. Əgər qrafda hər hansı til müəyyən bir düyünün özünü özü ilə birləşdirirsə, belə tilə ilgək deyilir.

ilə x_i düyününə qonşu olan bütün düyünlər çoxluğunu işarə edək. Bu çoxluğun gücünə düyününün dərəcəsi deyilir və belə işarə olunur: .
Teorem: İxtiyari qrafda bütün düyünlərin dərəcələrinin cəmi bu qrafdakı tillərin sayından (N) iki dəfə çoxdur:



Şək.2.12. Qraf
Məsələn, yuxarıda təsvir olunan qrafda =12, tillərin sayı isə 6-ya bərabərdir.
Teorem: İxtiyari qrafda tək dərəcəli düyünlərin sayı cüt ədəddir.
Alt qraf anlayışı. Fərz edək, və rafları verilib, şərtləri ödənilir, bu halda deyirlər ki, qrafı qrafının alt qrafıdır. Bundan başqa əgər şərti də ödənərsə, onda deyirlər ki, qrafı qrafının məxsusi alt qrafıdır. Məsələn, şəkil 2.11-də təsvir olunan qrafın məxsusi alt qrafı aşağıdakı ola bilər, ancaq 2.14-da təsvir olunan məxsusi deyil.

Şək.2.13. Şəkil 2.11-də təsvir olunan qrafın məxsusi alt qrafı




Şək. 2.14. Şəkil 2.11-də təsvir olunan qrafın məxsusi olmayan alt qrafı
məxsusi alt qrafı

Yalnız bir başlanğıc düyünü və bir son düyünü olan asiklik istiqamətlənmiş qrafa şəbəkə deyilir. Qrafda qonşu düyünlərin ixtiyari ardıcıllığına marşrut deyilir. Əgər marşrutda hər bir düyün bir dəfədən artıq rast gəlmirsə, belə marşrut yol adlanır. Əgər hər-hansı yolun başlanğıc və sonu üst-üstə düşürsə, belə yola kontur deyilir.

Əgər qrafda elə iki düyün tapmaq olarsa ki, bunlar arasında yol mövcud deyil, belə qrafa rabitəsiz, əks halda rabitəli qraf deyilir.
Fərz edək, qrafı elə təşkil olunub ki, bunun hər biri rabitəli olan alt qrafları mövcuddur, lakin bunlar arasında rabitə mövcud deyil. Bu halda deyirlər ki, qrafları G qrafının komponentləridir. ilə G qrafından düyününü silməklə alınan qrafı işarə edək, bundan başqa G qrafından tilini silməklə alınan qrafı işarə edək. Əgər qrafının komponentləri qrafının komponentlərindən çox olarsa, onda düyününə ayıran deyilir. Əgər qrafının komponentləri qrafının komponentlərindən çox olarsa, onda tilinə körpü deyilir.
Qrafların yadda saxlanılması üsuları:
1) x_i düyünləri ilə a_j tilləri arasında insidentlik matrisi ilə,
2) düyünlərin qonşuluq matrisi əsasında,
3) tillərin qonşuluq matrisi əsasında, və s.
Ağac elə qrafa deyilir ki, onun yalnız bir düyünü sələfsiz düyündür, bu düyünə kök deyilir, qalan bütün düyünlərin hər birinin yalnız bir sələfi var. Bu qrafda düyünlərin birdən artıq varisi ola bilər. Ağacda həmişə heç bir varisi olmayan düyünlər mövcuddur, belə düyünlərə yarpaq deyilir.
İndi də qrafların qurulmasına aid bəzi məsələlərə baxaq.
1) Şəkil 2.15-də 2, 3, 4 ilə - adalar, 1ilə – dənizin sahili, böyük dairə ilə dəniz işarə olunub. i nömrəli quru sahəsini x_i ilə, bunlar arasında körpüləri qrafın tilləri ilə işarə etsək, şəkil şəkil 2.16-da təsvir olunan qraf alınar.




Şək.2.15. Dəniz, adalar və sahilin həndəsi quruluşu


x₄
x₃ x₁
x₂


Şək.2.16. Dəniz, adalar və sahilin qraf modeli

Misal 2. Вinomial əmsalların qrafla təsviri. Məlumdur ki, binomial əmsallar aşağıdakı düsturlar sistemi ilə qurulur:

Bu düsturlardan istifadə etməklə C(4,2) elementini aşağıdakı kimi qurmaq olar:
C(4,2)

C(3,2) C(3,1)

C (2,2) C(2,1) C(2,1) C(2,0)

……………………………………………………….

Şək. 2.17. C(4,2) binomial əmsalı hesablamaq üçün ağac
Misal 3. Determinantın hesablanmasına aid bir nümunə əsasında ağacın qurulmasına baxaq:


Göründüyü kimi, determinantını hesablamaq üçün iki alternativ qaydadan: və (birinci konyunktiv qrup),ya da və (ikinci konyunktiv qrup) determinantlarından istifadə etmək olar. Konyunktiv qruplar birlikdə ümumi dizyunktiv qrupu təşkil edir. Deməli, qurulan stoxastik ağacın hər bir düyünü bir neçə əlamətə malik ola bilər. Bu xüsusiyyət hesablamada problem yarada bilər. Bunu aradan götürmək üçün qurulan ağaca iki əlavə C₁, C₂ düyünlərini daxil edək , nəticədə aşağıdakı struktur alınar:

Şək.2.18. “və/və ya” tipli ağac

Bu struktura “və/və ya” ağacı deyilir. Bunun əvvəlki ağacdan üstünlüyü bundan ibarətdir ki, hər bir düyün yalnız bir əlamətlə səciyyələnir: ya dizyunktiv, ya da konyunktiv.