Qraf nəzəriyyəsi

Qraf nəzəriyyəsi — qrafların xüsusiyyətlərini öyrənən diskret riyaziyyatın bir qolu. Ümumi mənada bir qrafik kənarları ilə birləşdirilmiş zirvələr (düyünlər) toplusu kimi təmsil olunur. Qəti tərifdə qraf cüt cütüdür, burada istənilən sayılan çoxluğun alt dəstidir və  — altdır .

Altı zirvəli və yeddi kənarı olan qraf

Qraf nəzəriyyəsi, məsələn, coğrafi informasiya sistemlərində (CİS) istifadə olunur. Mövcud və ya yeni dizayn edilmiş evlər, tikililər, məhəllələr və s. zirvələr, onları birləşdirən yollar, mühəndis şəbəkələri, elektrik xətləri və s. Belə bir qrafik üzərində aparılmış müxtəlif hesablamaların istifadəsi, məsələn, ən qısa yol yolunu və ya ən yaxın ərzaq mağazasını tapmaq və optimal marşrutu planlaşdırma imkanı verir.

Qraf nəzəriyyəsi çox sayda həll olunmamış problemi və hələ təsdiqlənməmiş fərziyyələri ehtiva edir.

Qraf nəzəriyyəsinin tarixi

redaktə

Qraf nəzəriyyəsinin banisi Leonard Eyler. 1736-cı ildə məktublarından birində, daha sonra qraf nəzəriyyəsində klassik problemlərdən biri halına gələn yeddi Koenigsberg körpüsü problemini həll edir və həll təklif edir. "Sayı" ifadəsi ilk dəfə Silvester, Ceyms Yozef tərəfindən 1878-ci ildə Nature jurnalında yayımlanan məqaləsində gətirilmişdir[1].

Qraf nəzəriyyəsinin terminologiyası

redaktə

Qraf nəzəriyyəsinin terminologiyası hələ də ciddi şəkildə müəyyənləşdirilməyib. Xüsusən, Goodman, Hidetniemi, 1981-ci ildə çap edilən monoqrafiyasında deyilir: "Proqram dünyasında iki termindən hansının" qraf "və ya" şəbəkə "olduğuna dair dəqiq fikir birliyi yoxdur. Tətbiq sahələrində daha çox göründüyü üçün "şəbəkə" ifadəsini seçdik. " Vəziyyət "top / point" ifadələri ilə eynidir.

Qrafların növləri:

  • yönləndirilməmiş
  • yönləndirilmiş

İstinadlar

redaktə
  1. Sylvester, James Joseph. Chemistry and Algebra. 17 (Nature). 1878. 284.

Ədəbiyyat

redaktə

Xarici keçidlər

redaktə