00i9az titul(1-7)

 
 
5 
91 
 
•  V  fəsil  •  
İnformasiya texnologiyaları 
•
  
Q
RAFLARLA BAĞLI MƏSƏLƏLƏR
 
 
 
 
 
Bir çox praktik məsələlərdə (məsələn, iki məntəqə arasında ən qısa yolun tapıl-
masında)  yalnız  təpələr  arasında  əlaqələr  deyil,  bu  əlaqələrə  uyğun  ədədlər  (əm-
sallar) önəmli olur. Məsələn, bu ədədlər şəhərlər arasındakı məsafə, yaxud yolpulu 
ola bilər. Qraflar nəzəriyyəsində hər bir tilə uyğun ədədə (əmsala) onun çəkisi, belə 
qrafa isə çəkili qraf deyilir.  
 
 
 
Həlli.
 
Uyğun məntəqələrin və onlar arasındakı yolların sxemini belə bir çəkili qraf 
şəklində göstərmək olar. Göründüyü kimi, burada 6 mümkün dövrə var: ABCDA, 
АСВDА, АВDСА, АСDВА, АDВСА, АDСВА. Onların uzunluqları uyğun olaraq 
belədir: 25, 16, 21, 21, 16, 25.  
Beləliklə, ən qısa marşrutlar АСВDА və АDВСА olacaq. 
 
Çəkili qraflarda qonşuluq matrisinin əvəzinə çəki matrisindən istifadə olunur. 
Çəki matrisinin xanalarında tillərin çəkisi göstərilir və əgər 
iki  təpə  arasında  til  yoxdursa,  uyğun  xana  boş  saxlanılır. 
Şəkildə yolların uzunluğu qeyd olunmuş sxem, ona uyğun 
qraf və çəki matrisi göstərilib.  
20 
 İstiqaməti olan tilə nə deyilir? 
 Hər bir tilinin istiqaməti olan qraf necə adlanır? 
 
 
Verilmiş A, B, C və D məntəqələrinin hər birindən qalan məntəqələrə yollar var və 
onların  uzunluqları  məlumdur:  AB=7,  AC=5,  AD=4,  BC=6,  BD=1,  CD=8.  Bu 
məntəqələrin birindən başlayıb onların hər birində yalnız bir dəfə olmaqla başlanğıc 
məntəqəyə qayıtmaq lazımdır. Hansı marşrut üzrə hərəkət edilməlidir ki, keçilən yol 
ən qısa olsun? 
 
 
Məsələ
 
A
B
C 
D 
7
6 
8 
4
1
5
• 
Çəkili qraf 
• 
Çəki matrisi 
S ö z l ü k  

---

 
 
92 
 
 
 
 
 
 
 
 
 
 
Bəs çəki matrisinin köməyi ilə nə müəyyən etmək olar? Birincisi, verilmiş iki 
təpə arasında tilin olub-olmadığını və əgər varsa, onun uzunluğunun (çəkisinin) nə 
olmasını.  Bunun  üçün,  sadəcə,  uyğun xanaya  baxmaq  lazımdır. Məsələn,  B  və  C 
təpələri arasında til var və  onun çəkisi 5-ə  bərabərdir. İkincisi,  tillərin  çəkilərinin 
təpələr  arasındakı  məsafələri  göstərdiyini  fərz  etsək,  verilmiş  təpələrdən  keçən  
yolun uzunluğunu müəyyən etmək olar. Məsələn, ABCD yolunun uzunluğu AB, BC 
və  CD  tillərinin  uzunluqları  cəminə  bərabər  olacaq:  12  +  6  +  4  =  22.  Nəhayət, 
verilmiş çəki matrisinin köməyi ilə qrafın özünü çəkmək olar.  
 
 
 
Həlli.
 
Neptun  planetindəki  şəhərləri  qrafın  təpələri,  onlar  arasındakı  yolları  isə 
tillər  şəklində  göstərsək,  adi  qraf  alarıq.  Məsələdə  qrafdakı  tillərin  sayını  tapmaq 
tələb olunur. Bu qrafa uyğun qonşuluq matrisi təxminən aşağıdakı kimi olacaq:
 
