Qraf (riyaziyyat)
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. Kompüter şə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. Kompüter şə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. Kompüterlə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ə ə