00i9az titul(1-7)

 
 
88 
 
 
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 siya-
hı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×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 
a
x,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
 
 
Qrafları kompüterin yaddaşında saxlamaq üçün hər iki üsuldan, eləcə də başqa 
üsullardan  istifadə  olunur.  Məsələn,  verilmiş  qrafın  "qonşuluq  siyahısı"nı  Python 
dilində 
adjacency_list
,
 
onun təpələrinin sayını isə 
num_vertices
 kimi adlan-
dırsaq, onda:  
 
adjacency_list = [[1, 2, 4],   
                  [0, 2, 3, 4], 
                  [0, 1], 
                  [1], 
                  [0, 1], 
                  [], 
                 ] 
num_vertices = 
len
(adjacency_list) 
 
Bu  qraf  üçün  "qonşuluq  matrisi"ni 
adjacency_matrix 
kimi  adlandırsaq, 
onda:
 
 
adjacency_matrix = [[0, 1, 1, 0, 1, 0], 
                    [1, 0, 1, 1, 1, 0], 
                    [1, 1, 0, 0, 0, 0], 
                    [0, 1, 0, 0, 0, 0], 
                    [1, 1, 0, 0, 0, 0], 
                    [0, 0, 0, 0, 0, 0], 
                   ] 
num_vertices = 
len
(adjacency_matrix) 
 

---

 
 
5 
89 
 
•  V  fəsil  •  
İnformasiya texnologiyaları 
•
Göründüyü kimi, adi qrafın (yönəldilməmiş qrafın) qonşuluq matrisi həmişə baş 
diaqonala nəzərən simmetrikdir. Matrisin baş diaqonalı sol yuxarı küncdən sağ aşağı 
küncə gedir. 
Qrafı "tillər siyahısı" şəklində də saxlamaq olar. Bu halda hər bir til iki ədədlə – 
onun başlanğıc və son təpəsinin nömrəsi ilə göstərilir. Qrafın təpələrinin sayı ayrıca 
dəyişəndə  saxlanılır,  çünki  yalqız  (heç  bir  təpə  ilə  birləşməmiş)  təpələr  tillər 
siyahısına "düşmür". 
 
num_vertices = 6          
# Təpələrin sayı
 
edges_list = [[0, 1],     
# Tillərin siyahısı
 
              [0, 2], 
              [0, 4], 
              [1, 2], 
              [1, 3], 
              [1, 4], 
             ] 
 
Qraflarla bağlı daha bir neçə anlayışla tanış olaq. Sonuncudan başqa hər bir tilin 
son  təpəsi  o  biri  tilin  başlanğıc  təpəsi  olarsa,  belə  tillər  ardıcıllığına  yol  deyilir. 
Qapalı  yola  isə  dövrə  deyilir.  Məsələn,  yuxarıdakı  nümunədə  1,  2,  3  təpələrini 
birləşdirən tillər yol əmələ gətirir, 1, 2, 5 təpələri arasındakı yol isə dövrədir.  
Qeyd olunduğu kimi, qrafın bütün təpələrinin birləşməsi 
vacib  deyil,  ancaq  qrafın  istənilən  iki  təpəsi  arasında  yol 
varsa, onda belə qraf əlaqəli adlanır.
  
Bəzən hər hansı təpədən çıxan til həmin təpəyə qayıdır. 
Belə tilə ilgək deyilir.  
 
Əgər  tilin  müəyyən  istiqaməti  varsa  (məsələn,  til  B 
təpəsindən  A  təpəsinə  deyil,  A  təpəsindən  B  təpəsinə 
gedirsə), belə tilə qövs deyilir. Başqa sözlə, til, sadəcə, qrafın iki təpəsini birləşdirir, 
qövs  isə  bir  təpədən  başlayır,  o  biri  təpədə  bitir.  Bütün  tilləri  qövs  olan  qrafa 
yönəldilmiş qraf və ya diqraf deyilir. 
Yönəldilmiş  qrafları  yaddaşda  saxlamaq  üçün  müəyyən  dəyişikliklərlə  bu 
üsullardan istifadə etmək olar:  
  qonşuluq siyahılarında hər bir təpə üçün ondan çıxan tillərin getdiyi təpələr 
saxlanılır; 
  qonşuluq matrisində i-dən j-a til adjacency_matrix[i][j] == 1 
deməkdir və əgər qrafda geriyə til yoxdursa, 
adjacency_matrix[j][i] == 0 bərabərliyi doğru olacaq; 
  tillər siyahısında hər bir til [başlanğıc, son] şəklində saxlanılır. 
İlgək
 

---

 
 
90 
 
 
Ağac  (ağacşəkilli  struktur)  qrafın  bir  növüdür, 
yəni ağac heç bir dövrəsi olmayan əlaqəli qrafdır. 
Belə ki, ağacın istənilən iki təpəsi arasında yol var, 
ancaq ağacda heç bir qapalı yol yoxdur.  
 
Qraf  (şəbəkə)  informasiya  modelindən  həyatı-
mızın  müxtəlif  sahələrində  geniş  istifadə  olunur. 
Məsələn,  yeni  salınan,  yaxud  mövcud  yaşayış 
sahəsində  evləri  və  başqa  tikililəri  qrafın  təpələri, 
onlar arasındakı yolları, elektrik, su, rabitə və başqa 
xətləri  isə  qrafın  tilləri  kimi  göstərmək  olar.  Belə 
qraf üzərində optimal nəqliyyat marşrutlarını, obyektlər arasındakı ən qısa yolları 
planlaşdırmaq olar.   
 
 
 
 
 
 
  
1. 
Qraf nədir və hansı elementlərdən ibarətdir? 
2. Dövrəsi olmayan əlaqəli qraf necə adlanır? 
3. Bir təpədən çıxıb həmin təpəyə qayıdan tilə nə deyilir? 
4. Qraflar kompüterin yaddaşında hansı formada saxlanılır? 
5. Yaşadığınız bölgənin qrafını və uyğun qonşuluq matrisini qurun.  
 
 
Azərbaycanın  yuxarıda  göstərilmiş  şəhərləri  arasındakı  məsafələri  İnternetdən  (mə-
sələn, www.gomap.az saytından) öyrənin və onların əsasında qraf qurun. Həmin qraf 
üzərində Ağdaş və Şamaxı şəhərləri arasında ən qısa yolu göstərin. 
 
Araşdıraq- 
          öyrənək  
 
Öyrəndiklərinizi  
yoxlayın
 
Qövs
Yönəldilmiş qraf
 

---