İnformatika, Modelləşdirmə

Qraf və ağac modelləri: yolları saymağın asan üsulu

Yönəli qrafda başlanğıcdan sona neçə yol olduğunu tez saymağı, məcburi məntəqəli marşrutları hesablamağı və ağacı oxumağı öyrənəcəksən.

Oxumaq üçün 4 dəqiqə

Süni intellektlə hazırlanmış şəkil: yuxarıdan görünən şəhər məhəlləsi, kəsişən küçələr və onlarda hərəkət edən maşınlar.

Birtərəfli küçə ilə bir istiqamətdə rahat keçirsən, amma həmin küçə ilə geri qayıda bilmirsən. Xəritədə bunu ox göstərir. Bir neçə belə küçə bir-birinə qoşulanda maraqlı sual çıxır: evdən məktəbə neçə müxtəlif yolla getmək olar?

Kompüterindəki qovluqlara da bax. Diskdə qovluq var, onun içində başqa qovluqlar, onların içində də fayllar. Kök qovluqdan başqa hər qovluq yalnız bir qovluğun içində yerləşir, ona görə də bu quruluş budaqlanan ağaca bənzəyir.

Hər iki halda nöqtələr və onları birləşdirən xətlər var. Bu mövzu onları oxumağı və yolları bir-bir yazmadan saymağı öyrədir.

Niyə lazımdır

Marşrutları əl ilə sadalayanda birini unutmaq və ya ikisini təkrar saymaq çox asandır. Toplama üsulunda isə hər təpəyə bir ədəd yazırsan və yollar çox olanda da cavab dəqiq çıxır. İmtahanda bu, həm vaxta qənaətdir, həm də hesab səhvinə qarşı sığortadır.

Ağac modeli isə qovluqlar, ailə şəcərəsi, olimpiya sistemli turnir cədvəli kimi pillə-pillə qurulan hər şeyi oxumağa kömək edir: kim kimin altındadır, harada budaq bitir.

İmtahan bu mövzuda nə soruşur?

İmtahanda sənə birtərəfli yolların cədvəli və ya qonşuluq matrisi verilir. Başlanğıcdan sona neçə müxtəlif marşrut olduğunu hesablayırsan. Bəzi tapşırıqlarda marşrutun müəyyən məntəqədən keçməsi də tələb olunur. Bunun üçün əlaqələrin istiqamətini oxumağı, hər məntəqəyə çatan yolları saymağı və nəticələri düzgün birləşdirməyi bacarmalısan.

Qayda

Qraf obyektləri və onların əlaqələrini göstərir: obyekt təpə ilə, birbaşa əlaqə isə tillə təsvir edilir. Aralarında til olan təpələr qonşudur.
Yönəli qraf istiqamətli əlaqələrdən qurulur. Oxla göstərilən əlaqəyə qövs deyilir. $U\to V$ keçidi avtomatik olaraq əks istiqamətdə hərəkətə icazə vermir.
Qonşuluq matrisi oxunarkən sətir başlanğıcı, sütun sonu göstərir: $1$ birbaşa keçidin mövcudluğunu, $0$ isə yoxluğunu bildirir. Yönəli qrafda matrisin simmetrik olması vacib deyil.
Yol əlaqələr boyunca ardıcıl hərəkəti göstərir. Başlanğıca qayıdan qapalı yol dövrə yaradır. Yönəldilməmiş qrafda hər təpədən digərinə çatmaq mümkündürsə, qraf bağlantılıdır.
Ağac bağlantılı və dövrəsiz qrafdır; iki təpəni birləşdirən yeganə sadə yol var. Köklü ağacda seçilmiş başlanğıc kökdür; kökdən başqa hər təpənin bir valideyni olur. Övladı olmayan təpə yarpaqdır.
Çəkili qraf əlaqələrə məsafə və ya xərc kimi ədədlər bağlayır. Marşrutun ümumi çəkisini hesablamaq üçün keçdiyin tillərin çəkilərini topla.
Yolların sayı dövrəsiz yönəli qrafda toplamaqla hesablanır. Başlanğıca $1$ yaz; digər təpənin qiyməti ona birbaşa keçidi olan təpələrdəki qiymətlərin cəmidir. Əvvəl həmin əvvəlki təpələrin qiymətlərini hesabla. Başlanğıcdan çatılmayan təpədə qiymət $0$ olur.
Məcburi məntəqə olduqda dövrəsiz yönəli qrafda iki hissəni ayrıca say: başlanğıcdan həmin məntəqəyə $a$ , oradan sona $b$ yol varsa, cavab $a\times b$ olar.

