İnformasiya texnologiyaları |  | 5

Öz aralarında ixtiyari qaydada birləşmiş müəyyən sayda obyektdən ibarət olan struktura qraf deyilir.Proqramlaşdırmada bəzən “qraf” termininin əvəzinə

“şəbəkə” terminindən istifadə olunur. Qrafı təşkil edən obyektlər təpələr, onları birləşdirən xətlər isə tillər adlanır. Qrafın hər hansı iki təpəsi tillə birləşdirilməyə də bilər. Çox zaman qrafın təpələri ardıcıl nömrələnir, yaxud hərflərlə işarələnir. |

Qraflar nəzəriyyəsinin yaranmasına səbəb görkəmli riyaziyyatçı Leonard Eylerin (1707-1783) 1736-cı ildə Köniqsberq (indiki Kalininqrad) şəhərində olarkən həll etdiyi bir əyləncəli məsələ olub.

Şəhərdən keçən çay onu dörd hissəyə bölürdü və bu hissələr yeddi körpü vasitəsilə birləşirdi. Şəhərin sadələşdirilmiş planında körpülər rəqəmlərlə, şəhərin hissələri isə hərflərlə işarə olunub. Həmin dövrdə məşhur olan məsələ isə belə idi: hər körpüdə yalnız bir dəfə olmaqla bütün körpülərdən necə keçmək olar? Eyler bu məsələni həll etməyin mümkün olmadığını müəyyənləşdirdi. O, şəhərin hissələrini uyğun olaraq A, B, C və D nöqtələri ilə, körpüləri isə bu nöqtələri birləşdirən xətlər vasitəsilə göstərdi. Beləliklə, qoyulmuş məsələ belə bir məsələyə ekvivalent olur: qələmi kağızdan ayırmadan və hər xətdən yalnız bir dəfə keçməklə bu fiquru çəkmək olarmı? |

Qrafların təqdim edilməsi. Adətən, qraflar iki üsulla təqdim edilir: qonşuluq siyahısı və qonşuluq matrisi. Qonşuluq siyahısında hər bir təpə üçün ona bitişik təpələr sadalanır. Bu formada təkrarçılıq olur: məsələn, əgər A və B təpələri bitişikdirsə, onda A-nın qonşuluq siyahısında B, B-nin siyahısında isə A olur.
İkinci təqdimolunma formasında - qonşuluq matrisində n təpədən ibarət qraf n sətirdən və n sütundan ibarət cədvəl (n x n ölçülü matris) şəklində göstərilir. Əgər hər hansı x təpəsi ilə y təpəsi arasında til varsa, onda ax,y elementi 1-ə, əks halda isə 0-a bərabər olur. Məsələn, yuxarıdakı qrafın qonşuluq siyahısı və qonşuluq matrisi belə olacaq:

Təpə | Qonşuluq siyahısı
0 | 1, 2, 4
1 | 0, 2, 3, 4
2 | 0, 1
3 | 1
4 | 0, 1
5 |
| 0 | 1 | 2 | 3 | 4 | 5
0 | 0 | 1 | 1 | 0 | 1 | 0
1 | 1 | 0 | 1 | 1 | 1 | 0
2 | 1 | 1 | 0 | 0 | 0 | 0
3 | 0 | 1 | 0 | 0 | 0 | 0
4 | 1 | 1 | 0 | 0 | 0 | 0
5 | 0 | 0 | 0 | 0 | 0 | 0