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Ə