0 1 1 0 1 0 
1 0 1 1 1 0 
1 1 0 0 0 0 
0 1 0 0 0 1 
1 1 0 0 0 1 
0 0 0 1 1 0 
Burada i-ci sətir ilə j-ci sütunun kəsişməsində 1 olması uyğun şəhərlər arasında 
yolun olmasını bildirir. Belə bir yol varsa, j-ci sətir ilə i-ci sütunun kəsişməsində də 
Qoşabulaq
Laçın 
Günəşli 
Çinarlı 
12 
5
6 
4
2 
8
A
B
D
 
C
 
12
8
5
4
 
2
 
6
Süd  yolu  qalaktikasının  Neptun  planetində  6  şəhər  var  və  onlar  1-dən  başlayaraq 
ardıcıl nömrələnib. Şəhərlərin bəziləri yollarla birləşdirilib. Qalaktikanın imperatoru 
Maksimus bu planetdəki yolları siyahıya almağa qərar verir, ancaq riyaziyyatdan zəif 
olduğundan yolların sayını hesablamaqda  sizdən kömək istəyir. 
 
 
Məsələ
 
A 
B 
C 
D 
A 
 12 8   
B 
12 
 5 6 
C 
8 5 2 4 
D 
 6 4  

---

 
 
5 
93 
 
•  V  fəsil  •  
İnformasiya texnologiyaları 
•
1 olacaq. Başqa sözlə, i nömrəli şəhərdən j nömrəli şəhərə yol varsa, j nömrəli şəhər-
dən də i nömrəli şəhərə yol var. Deməli, qoyulan məsələni həll etmək üçün qonşuluq 
matrisindəki  1-lərin  sayını  hesablayıb  nəticəni  2-yə  bölmək  lazımdır.  Beləliklə, 
yuxarıdakı qonşuluq matrisinə görə, Neptun planetində cəmi 8 yol var. 
Bu məsələnin Python dilində həll proqramını belə yazmaq olar: 
 
i = 1 
w 
= 
0 
    
# w - yolların sayı 
 
while
 i <= 6: 
    s = 
input
()  
 
# Matrisin bir sətri  
     # 
daxil 
edilir
 
    w = w + s.count(
'1'
)  
# Həmin sətirdəki 1-lərin  
 
 
 
 
 
# sayı hesablanıb ümumi  
     # 
yolların sayına əlavə olunur 
 
    i = i + 1 
 
w = w // 2 
print
(w) 
 
 
 
 
 
Süd yolu qalaktikasının Neptun planetində N şəhər var və onların bəziləri yollarla 
birləşdirilib.  Qalaktikanın  imperatoru  Maksimus  bu  planetdəki  yolları  siyahıya 
almağa qərar verir, ancaq riyaziyyatdan zəif olduğundan yolların sayını hesablamaqda  
sizdən kömək istəyir. (Mənbə: informatika.edu.az) 
 
Araşdıraq- 
          öyrənək  
Şahmat turniri dairəvi sistem üzrə keçirilir, 
yəni  iki  oyunçu  öz  aralarında  yalnız  bir 
dəfə  görüşürlər.  Turnirdə  yeddi  məktəbli 
iştirak edir. Məlumdur ki, Arif altı, Bəkir 
beş, Ceyhun və Dadaş hərəyə üç, Elxan və  
Əli  hərəyə  iki,  İlkin  isə  bir  oyun  keçirib. 
Ceyhun kimlərlə oynayıb? 
 
Həlli. Oyunçuların görüşlərini əks etdirən 
qraf quraq və onu G ilə işarə edək. Bu qra-
fın təpələrini 1-dən 7-dək ədədlərlə işarə-
ləyək və uyğunluğu belə müəyyənləşdirək: 
1 – Arif, 2 – Bəkir, 3 – Ceyhun,  
4 – Dadaş, 5 – Elxan, 6 – Əli, 7 – İlkin.  
 
 
Məsələ
 

---