Ö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ә
terminlərində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 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ı?
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.