I9az titul+шмуц

 
 
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  gediş 
haqqı 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  
LAYİHƏ

---

 
 
92 
 
 
 
 
 
 
 
 
 
 
Bəs çəki matrisinin köməyilə 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əyilə 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  
LAYİHƏ

---

 
 
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əlli 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 Maximus 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ә
 
LAYİHƏ

---