Qraf (riyaziyyat)
Bu məqaləni vikiləşdirmək lazımdır. |
Qraf (riyaziyyat) - (ing.graph, ru. граф) - proqramlaşdırmada: öz aralarında ixtiyari qaydada birləşmiş (tillər vasitəsilə) müəyyən sayda (sıfır da ola bilər) təpədən ibarət olan verilənlər strukturu. Qrafın istənilən iki təpəsi (düyün) tillə birləşdirilə və ya birləşdirilməyə bilər. 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 rabitəli adlanır. Qrafin təpələrinin və tillərinin hər hansı altçoxluğuna altqraf deyilir. Qrafların çoxlu növləri vardır: çəkili qraflar – hər bir tilinə müəyyən əmsal (çəki) təyin olunur; yönəldilmiş (oriyentasiyalı) qraflar və ya diqraflar – hər bir tilin müəyyən istiqaməti olur, yəni til B təpəsindən A təpəsinə yox, A təpəsindən B təpəsinə gedir.
1. Qraflar
1.1 Əsas anlayışlar və qrafların növləri
Riyaziyyat əşyaların məzmunu ilə yox, onların strukturu ilə əməliyyatlar aparır və onları tam verilənlər vasitəsilə təsvir edir. Əşyanın keyfiyyətləri və xüsusiyyətlərindən kənarlaşmaq həmin əşyanın bünövrəsini, onu ilk görünüşdə ondan fərqli digər əşyalarla bir sıraya qoymağa imkan verən ayırlmaz hissəsini ortaya çıxarmağa icazə verir. Qraflar nəzəriyyəsi riyaziyyatın məhz bu kənarlaşmaq prinsipi istifadə edilən bölməsidir - əşyanın nə olduğu vacib deyil, onun yalnız qraf olub-olmaması, yəni qraf üçün vacib olan keyfiyyətlərə malik olub-olmaması vacibdir.
Qrafların təsvir olunmasına keçməmişdən əvvəl bəzi misallara baxaq, qrafa tərif verək və qraflar nəzəriyyəsinin əsas anlayışları ilə tanış olaq. Burada qraflar nəzəriyyəsinin bütün anlayışlarına baxa bilməyəcəyik (buna ehtiyac da yoxdur), amma bizə gələcəkdə lazım ola biləcək böyük hissəsini gözdən keçirəcəyik.
Gündəlik həyatda biz qraf strukturuna malik olan obyektlərlə tez-tez təmasda oluruq. Belə obyektlərə fərqli cür ictimai nəqliyyat marşrutlarını aid etmək olar – metropoliten sistemi, avtobus marşrutları və s. Proqramçıya kompüter şəbəkəsi xüsusən tanışdır və bu şəbəkə özü də qrafdır. (bax şək. 1). Bu iki anlayışın ortaq nöqtəsi hər ikisində xətlərlə birləşmiş nöqtələrin olmasıdır. Kompyuter şəbəkəsində bu nöqtələr ayrı-ayrı serverlər, xətlər isə fərqli elektrik siqnallarıdır. Metropolitendə nöqtələr stansiyalar, xətlər isə stansiyalar arasındakı tunellərdir. Qraflar nəzəriyyəsində nöqtələr təpələr və ya düyünlər, xətlər isə tillər və ya qövslər adlanır. Beləlkiklə, qraf tillərlər birləşmiş təpələr məcmuəsidir.
Kompyuter şəbəkələrinə qayıdaq. Bu şəbəkə şərti olaraq bir neçə kompüter və onları birləşdirən xətlər kimi göstərilə bilən müəyyən topologiyaya məxsusdur. Yuxarıdakı şəkildə taməlaqəli topologiya göstərilib.
Belə şəbəkə faktiki olaraq qrafdır. Beş kompüter beş təpə, onlar arasındakı birləşdirici xətlər (elektrik siqnallarının ötürülməsi yolları) isə tillərdir. Kompyuterləri təpələrlə əvəz etsək, biz riyazi obyekt – qraf alarıq. Bu qrafın 10 tili və 5 təpəsi olacaq. Təpələri şəkildəki kimi adlandırmaq vacib deyil, bunu ixtiyari üsulla da etmək olar.
Qraflar nəzəriyyəsində istifadə edilən bəzi vacib anlayışlar:
· G=(V, E), burada G – qraf, V- onun təpələri, E – tillər;
· |V| - sıra (təpələrin sayı);
· |E| - qrafın ölçüsü (tillərin sayı).
Bizim halımıda (şək. 1) |V| = 5, |E| = 10 olur.
Hər hansı istənilən bir təpədən digər istənilən təpəyə getmək mümkündürsə, deməli bu qraf yönəldilməmiş (oriyentasiyasız) əlaqəli qraf adlanır (şək. 1). Əgər qraf əlaqəlidirsə, amma bu şərt yerinə yetirilmirsə, onda bu qraf yönəldilmiş (oriyentasiyalı) və ya orqraf adlanır (şək. 2). Orqrafın tilləri adətən qövs adlandırılır.
Orientasiyalı və oriyentasiyasız qraflarda təpənin qüvvəti anlayışı istifadə edilir. Təpənin qüvvəti – həmin təpəni digər təpələrlə birləşdirən tillərin sayına deyilir. Təpənin giriş qüvvəti – həmin təpəyə daxil olan tillərin sayı, çıxış qüvvəti – həmin təpədən çıxan tillərin sayıdır. Qrafın bütün qüvvətlərinin cəmi bütün tillərinin sayının ikiqatına bərabərdi. Şəkil 2-dəki qraf üçün bütün qüvvətlərin cəmi 20-ə bərabərdir.
Orientasiyasız qrafdan fərqli olaraq oriyentasiyalı qrafda h təpəsindən s təpəsinə aralıq təpələri keçmədən yalnız qövs (til) h təpəsindən çıxıb s təpəsinə daxil olursa, hərəkət etmək olur.
Orientasiyalı qraf növbəti qeyd olunma formasına məxsusdurlar:
G=(V, A), burada V – təpələr, A – tillərin istiqamətidir.
Qrafların üçüncü tipi – qarışıq qraflardır (şək. 3). Belə qrafların həm istiqamətlənmiş, həm də istiqamətlənməmiş tilləri olur. Formal olaraq bu cür qraflar belə yazılır:
G=(V, E, A), burada V – təpələr, E – tillərin sayı, A – tillərin istiqamətidir.
Bu şəkildə həm istiqamətlənmiş təpələr - [(e, a), (e, c), (a, b), (c, a), (d, b)], həm də istiqamətlənməmiş təpələr [(e, d), (e, b), (d, c)…] mövcuddur.
Tilin hər iki sonluğu üst-üstə düşürsə, yəni hər hansı bir F təpəsindən çıxan til, elə həmin təpəyə daxil olursa, onda belə til ilmə adlanır (şək 4.).
İki və ya daha çox qraf ilk görünüşdə öz strukturlarına görə fərqli görünə bilərlər, bu əsasən onların fərqli cür təsvir olunmasına görə yaranır. Bu həmişə belə olmur. İki qraf götürək (şək 5.). Onlar bir-birlərinə ekvivalentdirlər. Çünki, bu qraflardan hər birinin strukturunu dəyişdirmədən, digərini qura bilərik. Belə qraflar izomorf qraflar adlanır, yəni bir qrafda müəyyən sayda tilə məxsus olan təpə digər qrafda identik təpəyə sahib olur.
Qrafın hər tilinə qarşılıq olaraq tilin çəkisi adlı müəyyən əmsal qarşı qoyulursa, belə qraf çəkili qraf adlanır. Fərqli məsələlərdə çəki qismində fərqli ölçülər verilə bilər, məsələn, marşrutların uzunluğu, qiyməti və s. Qrafların qrafiki təsvirində çəki əmsalları bir qayda olaraq tillərin yanında göstərilir.
Nəzərdən keçirdiyimiz istənilən qrafda yol anlayışını fərqləndirə bilərik, həm də tək bir yol yox, bir neçə yol. Yol – hər biri qonşu təpə ilə til vasitəsilə birləşdirilən təpələr ardıcıllığıdır. Əgər ilk və son təpələr üst-üstə düşürsə, belə yol dövr adlanır. Yolun uzunluğu onu təşkil edən tillərin sayı ilə müəyyən edilir. Məsələn, şək 4.a-da [(e), (a), (b), (c)] ardıcıllığı yoldur. Bu yol altqrafdır, çünki o altqraflıq şərtini ödəyir. Bu şərt belədir: G’=(V’, E’) qrafı o vaxt G=(V, E) qrafının altqrafı adlanır ki, V’ və E’ V, E-yə aid olsun.
Qraf bir çox riyazi obyektlər kimi kompüterdə göstərilə və onun yaddaşında saxlanıla bilər. Qrafların interpretasiyasının bir çox üsulu var, onlardan ən məşhurları isə bunlardır:
· Qonşuluq matrisi;
· İdentiklik matrisi;
· Qonşuluq siyahısı;
· Tillər siyahısı.
İlk iki metodun istifadəsi qrafın ikiölçülü massiv (matris) kimi göstərilməsini nəzərdə tutur. Bu matrislərin ölçüləri isə baxılan qrafdakı təpələr və tillərin sayından asılı olur. Beləliklə, nxn ölçülü qonşuluq matrisinin ölçüsündə n təpələrin sayı, mxn ölçülü identiklik matrisində isə n təpələrin, m isə tillərin sayıdır.
1.2 Qonşuluq matrisi
Qrafın qonşuluq matrisi – hər bir elementi ya 0, ya da 1 qiyməti alan kvadrat matrisə deyilir. Qrafı qonşuluq matrisi kimi təsvir etməmişdən əvvəl, belə matrisin sadə misalına baxaq. (şək. 6)
Bu ikilik kvadrat matrisdir, çünki onun sətirlərinin sayı sütunlarının sayına bərabərdir və onun istənilən elementi ya 1, ya da ki 0 qiymətini alıb. İlk sətir və ilk sütun (onlar matrisin tərkibinə daxil deyillər və burada sadəcə anlaşılmanın rahatlığı üçün təsvir ediliblər) kəsişmələrində elementlər yerləşən rəqəmlərdən ibarətdir və bu sətir və sütunlar elementlərin indeksini müəyyənləşdirirlər. Belə matris olduğu halda müvafiq matris qurmaq elə də çətin deyil.
Aşağıda (şək 7.) həmin 4x4 ölçülü qonşuluq matrisi təsvir edilib. Mavi rənglə seçilmiş rəqəmləri matrisin qraf təsviri olan sağdakı qarışıq qrafın təpələri kimi qəbul etmək olar.
Qrafın qrafiki təsviri üçün qonşuluq matrisinə görə onun təpələrini saymaq bacarığına və növbəti qaydanı bilməyə ehtiyac var. Bir təpədən digərinə keçid mümkün olanda (yəni til olanda), xanaya 1 yazılır, keçid mümkün olmadıqda isə 0. Deyilənləri formallaşdırsaq alarıq ki - əgər i-dən j-yə til varsa, A[i][j]=1, əks halda A[i][j]=0. Göründüyü kimi, əsas diaqonalın bütün elementləri 0-a bərabərdir, bu qrafda ilmələrin olmamasının nəticəsidir. Lakin, bu həmişə belə olmaya bilər.
Proqram yazılışında qonşuluq matrisi adi nxn ölçüsünə malik ikiölçülü massiv kimi göstərilir. Burada n – qrafın təpələrinin sayıdır. C++ dilində bu matrisi belə yazmaq mümkündür:
int graph[n][n] =
{
{0, 1, 0, 1},
{0, 0, 1, 1},
{0, 1, 0, 0},
{1, 0, 1, 0}
};
Əgər qraf əvvəlcədən naməlumdursa və onu istifadəçi müəyyən edirsə, ikiölçülü massivin daxil edilməsi üçün əl ilə daxiletmə yaratmaq lazımdır.
Qrafı qonşuluq matrisi formasında təsvir etmək üçün O(|V|2) yaddaş lazımdır. Çünki matrisin ölçüsü əvvəl də dediyimiz kimi bütün təpələrin kvadratına bərabərdir. Və əgər təpələrə nisbətdə qrafın tillərinin sayı çox deyilsə, onda matrisin bir çox elementləri sıfıra bərabər olacaq və beləliklə bu qədər yaddaş yerinin istifadəsi məqsədəuyğun olmayacaq. Elə tip qonşuluq matrisləri üçün xüsusi təqdimat forması mövcuddur.
1.3 Qonşuluq siyahısı
Qonşuluq siyahıları qonşuluq matrislərinə nisbətən yaddaş istifadəsinə daha az tələbkardırlar vəə onların saxlanması üçün O(|V|+|E|) yaddaş lazımdır. Belə siyahını qrafiki olaraq iki sütunu və qrafın təpələrindən çox olmayan sətri olan cədvəl olaraq göstərə bilərik. Misal kimi qarışıq qrafı götürək:
Bu qrafda 6 təpə (|V|) və 5 til (|E|) var. Sonunculardan 2 til istiqamətlənmiş və 3-ü istiqamətlənməmişdir. Həmçinin hər təpədən ən azı bir til digər təpəyə daxil olur. Buradan belə nəticə çıxır ki, qrafın qonşuluq siyahısında |V| sətir olacaq.
| Çıxış təpəsi | Giriş təpəsi |
| 1 | 5 |
| 2 | 6 |
| 3 | 2, 5 |
| 4 | 5 |
| 5 | 1, 4 |
| 6 | 2 |
İndi isə qonşuluq siyahısının proqram realizasiyasına keçək. Təpə və tillərin sayı klaviatura vasitəsilə daxil ediləcəyi üçün məhdudiyyətlər verməliyik. Yəni, bu məhdudiyyətlərdən birincisi maksimum təpə sayını (Vmax), digəri isə maksimum til sayını(Emax) müəyyənləşdirməlidir. Növbəti addımda bizə üç birölçülü tam ədədlər massivi lazım olacaq:
· terminal[1..Emax] – tillərin daxil olduğu təpələri saxlayır;
· next [1..Emax] – terminal massivinin elementlərinə daxil olan göstəriciləri saxlayır;
· head[1..Vmax] – altsiyahıların, yəni terminal massivinin bir i-ci təpədə qonşu olan bütün təpələrin sayılmasının başlandığı təpələrə olan göstəriciləri saxlayır.
Proqramda iki hissəni ayırmaq lazımdır – daha sonra qonşuluq siyahısına əlavə ediləcək tillərin daxil edilməsi və alınan qonşuluq siyahısının ekrana verilməsi. Bunları C++ dilində belə realizə etmək olar:
const int Vmax=100, Emax=Vmax*2;
int head[Vmax];
int next_el[Emax];
int terminal[Emax];
int n, m, i, j, k, v, u;
char r;
void Add(int v, int u) //tilin əlavə edilməsi
{
k=k+1;
terminal[k]=u;
next_el[k]=head[v];
head[v]=k;
}
void main() //əsas funksiya
{
k=0;
cout<<"Təpələrin sayı >> "; cin>>n;
cout<<"Кол. ребер >> "; cin>>m;
cout<<"Qonşu təpələri daxil edin:"<<endl;
for (i=0; i<m; i++) {
cin>>v>>u;
cout<<"Til istiqamətlənibmi.? (y/n) >> "; cin>>r;
if (r=='y') Add(v, u);
else {
Add(v, u);
Add(u, v); }
cout<<"..."<<endl;
}
cout<<"Qrafın qonşuluq siyahısı:";
for (i=0; i<n+1; i++) //qonşuluq siyahısının xaric edilməsi
{
j=head[i];
if (i) cout<<i<<"->";
while (j>0) {
if (!next_el[j]) cout<<terminal[j];
else cout<<terminal[j]<<", ";
j=next_el[j];
}
cout<<endl; }}
İlk fikir verməli olduğumuz addım qrafın n təpəsinin və m tilinin daxil edilməsinin istənməsidir (istifadəçi əvvəldən bu məlumatları bilməlidir). Daha sonra tillərin (qonşu təpələrin) daxil edilməsi dövrü başladılır. Bu dövrdəki şərt ona görə lazımdır ki, istifadəçi hansı tilin daxil edildiyini bilsin. Əgər istiqamətləndirilmiş til daxil edilirsə, add funksiyasına 1 dəfə müraciət edilir, əgər çağırılmırsa 2 dəfə, bu zaman funksiya həm i təpəsindən v təpəsinə, həm də v təpəsindən i təpəsinə tilin olduğu haqqında məlumat daxil edir. Qonşuluq siyahısı formalaşdırılandan sonra, proqram bu siyahını ekrana verir. Bunun üçün də 1-dən n-ə qədər dövr istifadə edilir ki, burada da n – təpələrin sayıdır. Həmçinin burada növbəti mövcud olmayan i-ci təpəyə müraciət edən göstərici olduğu halda dövrü kəsən şərt də daxil edilib.
Add funksiyası əvvəlcə boş olan qonşuluq siyahısına elementlərin daxil edilməsini həyata keçirir:
Add(v, u) {
k=k+1;
terminal[k]=u;
next[k]=head[v];
head[v]=k;}
Bunu həyata keçirmək üçün formal parametrlər, köməkçi k dəyişəni və üç birölçülü tam ədədlər massivi üzərində əməliyyatlar aparılır. K dəyişəninin qiyməti 1 vahid artırılır. Daha sonra terminal massivinin k-cı elementinə hər hansı til üçün sonuncu olan u təpəsi yazılır. Üçüncü sətirdə next massivinin k-cı elementinə terminal massivinin növbəti elementi mənimsədilir. Sonda isə head massivin başlanğıc elementlərinə - hər hansı i-ci təpəsi olan qonşu təpəli altsiyahılara göstəricilərlə doldurulur.
İ-ci sətir və 2-ci sütunun kəsişməsindəki xanaya bir neçə element yazıla bildiyi üçün (bir neçə qonşu təpələrə uyğundur) qonşuluq siyahısındakı hər bir sətri onun altsiyahısı adlandıracayıq. Beləliklə, çıxışa verilmiş qonşuluq siyahısında altsiyahıların elementləri əksinə sıralanmış olacaq. Amma, bir qayda olaraq, (altsiyahılarda) qonşu təpələrin çıxış ardıcıllığı sadəcə vacib deyil.
1.3 Tillər siyahısı
Hər sətrində iki qonşu təpə və onları birləşdirən tilin çəkisi yazılan siyahı qrafın tilləri siyahısı adlanır. G=(V, E) əlaqəli qrafını götürək və E tillər çoxluğunu iki sinifə - d və k siniflərinə bölək, burada d – G qrafının ancaq oriyentasiyasız tillərini özündə saxlayan altçoxluq, k – isə oriyentasiyasız tilləri özündə saxlayan altçoxluqdur. Fərz edək ki, hər hansı p ölçüsü d altçoluğuna daxil olan bütün tillərin, s ölçüsü isə k altçoluğuna daxil olan bütün tillərin sayına uyğundur. Bu zaman G qrafı üçün tillər siyahısının hündürlüyü s+p*2 bərabər olacaq. Digər sözlərlə, tillər siyahısındakı sətirlərin sayı həmişə oriyentasiyalı tillərin oriyentasiyasız tillərin ikiqatı ilə cəminə bərabər olmalıdır. Bu fikir əvvəlki düsturdan alınır, daha dəqiq desək, qrafın bu cür təqdimedilmə üsulu özündə hər sətirdə iki qonşu təpənin və həm v və u təpələrini birləşdirən və həm v-dən u-ya, həm də u-dan v-yə gedən oriyentasiyasız tilin saxlanmasını nəzərdə tutur.
Özündə 5 təpə, 4 til və hər tilə uyğun tam qiymət (rahat olması üçün bu qiymətlər təpələrin nömrələrindən təşkil edilib) müvafiq qoyulan qarışıq qrafı nəzərdən keçirək (şək. 9).
Bu qrafda 3 istiqamətlənmiş və 1 istiqamətlənməmiş til var. Bu qiymətləri düsturda yerinə qoysaq, tillər siyahısının hündürlüyünü alarıq: 3+1*2=5.
| 1 | 3 | 13 |
| 1 | 4 | 14 |
| 2 | 1 | 12 |
| 3 | 1 | 13 |
| 5 | 1 | 15 |
Verilmiş qrafın tillər siyahısını belə görünür. Bu nx3 ölçülü cədvəldə n=s+p*2=3+1*2=5. İlk sütunun elementləri artan sıra ilə düzüldüyü halda, ikinci sütundakı elementlərin ardıcıllığı birinci sütundan, üçüncü sütundakı elementlərin ardıcıllığı isə ikinci sütundan asılıdır.
Tillər siyahısının proqram realizasiyası qonşuluq siyahısının realizasiyasına bənzəyir. Sonuncuda olduğu kimi tillər siyahısında da, ilk öncə məlumatların daxil edilməsini təşkil etmək lazımdır. Bu məlumatlar xüsusi funksiyanın köməyi ilə massivlərə düzüləcəklər. İkinci addımda alınmış siyahını ekrana çıxartmaq lazımdır.
Qonşuluq siyahısında ancaq qonşu təpələr saxlandığı halda, burada onlardan başqa həmin təpələrə insidentliyə məxsus olan tillərin çəkiləri də saxlanır. Bunun üçün də əlavə massiv lazım olur. Həmçinin bu metod təpələrin xaric edilməsinin daha ciddi üsulunu tələb edir, çünki, əgər qonşuluq siyahısında ardıcıllıq ancaq sətirlərdə pozulurdusa, analoji üsulun istifadəsi sütunlardakı ardıcıllığın pozulmasına gətirib çıxara bilər. Buna görə də tillərin əlavə edilməsi funksiyasını başqa cür yazmaq lazımdır.
const int Vmax=100,
Emax=Vmax*(Vmax-1)/2; //qrafın tam olduğu halda
int terminal[Emax], weight[Emax], point[Emax];
int head[Vmax], last[Vmax];
int n, m, v, u, w, k=0, i;
char r;
void Add(int v, int u, int w) //tilin əlavə edilməsi
{
k=k+1;
terminal[k]=u; weight[k]=w;
//əgər v təpəsi yenidirsə,
//onun ilk qonşu təpəsi k nömrəsini alacaq
if (head[v]==0) head[v]=k;
//əgər təpəyə artıq baxılıbsa
//ona qonşu olan növbəti təpə k nömrəsini alacaq
if (last[v]!=0) point[last[v]]=k;
last[v]=k;
}
void main() //əsas funksiya
{
cout<<"Təpə sayı >> "; cin>>n;
cout<<"Til sayı >> "; cin>>m;
cout<<"Tilləri və onların çəkilərini daxil edin (v, u, w):\n";
for (i=0; i<m; i++) {
cin>>v>>u>>w;
cout<<"Til oriyentasıya olunub mu? (y/n) >> "; cin>>r;
if (r=='y') Add(v, u, w);
else {
Add(v, u, w);
Add(u, v, w);
}
cout<<"..."<<endl;
}
m=m*2;
cout<<"Qrafın tilləri siyahısı:\n";
for (i=0; i<m; i++) //Tillər siyahısının xaric edilməsi
{
k=head[i];
while (k>0)
{
cout<<"("<<i<<"->"<<terminal[k]<<")$="<<weight[k]<<endl;
k=point[k];
}
}
}
Qrafda maksimum təpə sayı Vmax ilə, maksimum til sayı isə Emax ilə işarə edilib. Son sabit Vmax*(Vmax-1)/2 ifadəsi ilə inisializasiya edilir və bu ifadə təpələrin bilindiyi halda tam qrafda tillərin sayını hesablayır. Növbəti sətirlərdə proqramda 5 massiv göstərilir:
· terminal – tillərin daxil olduğu təpələr massivi;
· weight – tillərin çəkiləri massivi;
· head[i]=k – i-ci təpə üçün terminal və weight massivlərinin k-cı elementlərini saxayır. Burada terminal[k] – i-ci təpə ilə qonşu olan ilk təpə, weight[k] – isə ona insident olan tilin çəkisidir;
· last[i]=k – i-ci təpə üçün terminal və weight massivlərinin k-cı elementlərini saxayır. Burada terminal[k] – i-ci təpə ilə qonşu olan son təpə, weight[k] – isə ona insident olan tilin çəkisidir;
· point[i]=k – i-ci təpə üçün terminal və weight massivlərinin k-cı elementlərini saxayır. Burada terminal[k] – i-ci təpə ilə qonşu olan növbəti təpə, weight[k] – isə ona insident olan tilin çəkisidir.
Təpə (n) və tillərin (m) daxil edilməsindən sonra hər addımında istifadəçinin klaviaturadan iki qonşu təpə və onların arasındakı tilin çəkisini daxil etdiyi dövr işə düşür. Əgər til oriyentasiya olunmuşdursa, onda siyahıya tillərin əlavə edilmə funksiyası (Add) bir dəfə, əgər oriyentasiya olunmamışdırsa iki dəfə çağırılır. Funksiyanın ümumi çağırış sayı elə həmin s+(p*2) düsturu ilə hesablanır ki, burada s – qrafın oriyentasiya olunmuş tilləri sayı, p isə oriyentasiya edilməmiş tillərinin sayıdır. Tillər siyahısını formalaşdırandan sonra m dəyişənini iki dəfə artırmaq lazımdır ki, tam oriyentasiya edilməmiş qraf daxil edildiyi halda onun hündürlüyü 0+(m*2) ilə hesablanır.
Bundan sonra təkcə alınmış konstruksiyanı ekrana çıxartmaq lazımdır. İ təpəsi ilə qonşu olan ilk təpənin nömrəsinə head[i] elementi işarə edir, deməli xarici dövrün hər yeni iterasiyası bu elementin götürülməsi ilə başlamalıdır (k=head[i]). Daxili dövr isə i təpəsi ilə heç bir qonşu təpə tapılmadıqda (k sıfıra bərabər olduqda) kəsilir, xarici dövr isə tillər siyahısının çıxışa verilib bitirildiyi anda.
1.5 İdentiklik matrisi
Bunu yadda saxlamaq lazımdır ki, g tilinin və u və y təpələrinin hər birinin g tilinə identik olduğunu ancaq g tilinin u və y təpələrini birləşdirdiyi halda demək olar. İdentiklik matrisi əvvəlki qonşuluq matrisi üsuluna oxşar üsulla qurulur. Yəni qonşuluq matrisi n təpəli və nxn ölçülü olduğu halda, identiklik matrisi n təpəli və m tilli nxm ölçülü olur. Bu halda xanaya qiymət verdikdə təpəni təpə ilə yox, təpəni til ilə qarşı qoymaq lazım olur.
Orientasiya edilməmiş qrafın identiklik matrisinin hər xanasında ya 0, ya da 1 yazılır, oriyentasiyalı qrafın matrisində isə 1, 0 və ya -1 qeyd edilir. İndi isə deyilənləri daha strukturlu şəkildə yazaq:
1. Orientasiya edilməmiş qraf:
· 1 – təpə tilə identikdir;
· 0 – təpə tilə identik deyil.
2. Orientasiyalı qraf:
· 1 – təpə tilə identikdir və onun başlanğıcıdır;
· 0 – təpə tilə identik deyil;
· 1 – təpə tilə identikdir və onun sonudur.
Əvvəlcə oriyentasiya edilməmiş qraf üçün (şək. 10), daha sonra orqraf üçün (şək. 11) identiklik matrisini quraq. Tilləri a-dan e-yə qədər hərflərlə, təpələri isə rəqəmlərlə işarə edək. Qrafın heç bir tili istiqamətlənmiş olmaığı üçün identiklik matrisi ancaq müsbət ədədlərlə doludur.
Orqraf üçün identiklik matrisi biraz başqa görünüşə məxsusdur. Onun hər bir xanasına üç qiymətdən biri yazılır. Hər iki matrisdə sıfırların eyni yerdə yazıldığına diqqət yetirin. Bunun səbəbi hər iki qrafın eyni struktura malik olmasıdır. Amma bəzi müsbət vahidlər mənfiyə çevrilirlər. Məsələn oriyentasiya olunmamış qrafda (1, b) xanası 1 olduğu halda, oriyentasiyalı qrafda bu vahid əks işarə ilə -1 kimi yazılır. Bunun səbəbi ilk dəfə tilinin istiqamətlənməmiş olması, oriyentasiyalı qrafda isə 1 təpəsindən çıxaraq istiqamətlənmiş olmasıdır.
Burada hər bir sütun bir tilə cavabdehdir, buna görə də identiklik matrisi ilə yazılmış qraf həmişə bu göstəriciyə malik olacaq - istiqamətlənmiş til üçün matrisin istənilən sütunu ya iki vahidə, ya da 1 və -1 qiymətlərinə malik olaraq, digər xanalar 0 olur.
Proqramda identiklik matrisi qonşuluq matrisi kimi, daha dəqiq desək ikiölçülü massivlə verilir. Onun elementləri isə ya daxil edilmə zamanı, ya da proqramın işə düşməsi ilə inisializasiya edilirlər.
-
Qraf nümunəsi -
Qraf nümunəsi -
Qraf nümunəsi -
Qraf nümunəsi -
Qraf nümunəsi -
Qraf nümunəsi
.png)
Ədəbiyyat redaktə
- İsmayıl Calallı (Sadıqov), “İnformatika terminlərinin izahlı lüğəti”, 2017, “Bakı” nəşriyyatı, 996 s.