Qraflar

1.1 Qrafın tərifi və onun komponentləri

Qraf — fərqli obyektləri və onların əlaqələrini modelləşdirib təqdim etmək üçün geniş istifadə olunan, çox sayda zirvə (və ya nod) və həmin zirvələri birləşdirən kənarlardan (və ya ox) ibarət məlumat strukturudur.

Qrafın əsas komponentləri:

Zirvələr:

• Qrafın obyektləri təmsil edən elementləri.
• V kimi göstərilir (zirvələrin çoxluğu).
• Məsələn, V = {A, B, C, D}.

Kənarlar:

• Zirvələr arasındakı əlaqələri və ya münasibətləri təmsil edən birləşmələr.
• E kimi göstərilir (kənarların çoxluğu).
• Məsələn, E = {(A, B), (B, C), (C, D), (A, D)}.

Qrafın əsas xüsusiyyətləri:

Zirvənin dərəcəsi:

• Həmin zirvəyə aid olan kənarların sayı.
• Orientasız qrafda zirvənin dərəcəsi – həmin zirvəni digər zirvələrlə birləşdirən kənarların sayıdır.
• Orientasiyalı qrafda isə daxil olan və çıxan dərəcələr fərqlənir.

Qrafda yol:

• Zirvələrin ardıcılını birləşdirən kənar ardıcıllığı.
• Məsələn, A-dan D-yə yol: A → B → C → D.

Qrafda dövr:

• Eyni zirvədə başlayıb bitən yol.
• Məsələn, dövr: A → B → C → A.

1.2 Qraf növləri

Qraflar çox müxtəlif ola bilər, amma onların içində maraqlı alt növləri qeyd etmək olar:

1. İstiqamətsiz qraf:

Bu qrafın qıraqları istiqamətə malik deyil, yəni iki zirvə arasında əlaqə hər iki tərəfə keçilə bilər.

Nümunə:

Sosial şəbəkələr, burada düyünlər insanları, qıraqlar isə onların dostluq əlaqələrini təmsil edir.

2. İstiqamətli qraf:

Qrafın qıraqları istiqamətə malikdir (adətən oxlarla göstərilir), yəni iki zirvə arasında əlaqə yalnız bir istiqamətdə keçilə bilər.

Nümunə:

Veb-səhifələrdə linklərdən ibarət qraf, burada düyünlər səhifələr, qıraqlar isə aralarındakı linklərdir.

3. Çəkili qraf:

Qıraqlar çəkiyə (rəqəmlər) malikdir, bu çəki məsafələri, xərcləri və ya digər ölçüləri təmsil edə bilər.

Nümunə:

Yolların qrafı, burada düyünlər şəhərlər, qıraqlar isə yollar və onların uzunluğu və ya keçid dəyəridir.

4. Qarışıq qraf:

Hem istiqamətli, həm də istiqamətsiz qıraqlara malik olan qrafdır.

Nümunə:

Nəqliyyat sistemləri, burada bəzi yollar ikitərəfli, bəziləri isə birtərəflidir.

5. Mütləq səth qrafı:

Belə bir qraf ki, onu müstəvinin üzərində çəkmək olar və qıraqları bir-birini kəsməz.

Nümunə:

Şəhərdəki yollar qrafı (tunellərsiz).

6. Birləşmiş qraf:

Elə bir qraf ki, hər hansı iki zirvənin arasında yol mövcuddur.

Nümunə:

Şəhərləri təmsil edən qraf, hər cüt şəhərin arasında yol mövcuddur.

7. Təkərsiz qraf:

Dövrləri olmayan qrafdır.

Nümunə:

Fayl sisteminin strukturunu təmsil edən ağac.

1.3 Qrafların tətbiq nümunələri

1. Sosial şəbəkələr:

• Node-lər insanları, rib-lər isə onların dostluq əlaqələrini təmsil edir.
• Əlaqələrin analizi, cəmiyyətlərin tapılması, istifadəçilərin təsir dərəcəsi və s. üçün istifadə olunur.

2. İnternet və routing:

• Node-lər router-ləri və ya kompüterləri, rib-lər isə onların arasındakı əlaqələri təmsil edir.
• Optimal data ötürmə yollarının tapılması üçün istifadə olunur.

3. Genomika:

• Node-lər genləri və ya proteinləri, rib-lər isə onların arasındakı qarşılıqlı əlaqələri təmsil edir.
• Genom məlumatlarının analizi, pattern-lərin tapılması və s. üçün istifadə olunur.

4. Logistika və nəqliyyat:

• Node-lər şəhərləri və ya nəqliyyat mərkəzlərini, rib-lər isə yolları və ya marşrutları təmsil edir.
• Daşınma marşrutlarının optimallaşdırılması, xərclərin minimuma endirilməsi və s. üçün istifadə olunur.

5. Kompüter şəbəkələri:

• Node-lər cihazları və ya serverləri, rib-lər isə onların arasındakı əlaqələri təmsil edir.
• Şəbəkələrin dizaynı və idarə olunması üçün istifadə olunur.

6. Data analizi və machine learning:

Qraflar məlumatların təsviri və analizi, klasterlərin tapılması, tövsiyə sistemlərinin yaradılması və s. üçün istifadə olunur.