Tapşırıqlarda işlənən düsturlar

Öyrənilməli düstur

N=p\times q

Dövrəsi olmayan yönəldilmiş qrafda $p$ başlanğıcdan tələb olunan aralıq təpəyə, $q$ isə həmin təpədən sona gedən yolların sayıdır; $N$ bu təpədən keçən marşrutların ümumi sayını göstərir. Bu sayları tapmaq üçün başlanğıca $1$ yaz, sonra hər təpəyə daxil olan qövslərin başlanğıclarındakı sayları topla.

Öyrənilməli düstur

f(s)=1,\qquad f(v)=\sum_{u\to v}f(u)\quad(v\ne s)

Dövrəsi olmayan yönəldilmiş qrafda $s$ başlanğıc təpə, $f(v)$ isə oradan $v$ təpəsinə gedən yolların sayıdır. Matrisdəki $1$ -lərə əsasən qövsləri müəyyən et və hər təpənin sayını ona gələn qövslərin başlanğıclarındakı saylar hesablandıqdan sonra tap.

Yolları özün say

Hər sualda cavabı ədədlə yaz. Başlanğıca $1$ yaz və təpələri növbə ilə doldur.

Nümunələr

Yalnız

S\to U

S\to V

U\to V

U\to T

V\to T

keçidləri var. S-dən T-yə neçə yol gedir? U-ya

1

, V-yə

1+1=2

yol çatır. T-yə gələn yolların sayı

1+2=3

olur.

Yalnız $S\to U$ , $S\to X$ , $U\to X$ , $X\to V$ , $X\to T$ , $V\to T$ keçidləri var. X-dən keçərək S-dən T-yə neçə marşrut qurmaq olar? X-ə birbaşa və U vasitəsilə $2$ yol var. X-dən T-yə də birbaşa və V vasitəsilə $2$ yol var. Nəticə $2\times2=4$ olur.

Ağacın kökü R, onun övladları U və V, U-nun övladı isə W-dir. Başqa təpə yoxdur. Yarpaqlar hansılardır? V və W-nin övladı yoxdur, deməli, $2$ yarpaq var. U yarpaq deyil.

Tipik səhv

T-yə $2$ ox daxil olur, deməli, S-dən T-yə $2$ yol var.

Keçidlər: $S\to A$ , $S\to B$ , $A\to B$ , $A\to T$ , $B\to T$ . A-ya $1$ , B-yə $1+1=2$ yol çatır, T-yə isə $1+2=3$ yol gedir.

Məntəqəyə daxil olan oxların sayını yolların sayı ilə qarışdırma: bir oxun başlanğıcına bir neçə marşrutla çatmaq mümkündür. Ona görə oxların sayını yox, onların başlanğıcındakı qiymətləri topla.

Matrisdə də diqqətli ol: sətir başlanğıcdır, sütun sondur, yerlərini dəyişmə. Məcburi məntəqədə isə iki hissənin saylarını toplamaq əvəzinə vur, çünki hər başlanğıc hissəsi hər son hissə ilə birləşir.

Özünü yoxla

Dövrəsiz yönəli qrafda T-yə yalnız A, B və C-dən qövs gəlir. S-dən A-ya $4$ , B-yə $2$ yol var, C-yə isə çatmaq mümkün deyil. S-dən T-yə neçə yol var?

Dövrəsiz yönəli qrafda S-dən M-ə $3$ , M-dən T-yə $5$ yol var. S-dən T-yə M-dən keçən neçə marşrut qura bilərsən?

Köklü ağacda K-nın övladları L və M, L-in övladı N, N-in övladları isə P və Q-dur. Başqa təpə yoxdur. Yarpaqları seç.

Bu mövzu üzrə sınaq

Bu mövzunun tapşırıqlarını həll et və hər birinin izahına bax.

Mövzu üzrə sınaq, I qrup (Rİ)

Digər mövzular

Bütün İnformatika mövzuları

İnformatikaModellər və cədvəllə məntiqi həllİmtahanda verilən şərtlərdən obyektlərin sırasını, yerini və ya kimə aid olduğunu müəyyənləşdirirsən.

Dərslikdə bu mövzu

Dərslik: İnformatika, 9-cu sinif, «Qraf informasiya modeli», səh. 102
Dərslik: İnformatika, 9-cu sinif, «Qraf məsələləri», səh. 106
Dərslik: İnformatika, 8-ci sinif, «İnformasiya modelinin ağac forması», səh. 59
Dərslik: İnformatika, 8-ci sinif, «Ağacşəkilli struktur əsasında məsələ həlli», səh. 66