Qrafik hansı elementlərdən ibarətdir? Qrafik (qrafik nəzəriyyə)

Bəzi real obyekt haqqında məlumat müxtəlif yollarla təqdim edilə bilər. IN danışıq nitqi məlumatın şifahi (şifahi) təqdimatından istifadə edirik. Burada, məsələn, bölgəmizin şifahi təsviri belədir: “Volqoqrad vilayəti inzibati-ərazi vahidlərindən - 33 rayon və 6 rayon əhəmiyyətli şəhərdən ibarətdir. Şəhərlər: Volqoqrad, Voljski, Kamışin, Frolovo, Mixaylovka, Uryupinsk. Bu təsvirlə bir şəhərdən digərinə necə gedə biləcəyinizi təsəvvür edə bilərsinizmi? (Şagirdlər nəticə çıxarırlar.) Aşağıdakı diaqramdan daha aydın görünür (slayd 2), məsələn, suala cavab vermək üçün istifadə edilə bilər: Volqoqraddan Uryupinska getmək üçün hansı şəhərlərdən keçmək lazımdır.

“Qrafik” və şəbəkələr anlayışı formalaşdırılır. Onun komponentləri vurğulanır: təpələr və kənarlar. (Slayd 3)

Qrafik qovşaqların (təpələrin) və onlar arasındakı əlaqənin (kənarların) məcmusudur.

Şəbəkə təpələrin çoxdan çoxa prinsipinə uyğun olaraq bir-birinə bağlandığı bir qrafikdir.

Qrafik haqqında məlumatı kompüter yaddaşında necə əks etdirmək olar? Onun şəkil (rastr və ya vektor) kimi saxlanması səmərəsizdir, çünki şəkil kompüter deyil, şəxs tərəfindən qavranmaq üçün nəzərdə tutulub. Kompüter üçün məlumatı cədvəllər şəklində saxlamaq ən əlverişlidir (massiv də ən sadə cədvəl hesab edilə bilər). Qrafiki təsvir etmək üçün tez-tez qovşaqlar arasında bütün mümkün əlaqələri (təkrarlanma nəzərə alınmadan) təsvir edən kvadrat cədvəldən istifadə olunur. Əgər, məsələn, xəttin kəsişməsində A və sütun B 1 rəqəmi yazılır, bu o deməkdir ki, təpələri birləşdirən kənar var A Və B; bu xanada 0 rəqəmi belə kənarın olmadığını bildirir. Bu cədvəl adlanır bitişiklik matrisi.Şəkildə yol xəritəsi, müvafiq qrafik və onun bitişiklik matrisi göstərilir: (slayd 4)

Əsas diaqonaldakı vahid (boz rənglə vurğulanmış) qrafikin ehtiva etdiyini göstərir bir döngə-eyni təpədə başlayan və bitən kənar.
Qeyd edək ki, bitişiklik matrisi əsas diaqonala görə simmetrikdir, yəni təpədən kənar varsa A yuxarıya B, onda bir kənar da var B V A. Belə bir qrafik deyilir istiqamətsiz- kənarların istiqaməti yoxdur və onların hər biri iki dəfə bitişiklik matrisində nəzərə alınır. Qonşuluq matrisi qovşaqların bir-birinə nisbətən necə yerləşdiyi barədə heç bir məlumat vermir. Yuxarıda göstərilən cədvəl üçün, məsələn, rəqəmlərdəki kimi seçimlər mümkündür. (slayd 5)

Əgər hər bir kənar üçün istiqamət göstərilibsə, qrafik istiqamətləndirilmiş qrafik (və ya diqraf) adlanır. Diqrafın kənarlarına qövslər deyilir. Onun bitişiklik matrisi həmişə simmetrik olmur. A sətri ilə B sütununun kəsişməsindəki vahid A təpəsindən B təpəsinə qədər bir qövs olduğunu göstərir: (slayd 6).

Tez-tez müəyyən bir rəqəm hər bir kənar ilə əlaqələndirilir - kənarın çəkisi. Bu, məsələn, şəhərlər arasındakı məsafə və ya səyahət xərcləri ola bilər. Belə bir qrafik çəkili adlanır. Belə bir qrafik haqqında məlumat kənar çəkiləri ehtiva edən çəki matrisi şəklində saxlanılır: (slayd 7).

Çəkili bir diqraf üçün çəki matrisi həmişə əsas diaqonala görə simmetrik olmur: (slayd 8).

İki qovşaq arasında əlaqə yoxdursa, cədvəl xanasını kağız üzərində boş qoya bilərsiniz və onu kompüter yaddaşında saxlayarkən ona şərti kod yazın, məsələn, 0, –1 və ya çox böyük rəqəm (?), vəzifəsindən asılı olaraq.

İstiqamətləndirilmiş qrafikin başqa bir nümunəsi alqoritm axını diaqramlarıdır. (slayd 9) Alqoritmin sxemi bəzi icraçının idarəetmə prosesinin qrafikidir. Bloklar - bu qrafikin təpələri - ifaçıya verilən fərdi əmrləri, qövslər isə bir əmrdən digərinə keçid ardıcıllığını göstərir.

4. Məlumatın qrafik şəklində təqdim edilməsi

Yəqin ki, kompüter şəbəkələri haqqında bir az məlumatınız var. Ola bilsin ki, məktəb informatika sinifindəki kompüterlər birləşdirilib yerli şəbəkə və ya İnternetdə işləmisiniz və ya xidmətlərdən istifadə etmisiniz E-poçt. Aydındır ki, şəbəkə yalnız kompüterlər bir-biri ilə məlumat ötürmə kanalları ilə bir-birinə bağlı olduqda formalaşır. Şəbəkə abunəçilərinin (kompüterlər və ya ona qoşulmuş digər avtomatik məlumat emalı sistemləri) yerləşdirilməsi və onların bir-birinə qoşulma üsulları şəbəkə konfiqurasiyası adlanır. Nümayiş et Müxtəlif növlər kompüter şəbəkələrinin konfiqurasiyası, məsələn, qrafiklər kimi informasiya modellərindən istifadə etməklə həyata keçirilə bilər. Qrafik bir-birinə xətlərlə bağlanmış nöqtələrin məcmusudur. Nöqtələrə qrafikin təpələri deyilir. Onlar nöqtələr, dairələr, düzbucaqlılar və s. ilə göstərilə bilər. Təpələri birləşdirən xətlər qövslər (istiqamət bir təpədən digərinə verilirsə) və ya kənarlar (istiqamət ikitərəflidirsə, yəni istiqamətlər) adlanır. bərabərdir). Bir kənar (qövs) ilə birləşdirilən iki təpəyə bitişik deyilir. Qrafikin təpələri və kənarları müəyyən ədədi qiymətlərlə xarakterizə edilə bilər. Məsələn, kənarın uzunluğu və ya onun boyunca “keçmənin qiyməti” məlum ola bilər. Belə xüsusiyyətlərə çəki, qrafikə isə çəkili deyilir.

Qrafik, onun təpələrinin çoxluğu, kənarların (qövslərin) çoxluğu verildikdə və hansı təpələrin hansı kənarların (qövslərin) və ola bilsin, təpələrin və kənarların (qövslərin) çəkiləri ilə birləşdirildiyi göstərildikdə unikal şəkildə müəyyən edilir. göstərilir. Bütün bu elementlərin tərifi bu halda rəsmiləşdirmənin mahiyyətini təşkil edir.

Şəkil 3-də qrafiklər şəklində təqdim olunan LAN strukturlarının məlumat modelləri olan müxtəlif növ yerli şəbəkə (LAN) konfiqurasiyaları göstərilir:

Avtobus konfiqurasiyası, ayrı-ayrı abonentlər müəyyən fasilələrlə (K) açıq kanala qoşulduqda, mənbə abunəçidən gələn məlumatlar hər iki istiqamətdə kanal boyunca paylanır;

Zəng konfiqurasiyası, hər bir abunəçi birbaşa iki qonşu abunəçiyə qoşulduqda və məlumat qapalı halqa vasitəsilə, çox vaxt bir istiqamətdə ötürülür;

Ulduz formalı konfiqurasiya, mərkəzində mərkəzi keçid (CC) var, o, ardıcıl olaraq abunəçiləri sorğulayır və onlara məlumat mübadiləsi hüququ verir;

Ağacabənzər konfiqurasiya bir neçə sadə rabitə kanalını bir magistralla birləşdirərək formalaşır;

Tam qoşulmuş konfiqurasiya abunəçilər arasında ən sürətli rabitə marşrutunun seçilməsini təmin edir və idarəetmənin kifayət qədər mürəkkəb olduğu yerlərdə əlverişlidir.

Fig.3 Lokal şəbəkə konfiqurasiyalarının müxtəlif növləri

Qrafik ən aydın şəkildə rəsmlə müəyyən edilir. Bununla belə, rəsmin bütün detalları eyni dərəcədə vacib deyil. Xüsusilə, kənarların həndəsi xüsusiyyətləri (uzunluq, əyrilik və s.), təpələrin forması (nöqtə, dairə, kvadrat, oval və s.) və qarşılıqlı tənzimləmə müstəvidə təpələr. Beləliklə, Şəkil 4 eyni qrafikin iki şəklini göstərir. Bütün təpələr və kənarlar tez-tez təpə və ya xətt üzərində müşayiətedici etiket kimi müəyyən edilir, lakin daxil edilməklə simvollar, onlar təpənin forması və ya rəngi, qalınlığı, xəttin növü və ya rəngi və s. ilə müəyyən edilə bilər.

düyü. 4 Eyni qrafikin müxtəlif şəkilləri

Modelləşdirmə obyektinin elementləri arasında mövcud olan əlaqələri əyani şəkildə göstərmək üçün qrafik şəklində olan informasiya modelindən istifadə oluna bilər. Beləliklə, qrafik obyektin strukturunu modelləşdirmək üçün ən əlverişli formadır, baxmayaraq ki, bu formada onu modelləşdirmək də mümkündür. görünüş, və obyektin davranışı.

Şəkil 5-də hər biri C4H10 düsturu olan, yəni 4 karbon atomundan və 10 hidrogen atomundan ibarət olan butan və izobutan molekullarının modelləri göstərilir. Eyni düstura malik olan butan və izobutan fərqlidir Kimyəvi xassələri, çünki atomların birləşdirilməsi yolları (molekulların quruluşu) fərqlidir. Molekulda atomların düzülüşü müxtəlif yollarla onların əlaqələri qrafiklə yaxşı göstərilə bilər.

Şəkil 5 Butan və izobutan molekullarının modelləri

Qeyd edək ki, kimyada bu cür maddələri təyin etmək üçün çox vaxt struktur formullardan istifadə olunur. Atomların birləşmə qaydası struktur düsturda tire ilə təsvir edilmişdir (hidrogen və digər atomlar arasındakı əlaqə adətən göstərilmir). Struktur formulun qrafikin növlərindən biri sayıla biləcəyini özünüz düşünün. Qrafik şəklində bir fəaliyyət sahəsi və ya biliyə aid anlayışların əlaqələrini göstərmək rahatdır.

Həndəsə kursundan “Dördbucaqlılar” mövzusunun konsepsiya qrafikinə nəzər salın (şək. 6). Yaxşı bir "fırıldaqçı vərəq" deyilmi?

Şəkil 6. “Dördbucaqlılar” mövzusunun konsepsiya qrafiki

Təcrübədə işin növlərini və qaydasını göstərmək üçün tez-tez qrafiklər şəklində modellərdən istifadə olunur. “İş şəbəkəsi qrafiki”, “tikinti şəbəkəsinin qrafiki” kimi terminlərlə tanış ola bilərsiniz. Çox vaxt şifahi və ya cədvəl təsviri ilə yanaşı, şəbəkə diaqramları həm də təpələri xüsusi iş növləri olan qrafik şəklində bir şəkil ilə müşayiət olunur və qövslər onların icrasının mümkün qaydasını müəyyənləşdirir.

Şəbəkə tikintisi qrafikləri hansı işlərin eyni vaxtda həyata keçirilə biləcəyini və əvvəlki mərhələlərin məcburi şəkildə tamamlanmasını tələb edən işləri aydın şəkildə nümayiş etdirir. Bu cür qrafikləri təhlil edərək, bütün işləri başa çatdırmaq üçün lazım olan vaxtı hesablaya, neçə, nə vaxt və hansı iş üçün mütəxəssis və avadanlıq göndərəcəyini planlaşdıra, ən "dar" sahələri müəyyənləşdirə və onlara xüsusi diqqət yetirə bilərsiniz.

Maşınla işləmə üçün qrafikləri simvolik olaraq bu kənarın hansı təpələri birləşdirdiyini göstərən kənarların siyahısı, həmçinin sətir və sütunların təpələrin adları və xana dəyərləri olduğu cədvəl təsviri şəklində təqdim etmək daha rahatdır. bu təpələrin bağlı olub-olmadığını göstərin.

Şəkil 7-də göstərilən qrafikləri, məsələn, aşağıdakı üsullarla təsvir etmək olar. Simvolik qeyd: a(1,2) b(l,4) c(2,4) d(3,5) e(4,5) ,(3,4)

Cədvəl girişi:

Şəkil 7. Cədvəl və simvolik qeyd şəklində eyni təsvirlərə malik olan qrafiklər

Verilənlərin ağac şəklində təqdim edilməsi

Qrafikin xüsusi növü ağacdır. Modelin bu formasından modelləşdirilmiş obyektin elementləri bir növ tabeçilik və tabeçilik vəziyyətində olduqda, iyerarxiya əlaqəsi olduqda istifadə olunur.

Müəssisənin (məktəb, teatr kollektivi və s.) idarəetmə modelini ağac şəklində təqdim etmək çox rahatdır.

Siz “ailə ağacı” anlayışını yaxşı bilirsiniz və ailə münasibətlərinizi bu formada təsvir edə bilərsiniz.

Diskdəki faylların kataloqu, eləcə də kitabxana kataloqu ağac şəklində olan informasiya modellərinə misaldır. Ağac, yuva, tabeçilik, miras və s. kimi obyektlər arasındakı əlaqələri göstərmək üçün hazırlanmış bir qrafikdir.

Aşağıdakı kimi qurulur

Əvvəlcə başqa heç bir təpədən asılı olmayan “əsas” təpəni çəkirik. Bu təpə ağacın kökü adlanır və yeganə 1-ci səviyyəli təpədir. Sonra 2-ci səviyyənin təpələrini əlavə edirik. Onların hər hansı bir sayı ola bilər və hamısı mütləq kökə bağlıdır - 1-ci səviyyənin yuxarı hissəsi, lakin bir-birinə bağlı deyil. Növbəti addımda 3-cü səviyyənin təpələrini əlavə edəcəyik. Onların hər biri 2-ci səviyyənin tam olaraq bir təpəsinə birləşdiriləcək (başqa zirvələrə deyil). 2-ci səviyyənin istənilən təpəsi 3-cü səviyyənin istənilən sayda təpəsinə qoşula bilər (heç biri daxil olmaqla). Növbəti addım 4-cü səviyyənin təpələrini əlavə etməkdir, onların hər biri 3-cü səviyyənin tam olaraq bir təpəsinə birləşdiriləcək (və başqa heç nə ilə əlaqəli deyil). Və s. Hər addımda biz növbəti səviyyənin təpələrini əlavə edirik, onların hər biri əvvəlki səviyyənin tam olaraq bir təpəsi ilə birləşdiriləcək və başqa heç bir əlaqəsi olmayacaqdır. Yaranan qrafik "yuxarıdan aşağıya doğru böyüyən" budaqlanan kollara bənzəyir: yuxarı səviyyələrdə daha aşağı nömrələr var, aşağı olanlar daha yüksəkdir. Ümumiyyətlə, ağac istiqamətsiz bir qrafik ola bilər, lakin daha tez-tez ağac yuxarı təpələrdən aşağıya doğru yönəldilmiş qövslərlə istiqamətləndirilir. Üst təpəyə onunla əlaqəli alt təpələrin əcdadı, aşağı təpələrə isə müvafiq yuxarı təpənin nəsli deyilir. İstənilən ağacda əcdadı olmayan tək bir təpə var - kök - və nəsli olmayan istənilən sayda təpələr - yarpaqlar ola bilər. Bütün digər təpələrin tam olaraq bir əcdadı və istənilən sayda nəsli var. Əlaqələrin istiqamətini nəzərə almırsınızsa, onda hər hansı bir təpədən bir ağacda hər hansı digər təpəyə və bir tək yol boyunca xətləri izləyə bilərsiniz. Sistemləri aşağı təpələrin müəyyən mənada yuxarılara "tabe" olduğu bir ağac şəklində təsvir etmək rahatdır. Üst zirvə patronu, aşağı olanlar - tabeliyində olanları təmsil edə bilər; yuxarı - sistem, aşağı - onun komponentləri; yuxarıdakılar obyektlər toplusudur, aşağılar isə ona daxil olan alt çoxluqlardır; yuxarı təpə əcdad, aşağı təpələr nəsildir və s. Ağacın qurulması (ierarxik qrafik) halında rəsmiləşdirmə sözügedən obyektin əsas (əsas, mərkəzi) elementini (sıfır səviyyəli təpə) müəyyən etməyə gəlir. , tez-tez kök adlanır), əsasdan birbaşa tabe olan elementlər (1-ci səviyyənin yuxarısı). Sonra 1-ci səviyyənin təpələrinə (2-ci səviyyənin təpələrinə) birbaşa “tabe” olan təpələr müəyyən edilir və s. Qurulmuş əlaqələr ağacı istənilən istiqamətdə təsvir edilə bilər - bu, model tərtibatçısının estetik zövqü məsələsidir. Elmi və təhsil fəaliyyəti Ağaclar çox vaxt tədqiq olunan obyektlərin təsnifatını təmsil etmək üçün istifadə olunur.

Təsnifat obyektlərin ümumi xüsusiyyətlərindən asılı olaraq siniflərə bölünməsi, müəyyən bir bilik sahəsinin vahid sistemində obyektlərin sinifləri arasında təbii əlaqələrin sabitləşdirilməsidir.

Təsnifat (latınca classis - kateqoriya + facere - etmək) - hər hansı bilik sahəsində obyektlərin ümumi xüsusiyyətlərini və bir-birləri ilə təbii əlaqələri nəzərə almaq əsasında tərtib edilmiş tabe anlayışlar (cisimlərin, hadisələrin sinifləri) sistemidir. onlar.

Təsnifat müxtəlif obyektlər arasında naviqasiya etməyə imkan verir və onlar haqqında bilik mənbəyidir. Təsnifat əsasının seçimi çox vacibdir - yəni obyektlərin hansı əsasda siniflərə bölündüyü xarakteristikası. Seçim müxtəlif səbəblər müxtəlif təsnifatlara gətirib çıxarır.

8-ci Şəkildə siz Böyük Qriqorinin təklif etdiyi təsnifatı görürsünüz, bu təsnifat insanın dünyada mövcud olan hər cür şeylə ortaq bir cəhətə malik olduğunu göstərmək məqsədi daşıyırdı və buna görə də o, haqlı olaraq “miniatürdəki kainat” adlandırılır. Nəzərə alın ki, buradakı obyektlər həmişə iki sinfə bölünür. Bu təsnifat dixotom adlanır.

Şəkil 8. Böyük Qriqori tərəfindən "nədir"in təsnifatı

Şəkil 9-da təqdim olunan printerlərin təsnifatı müxtəlif bölmə əsaslarından istifadə etməklə qurulur

Şəkil.9 Printerlərin təsnifatı

Tarixi təsnifatın mühüm növü ailə ağaclarının və ya nəsil ağaclarının tikintisidir. Çox girirlər fərqli növlər: yalnız birbaşa nəsilləri göstərən (şək. 10); o cümlədən arvadlar (ərlər) və onların qohumları və s.

Şəkil 10 Vladimir və Moskvanın böyük və əlavə knyazlarının ailə ağacı, XIII-XIV əsrlər (fraqment)

Həyatın məlum tarixləri mötərizədə verilmişdir; xaç ölüm ilini göstərir; Moskva taxtını tutan knyazların adları ikiqat konturda verilmişdir. Verilənlər bazalarında məlumatların təmsil olunması üçün yuxarıda müzakirə edilən relyativ (cədvəl), şəbəkə (qrafik) və iyerarxik (ağac) modellər əsasdır və proqram sistemləri verilənlər bazalarını yaratmağa, yeniləməyə, saxlamağa və onlara istifadəçi sorğularına xidmət etməyə imkan verən , müvafiq olaraq relational, şəbəkə, iyerarxik verilənlər bazası idarəetmə sistemləri (DBMS) adlanır. Mürəkkəb obyektləri təsvir edərkən adətən müxtəlif məlumat modellərinin kombinasiyasından istifadə olunur.

Mətn məlumatının rəsmiləşdirilməsi:

Emal prosesini asanlaşdırır və sürətləndirir;

Gəlin əldə edək kəmiyyət təxminləri;

Mətnin birmənalı başa düşülməsini təmin edir;

Mətndə olan məlumatın daha yaxşı qavranılmasına kömək edir;

Müqayisə etməyə kömək edir formal meyarlar mətndə təsvir olunan vəziyyəti real olanla və düzgün qərar qəbul edin.

Siz həm mətnin dizaynını, həm də məzmununu rəsmiləşdirə bilərsiniz.

Dizaynın rəsmiləşdirilməsi əvvəlcədən müəyyən edilmiş və tez-tez qanunla təsdiq edilmiş standart formanın formalarının, formalarının, şablonlarının istifadəsinə aiddir.

Sənəd şablonu ofis işi sahəsində tapılan standart sənəd formasıdır.

Sənədin təfərrüatları sənəddə əks etdirilməli olan məcburi məlumatlardır.

Mətnin məzmununun rəsmiləşdirilməsində məqsəd onun birmənalı başa düşülməsidir. Bu, hüquqi praktikada, elmi və idarəetmə fəaliyyətində, məsələn, təriflər tərtib edərkən, qanunlar, müqavilələr, sərəncamlar, qaydalar və s.

Cədvəllər təhlil və emal üçün əlverişlidir və məlumatın vizual formasıdır. İki və ya daha çox obyekti xarakterizə edən bir xassəni əks etdirən cədvəllər obyekt-obyekt cədvəlləri adlanır. Obyektin bir neçə xassələrini əks etdirən və bütün obyektlər bir çoxluğa aid olan cədvəllər “obyekt-xassəli” cədvəllər adlanır. Bir cədvəldə "obyekt-obyekt" və "obyekt-əmlak" tipli bir neçə cədvəlin birləşdirilməsi daha mürəkkəb tipli cədvəllər qurmağa imkan verir, məsələn, "obyekt-xassələr-obyektlər". Cədvəl aşağıdakılarla xarakterizə olunur:

Ad (və bir neçə cədvəl varsa, nömrə də),

Sütunların sayı və onların adları (sütun başlıqları),

Sətirlərin sayı və onların adları (sətir başlıqları),

Satır və sütunların kəsişməsində yerləşən xanaların məzmunu.

Çoxsəviyyəli sətir və sütun başlıqları vəziyyətində sütun başlığı səviyyələri səviyyələr, sıra başlığı səviyyələri isə addımlar adlanır.

Cədvəlin əsas elementləri bunlardır:

Qeydlər məlumatları ehtiva edə bilən cədvəl sətirləridir fərqli növlər, lakin çox vaxt bir obyektlə bağlıdır;

Sahələr, bir qayda olaraq, eyni tipli məlumatları ehtiva edən cədvəl sütunlarıdır;

Təfərrüatlar sətir və sütunların kəsişməsində cədvəl xanalarında yerləşən xüsusi dəyərlərdir.

Cədvəl formasına endirilmə mərhələləri:

1. məlumatların təhlili və haqqında olan obyektlərin müəyyən edilməsi haqqında danışırıq;

2. obyektlərin xassələrinin və/yaxud onlar arasındakı münasibətlərin işıqlandırılması;

3. obyektlərin müəyyən alt çoxluqlara birləşdirilə biləcəyinin müəyyən edilməsi və bundan asılı olaraq başlıqlarda səviyyələrin və pillələrin sayının müəyyən edilməsi;

4. sütunların ümumi sayının və onların yerləşdirilməsi qaydasının müəyyən edilməsi;

5. sütunların adlarının və orada yerləşəcək verilənlərin növünün müəyyən edilməsi;

6. cərgələrin yerləşdirilməsi qaydasının seçilməsi və cədvəlin hər bir sırasının adının müəyyən edilməsi;

7. verilənlərin təfərrüatlarının cədvəlin xanalarına daxil edilməsi (sətir-sətir və ya sütun sütun).

Qrafik bir-birinə xətlərlə bağlanmış nöqtələrin məcmusudur. Bu nöqtələrə qrafikin təpələri deyilir. Təpələri birləşdirən xətlər, əgər istiqamət bir təpədən digərinə olarsa, qövslər və ya istiqamət ikitərəfli olarsa, kənarlar adlanır. Təpələr və ya kənarlar (qövslər) bəzi əlavə məlumatlarla - təpənin və ya kənarın (qövs) çəkisi ilə xarakterizə olunursa, qrafik çəkilmiş adlanır. Qrafik onun təpələrinin çoxluğu, kənarlar çoxluğu (qövslər) verildikdə və hansı təpələrin hansı kənarlarla birləşdirildiyi göstərildikdə unikal şəkildə müəyyən edilir.

Qrafikin qurulması zamanı rəsmiləşdirmə aşağıdakı addımları əhatə edir:

Obyektin bütün elementlərinin identifikasiyası;

Elementlərin xüsusiyyətlərinin müəyyən edilməsi (adlar, nömrələr, çəkilər və s.);

Elementlər arasında əlaqələrin mövcudluğunun və növünün (birtərəfli və ya ikitərəfli) qurulması;

Bağlantı xüsusiyyətlərinin təyini - kənarların və qövslərin çəkiləri;

Təpələrin və kənarların təsvirinin formasının seçilməsi, zəruri hallarda simvolların daxil edilməsi;

Seçilmiş elementlərin və əlaqələrin qrafik formada təqdim edilməsi.

Kompüter modelləşdirməsi üçün qrafikin simvolik və/və ya cədvəlli spesifikasiyası daha əlverişlidir. Qrafikin simvolik vəzifəsi onun birləşdirdiyi təpələri göstərən bütün kənarlarının siyahısı və ya onlardan çıxan kənarları göstərən bütün təpələrin siyahısıdır.

Ağac elementləri iyerarxiya münasibətində (tabelik və tabeçilik) olan obyektin modelləşdirilməsi zamanı istifadə olunan qrafikin xüsusi növüdür. Ağacın kökü modelləşdirilmiş obyektin əsas (mərkəzi, əsas, ümumi) elementinə uyğun gələn təpədir. Ağac yarpaqları qrafikin "qul" təpələri olmayan təpələridir. Ağacın qurulması zamanı rəsmiləşdirmə sözügedən obyektin əsas elementinin (sıfır səviyyəsinin yuxarı hissəsi - ağacın kökü), əsas elementə birbaşa tabe olan elementlərin (1-ci səviyyənin yuxarı hissəsi), elementlərin müəyyənləşdirilməsinə gəlir. bilavasitə 1-ci səviyyənin zirvələrinə (2-ci səviyyənin zirvələrinə) və s. obyektlərin ümumi xarakteristikası və onlar arasındakı təbii əlaqələr. Ən çox iyerarxik qrafik (ağac) və ya cədvəl şəklində təqdim olunur. Verilənlərin verilənlər bazasında təmsil olunması üçün əsas modellər relational (cədvəl), şəbəkə (qrafik) və iyerarxik (ağac) modelləridir. Verilənlər bazalarını yaratmağa, yeniləməyə, saxlamağa və onlar üçün istifadəçi sorğularına xidmət etməyə imkan verən proqram sistemləri müvafiq olaraq relyativ, şəbəkə, iyerarxik verilənlər bazası idarəetmə sistemi (DBMS) adlanır. Mövcud avtomatlaşdırılmış verilənlər bazalarının əksəriyyəti əlaqəli tipli verilənlər bazalarıdır.

Və müəyyən bilik tələb edən əziyyətli bir proses. Növbəti paraqraflarda siz onunla daha ətraflı tanış olacaqsınız. Rəsmiləşdirmə mərhələsinin nəticəsi informasiya modeli olacaqdır. Amma modelləşdirmə prosesinin başa çatmasından danışmazdan əvvəl qurulan modelin ardıcıllığı yoxlanılmalı və onun modelləşdirmənin obyektinə və məqsədinə nə dərəcədə adekvat olduğu təhlil edilməlidir. Misal. Oxuyun...

Eksenel şüa diyaframı. İfadə (10) təxminidir, yalnız kiçik diametrlər üçün istifadə edilə bilər. Beləliklə, (7) və (10) ifadələrindən belə çıxır ki, dalğa, eninə və uzununa aberasiya müxtəlif formalarşüaların homosentrikliyinin pozulmasının bir fenomeninin təsviri. Təsvirin keyfiyyətini qiymətləndirərkən optik sistemin aberrasiya xüsusiyyətlərinin ilkin modeli kimi dalğa dalğa forması götürülür...

İstənilən verilənlər bazası sisteminə nisbətən asanlıqla uyğunlaşdırıla bilən yerli modellər. Ən çox yayılmış məlumat modelləşdirmə vasitəsi varlıq münasibətləri diaqramlarıdır (ERD). Onların köməyi ilə predmet sahəsi üçün vacib olan obyektlər (obyektlər), onların xassələri (atributları) və bir-biri ilə əlaqələri (əlaqələri) müəyyən edilir. ERD-lər birbaşa əlaqəli verilənlər bazalarının dizaynı üçün istifadə olunur...

Qrafiklər

Qrafiklər XVIII əsrdə məşhur riyaziyyatçı Leonhard Euler Köniqsberq körpüləri ilə bağlı indi klassik problemi həll etməyə çalışdığı zaman yaranmışdır. Həmin vaxt Köniqsberq şəhərində Şəkildə göstərildiyi kimi Preqol çayının sahillərinə və bir-birinə yeddi körpü ilə bağlanan iki ada var idi. 7.1. Tapşırıq aşağıdakılardan ibarətdir: şəhər ətrafında elə bir gəzinti həyata keçirmək ki, hər körpünün üstündən düz bir dəfə keçib, gəzinti başladığı yerə qayıdın. Bu problemi həll edən Eyler Koenigsberg-i qrafik kimi təsvir edərək onun təpələrini şəhərin hissələri ilə, kənarlarını isə bu hissələri birləşdirən körpülərlə müəyyən etdi. § 7.1-də göstərəcəyimiz kimi, Eyler şəhər ətrafında istənilən marşrutun mövcud olmadığını sübut edə bildi.

Şəkil 7.1. Köhnə Koenigsberg sxemi

Bu fəsildə biz qrafik nəzəriyyəsində istifadə olunan standart terminologiyanı təqdim edirik və bir neçəsini araşdırırıq konkret vəzifələr qrafiklərdən istifadə etməklə həll edilir. Xüsusilə, ağaclar adlanan qrafiklər sinfi ilə tanış olacağıq. Ağaclar iyerarxik sistemdə təşkil edilmiş məlumatları təmsil edən təbii modeldir. Ayrı-ayrı elementləri təcrid etmək üçün ağac axtarışı və ağacdakı məlumatların çeşidlənməsi kompüter elmində vacib səylərdir. Bu fəslin əlavəsində biz ağaclarda təşkil edilmiş məlumatların çeşidlənməsi və axtarışına baxacağıq.

Qrafiklər və terminologiya

Şəkildə. 7.1 Köniqsberqin yeddi körpüsünü belə göstərir. on səkkizinci əsrdə necə yerləşdiklərini. Eylerin müraciət etdiyi problem belədir: körpülərin hər birinin üstündən düz bir dəfə keçən və şəhərin eyni yerindən başlayıb, eyni yerdə bitən piyada marşrutu tapmaq mümkündürmü?

Tapşırıq modelidir qrafik,çoxlarından ibarətdir zirvələri və çoxlu qabırğalar təpələri birləşdirən. A, B, C təpələri və D çayın və adaların sahillərini və qabırğaları simvollaşdırır a,c, c,d,f Və g yeddi körpünü təmsil edir (bax. Şəkil 7.2). Tələb olunan marşrut (əgər varsa) qrafikin kənarlarını elə keçməyə uyğundur ki, onların hər biri yalnız bir dəfə keçsin. Qabırğanın keçidi açıq şəkildə çayın körpü ilə keçməsinə uyğun gəlir.

Şəkil 7.2. Köniqsberq körpüsü probleminin modeli

Marşrutun olduğu, eyni təpədən başlayan və bitən, qrafikin bütün kənarları boyunca düz bir dəfə keçən marşrutun olduğu qrafikə deyilir. Seiler qrafiki.İstədiyiniz marşrutun, marşrutun özü kimi keçdiyi təpələrin ardıcıllığı (bəlkə də təkrarlarla) adlanır. eulerian dövrü. Eyler qeyd etdi ki, qrafikdə Eyler dövrü varsa, onda hər hansı bir təpəyə gedən hər kənar üçün bu təpədən 1 çıxan başqa kənar olmalıdır və bu sadə müşahidədən o, aşağıdakı nəticəyə gəldi: əgər bir qrafikdə Eyler dövrü varsa. qrafik verilmişdirsə, onda hər bir təpənin cüt sayda kənarları olmalıdır.

Bundan əlavə, Eyler bunun əksini sübut edə bildi, belə ki, hər hansı bir cüt təpənin hansısa kənar ardıcıllığı ilə bağlandığı qrafik yalnız və yalnız bütün təpələrinin cüt dərəcəyə malik olduğu halda Eyleriandır. Dərəcə təpələr v δ(v) ədədi adlanır qabırğalar, onun Hadisə 2 .

İndi tamamilə aydındır ki, Köniqsberq körpüsü problemini modelləşdirən qrafikdə Eyler dövrü tapmaq mümkün deyil. Həqiqətən, onun bütün təpələrinin dərəcələri təkdir: δ(B) = δ(C)= δ(D) = 3 və δ(A) = 5. C yüngül əl Körpü probleminin həllində öyrəndiyimiz kimi Eyler qrafikləri bir çox praktiki problemlərin həllində istifadə olunmağa başladı və onların öyrənilməsi riyaziyyatın əhəmiyyətli bir sahəsinə çevrildi.

Sadə qrafik G = (V,) cütü kimi müəyyən edilir. E), burada V təpələrin sonlu çoxluğudur və E- məhdud kənarlar dəsti və ehtiva edə bilməz ilmələr(eyni təpədə başlayan və bitən kənarlar) və çoxlu kənarlar(birdən çox kənar eyni cüt təpələri birləşdirən çoxlu kənarlardır). Şəkildə göstərilən qrafik. 7.2. sadə deyil, çünki, məsələn, təpələr A Və IN iki kənar ilə bağlanır (məhz bu kənarlar çoxlu adlanır).

İki zirvə u Və v sadə bir qrafikdə deyilir bitişik, əgər onlar hansısa kənar ilə birləşdirilirsə e, onlar haqqında deyirlər ki, bu təsadüfi təpə u (və v ). Beləliklə, çoxlarını təsəvvür edə bilərik E kənarları bitişik təpələrin cütləri toplusu kimi, bununla da dəstdə qeyri-refleksiv, simmetrik əlaqəni təyin edir. V. Refleksiyanın olmaması sadə bir qrafikin hər iki ucu eyni təpədə olan döngələrin, yəni kənarların olmaması ilə əlaqədardır. Əlaqənin simmetriyası ondan irəli gəlir ki, kənar e, təpəni birləşdirən Və ilə v, birləşdirir və v ilə Və(başqa sözlə, kənarlar yönləndirilmir, yəni istiqaməti yoxdur). Bir cüt təpəni birləşdirən sadə qrafikdə tək kənar u Və v, kimi işarə edəcəyik və v(və ya vi).

Qrafikin kənarları ilə təyin olunan təpələr çoxluğuna münasibətin məntiqi matrisi adlanır. , bitişiklik matrisi. M bitişiklik matrisi baxımından münasibətin simmetriyası o deməkdir ki, M əsas diaqonala görə simmetrikdir. Və M matrisinin əsas diaqonalında bu əlaqənin əks olunmaması səbəbindən "L" simvolu var.

Misal 7.1. G(V, E) qrafikini çəkin təpələr dəsti ilə V = (a, b, c, d, e) və kənarlar dəsti E = (ab, ae, bc, bd, ce, de). Onun bitişiklik matrisini yazın.

Həll. Qrafik G şəkildə göstərilmişdir. 7.3.

Şəkil 7.3.

Onun bitişiklik matrisi aşağıdakı formaya malikdir:

Qrafiki bərpa etmək üçün bizə yalnız qonşuluq matrisinin əsas diaqonaldan yuxarı olan elementləri lazımdır.

Subqraf G = (V, E) qrafiki G’ = (V’, E’) qrafiki adlanır ki, burada E’ C E və V’ C V olur.

Misal 7.2Şəkildə göstərilən H, K və L qrafikləri arasında tapın. 7.4, G qrafikinin yarımqrafları.

Həll.Şəkildə göstərildiyi kimi G, H və K qrafiklərinin təpələrini işarə edək. 7.5. Bizim qeydimizdən göründüyü kimi H və K qrafikləri G-nin alt qrafikləridir. L qrafiki G-nin alt qrafası deyil, çünki onun 4 indeksli təpəsi var, G isə yoxdur.

Marşrut uzunluq k G qrafikində təpələrin belə ardıcıllığı deyilir v 0 , v 1 , …, v k , ki, hər i = 1, …, k cütü üçün v i – 1 v i qrafikin kənarını təşkil edir. Belə bir marşrutu ilə işarə edəcəyik v 0 v 1 … v k . Məsələn, 1 4 3 2 5 Nümunə 7.2-dən G qrafikində uzunluğu 4 olan marşrutdur.

G H

K L

Şəkil 7.4.

Velosiped qrafikdə təpələrin ardıcıllığını çağırmaq adətdir v 0 , v 1 , … , v k , hər bir cüt bir kənarın ucları olan və v 0 = v 1 , və qalan təpələr (və kənarlar) təkrarlanmır. Başqa sözlə desək, dövrə onun hər bir təpəsindən və kənarından yalnız bir dəfə keçən qapalı marşrutdur

1 2 1 2 3

Şəkil 7.5

Misal 7.3. Misal 7.2-dən G qrafikində dövrləri tapın.

Həll. Bu qrafikdə uzunluğu 5 olan iki fərqli dövr var:

1 3 2 5 4 1 və 1 2 5 4 3 1

Dövrün ixtiyari yuxarı hissəsindən başlayaraq, bu dövrlərdən bir istiqamətdə və ya digər istiqamətdə keçə bilərik. Bundan əlavə, qrafikin uzunluğu 4 olan üç fərqli dövrə malikdir:

1 2 5 4 1, 1 2 3 4 1 və 2 5 4 3 2,

və uzunluğu 3 olan iki döngə:

1 2 3 1 və 1 3 4 1.

Dövrləri olmayan qrafik adlanır asiklik. Hesablama zamanı yaranan ağac strukturları asiklik qrafiklərin xüsusi halıdır. Bu fəsildə daha sonra onlarla məşğul olacağıq.

Say, çağırdı ardıcıl, onun təpələrinin hər hansı bir cütü hansısa marşrutla bağlıdırsa. Hər hansı bir ümumi qrafiki hər biri bir-birinə bağlı olduğu ortaya çıxan alt qrafiklərə bölmək olar. Belə birləşdirilmiş komponentlərin minimum sayı çağırılır əlaqə nömrəsi qrafiki ilə işarələnir c(G) . Qrafik nəzəriyyəsinin kompüter şəbəkələrinə tətbiqində əlaqə məsələləri vacibdir. Qrafikin əlaqə nömrəsini təyin etmək üçün aşağıdakı alqoritmdən istifadə olunur.

Bağlantı alqoritmi.

G = (V, E) qrafiki olsun. Alqoritm dəyəri hesablamaq üçün nəzərdə tutulmuşdur c = c(G), olanlar. verilmiş qrafikin əlaqəli komponentlərinin sayı G.

V' :=V;

isəV’≠ øet

y Є seçin V’

Marşrutu y ilə birləşdirən təpələri tapın;

Buradan təpəni çıxarınV' Və

E-dən müvafiq kənarlar;

c:= c+1;

Misal 7.4.Şəkildə göstərilən qrafikdə əlaqə alqoritminin işini müşahidə edin. 7.6.

Şəkil 7.6.

Həll. Cədvələ baxın. 7.1.

Cədvəl 7.1.


İlkin dəyərlər	{1,2,3,4,5,6,7,8}
Seçim y = 1
Seçim y = 2
Seçim y = 7

Belə ki, c(G) = 3. Müvafiq birləşdirilmiş komponentlər Şəkildə göstərilmişdir. 7.7.

"Təcrid olunmuş" təpələrdən ibarət qrafik diaqramı deyilir sıfır qrafik. (Şəkil 2)

Bütün mümkün kənarların qurulmadığı qrafiklər deyilir natamam qrafiklər. (şək.3)

Bütün mümkün kənarların qurulduğu qrafiklər deyilir tam qrafiklər. (Şəkil 4)

Qrafikin kənarlarında kənarların istiqamətini göstərən oxlar varsa, belə bir qrafik adlanır. yönəldib.

Şəkildə göstərilən qrafikdə bir işdən digərinə ox işlərin ardıcıllığını bildirir.

Bitirməyə başlamaq üçün təməli bitirmədən divarların quraşdırılmasına başlaya bilməzsiniz, mərtəbələrdə su olmalıdır və s.

Təpələrin dərəcələri və kənarların sayının hesablanması.

Qrafikin təpəsindən çıxan kənarların sayı təpənin dərəcəsi adlanır. Qrafikin tək dərəcəyə malik təpəsinə tək, cüt dərəcəyə malik təpə isə cüt adlanır.

Qrafikin bütün təpələrinin dərəcələri bərabərdirsə, o zaman qrafik adlanır homojen. Beləliklə, istənilən tam qrafik homojendir.

Şəkil 5-də beş təpəsi olan bir qrafik göstərilir.

A təpəsinin dərəcəsini St.A kimi işarə edirik.

Şəkildə:
St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.

Gəlin müəyyən qrafiklərə xas olan bəzi qanunauyğunluqları formalaşdıraq.

Nümunə 1. Tam qrafikin təpələrinin dərəcələri eynidir və onların hər biri bu qrafikin təpələrinin sayından 1 azdır.

Nümunə 2. Qrafikin təpələrinin dərəcələrinin cəmi, qrafikin kənarlarının sayının iki qatına bərabər olan cüt ədəddir.

Bu nümunə yalnız tam qrafik üçün deyil, həm də istənilən qrafik üçün doğrudur.

İstənilən qrafikdə tək təpələrin sayı cütdür.

Qeyd edək ki, tam qrafikin n təpəsi varsa, onda kənarların sayı n(n-1)/2-ə bərabər olacaqdır.

Tamamlanmayan bir qrafik, çatışmayan kənarları əlavə etməklə eyni təpələrlə tamamlana bilər. Məsələn, Şəkil 3-də beş təpəsi olan natamam qrafik göstərilir. Şəkil 4-də qrafiki tam qrafikə çevirən kənarlar fərqli rəngdə təsvir edilmişdir.

Eyler qrafikləri.

Qələmi kağızdan qaldırmadan çəkmək mümkün olan qrafik adlanır eulerian. (Şəkil 6)

Bu qrafiklər alimin adını daşıyır Leonhard Euler.

Nümunə 3.(nəzərdən keçirdiyimiz teoremdən irəli gəlir).
Tək sayda tək təpələri olan qrafik çəkmək mümkün deyil.

Nümunə 4.Əgər qrafikin bütün təpələri bərabərdirsə, onda siz bu qrafiki qələminizi kağızdan qaldırmadan (“bir vuruşla”) çəkə bilərsiniz, hər kənarı yalnız bir dəfə hərəkət etdirə bilərsiniz. Hərəkət istənilən təpədən başlaya və eyni təpədə bitə bilər.

Nümunə 5. Qələmi kağızdan qaldırmadan yalnız iki tək təpəsi olan qrafiki çəkmək olar və hərəkət bu tək təpələrdən birində başlayıb, ikincisində bitməlidir.

Nümunə 6.İkidən çox tək təpəsi olan qrafik çəkilə bilməz " bir vuruşla».

Kağızdan qələmi qaldırmadan çəkmək mümkün olan fiqur (qrafik) adlanır unicursal.

Qrafik adlanır ardıcıl, əgər onun təpələrindən hər hansı ikisi bir yolla, yəni hər biri əvvəlkinin sonundan başlayan kənarların ardıcıllığı ilə birləşdirilə bilərsə.

Şəkil 7 açıq şəkildə əlaqəsiz bir qrafiki göstərir.

Qrafik adlanır uyğunsuz, bu şərt yerinə yetirilmədikdə.

Məsələn, şəkildəki D və E təpələri arasında bir kənar çəksəniz, qrafik birləşdiriləcəkdir.( Şəkil 8)

Qrafik nəzəriyyəsində belə bir kənar (çıxarıldıqdan sonra qrafik bağlı vəziyyətdən ayrılmış vəziyyətə çevrilir) adlanır. körpü.

Körpülərin nümunələri Şəkil 7 kənarları DE, A3, VZh və s. xidmət edə bilər, hər biri qrafikin "təcrid olunmuş" hissələrinin təpələrini birləşdirəcəkdir. ( Şəkil 8)

Əlaqəsi kəsilmiş qrafik bir neçə " ədəd" Bu “parçalar” qrafikin əlaqəli komponentləri adlanır. Hər bir əlaqəli komponent, əlbəttə ki, əlaqəli bir qrafikdir. Nəzərə alın ki, əlaqəli qrafikdə bir əlaqəli komponent var.

Qrafik yalnız və yalnız bir-birinə bağlı olduqda və ən çox iki tək təpə nöqtəsinə malik olduqda Euler qrafikidir.

Ağaclar.

ağac Dövrləri olmayan hər hansı əlaqəli qrafik deyilir.

Velosiped başlanğıcla sonun üst-üstə düşdüyü yoldur.

Dövrün bütün təpələri fərqlidirsə, belə bir dövrə deyilir ibtidai(və ya sadə) dövrü.

Əgər dövrə qrafikin bütün kənarlarını bir dəfə əhatə edirsə, belə dövrə deyilir Eyler xətti (Şəkil 9a).

Açıq sütunda Şəkil 9b iki dövrə: 1-2-3-4-1 və 5-6-7-5.

By bir təpədən digərinə olan qrafikdə bu təpələr arasında marşrutun çəkilə biləcəyi kənarların ardıcıllığı var.

Bu halda, marşrutun heç bir kənarı bir dəfədən çox görünməməlidir. Marşrutun çəkildiyi zirvə adlanır səyahətin başlanğıcı, marşrutun sonundakı zirvə - yolun sonu.

asma üstü tam olaraq bir kənarın çıxdığı təpədir ( Şəkil 10).
(asma zirvələr dövrələnir).

Hər bir cüt ağac təpəsi üçün onları birləşdirən unikal bir yol var.

Bu xüsusiyyət, nəsil ağacında, məsələn, nəsil ağacı şəklində təmsil olunan hər hansı bir şəxsin kişi nəslində bütün əcdadları taparkən istifadə olunur. ağac"və qrafik nəzəriyyəsi mənasında.

Ağacın hər kənarı bir körpüdür.

Həqiqətən, ağacın hər hansı bir kənarını götürdükdən sonra " parçalanır"iki ağac üzərində.

İstənilən iki təpənin bir sadə yolla bağlandığı qrafikdir ağac.

(asma üstü haqqında). Hər ağacın asılmış zirvəsi var.

. Bir ağacda təpələrin sayı kənarların sayından bir çoxdur.

İzomorfizm. Planar qrafiklər və Eyler teoremi.

İki qrafik adlanır izomorf, əgər onların bərabər sayda təpələri varsa və hər bir qrafikin təpələri 1-dən n-ə qədər nömrələnə bilərsə, beləliklə, birinci qrafikin təpələri kənar ilə birləşdirilir, o halda ki, ikinci qrafikin müvafiq təpələri bir-birinə bağlansın. bir kənar.

Şəkil 11-də göstərilən qrafiklərin izomorf olduğunu sübut edək.

Birinci və ikinci qrafiklərin təpələrini 1-dən 4-ə qədər nömrələyək ( Şəkil 12).

Birinci qrafik 1 və 2, 2 və 3, 3 və 4, 1 və 4, 1 və 3, 2 və 4 təpələrini birləşdirir; Qeyd edək ki, ikinci qrafikdə 1 və 2, 2 və 3, 3 və 4, 1 və 4, 1 və 3, 2 və 4 təpələri də bağlıdır, ona görə də bu qrafiklər izomorfdur.

İki qrafikin izomorf olub-olmadığını öyrənmək üçün onların olduğundan əmin olmalısınız:

eyni sayda təpələr
əgər bir qrafikin təpələri kənar ilə birləşdirilirsə, digər qrafikin müvafiq təpələri də kənar ilə birləşdirilir.

Kənarları təpələrindən başqa heç bir yerdə kəsişməyəcək şəkildə çəkilə bilən qrafik adlanır. düz və ya planar.

Eyler. Düzgün çəkilmiş müstəvi qrafik üçün o bərabərliyə malikdir: V-E+F=2, burada V təpələrin sayı, E kənarların sayı, F parçaların sayıdır (V -E+ bərabərliyi F=2 adətən Eyler düsturu adlanır).

Hər təpənin hər bir digər təpənin kənarına bağlandığı qrafikə deyilir tam.

Pontryagin - Kuratovski. Qrafik o zaman düzdür ki, onun tərkibində (topoloji mənada) altı təpəsi “ev-quyu” tipli qrafik və beş təpəsi olan tam qrafik yoxdur.

(Əsasən evlər və quyular haqqında qədim problemlərdə istifadə olunur, mahiyyəti suala aydınlıq gətirmək üçün qaynar - sözügedən qrafikin düz olub-olmaması, Şəkil 13)

İstiqamətləndirilmiş qrafiklər.

Əvvəllər müzakirə olunan qrafik tiplərindən istifadə etməklə həll edilə bilməyən praktiki problemlərin əhəmiyyətli sinifləri var.

Məsələn, bir şəhərin yollarının və meydanlarının xəritəsi düz bir qrafikdən istifadə edərək təsvir edilmişdir. Bəs bu sxemdən istifadə edərək şəhəri avtomobillə gəzmək lazımdırsa və bəzi (və ya bütün) küçələrdə nəqliyyatın hərəkəti birtərəfli olarsa nə etməli?

Sonra, məsələn, birbaşa kənarlarda - sözügedən şəhər diaqramının (qrafik) küçələrində yerləşən oxlar bu vəziyyəti idarə etməyə kömək edə bilər.

Kənarlarında oxlar olan qrafik adlanır yönümlü.

Məhsuldarlıq dərəcəsi istiqamətləndirilmiş qrafikin təpəsi bu təpənin başlanğıc olduğu kənarların sayıdır (kənarların sayı, " çıxır"yuxarıdan).

Giriş dərəcəsi istiqamətləndirilmiş qrafikin təpəsi bu təpənin sonu olduğu kənarların sayıdır (kənarların sayı, " gələn"yuxarıya).

Bəli, açıq Şəkil 15 istiqamətlənmiş ABCD qrafikini göstərir. Onun bəzi təpələrinin giriş və çıxış dərəcələri aşağıdakı kimidir:
St.in.A=2, St.out.A=1 St.in.B=2, St.out.B=0 St.in.D=1, St.out.D=3.

A1 təpəsindən An təpəsinə qədər istiqamətlənmiş qrafikdə yol A1A2, A2A3, ..., Аn-1Аn istiqamətlənmiş kənarların ardıcıllığıdır, burada hər bir əvvəlki kənarın sonu növbəti kənarın başlanğıcı ilə üst-üstə düşür və hər kənar bu ardıcıllıq yalnız bir dəfə.

Aktiv rəqəm.15 istiqamətləndirilmiş qrafikdə yolların nümunələri göstərilir. Üstəlik, ilk iki yol sadədir - təpələrin heç biri bir dəfədən çox deyil. Üçüncü yol sadə deyil, yəni. G təpəsindən keçin. keçdi"iki dəfə.

İstiqamətləndirilmiş dövr istiqamətlənmiş qrafikdə qapalı yol adlanır.

Aktiv Şəkil 15İstiqamətləndirilmiş dövrlərin nümunələri son iki qrafikdə verilmişdir. Dövr, qrafikdəki hər hansı digər yol kimi, bu yoldakı kənarların sayı ilə müəyyən edilən uzunluğa malikdir.

Beləliklə, Şəkil 16-da A-dan D-yə qədər olan yollar müxtəlif ola bilər və müxtəlif uzunluqlara malik ola bilər.
Birinci yolun uzunluğu 2, ikincinin uzunluğu 3,
üçüncüsü isə 4-dür.

İki təpə arasındakı "ən qısa yolun" uzunluğu onların arasındakı məsafə adlanır. Beləliklə, Şəkil 16-nın qrafikində A və D təpələri arasındakı məsafə 2-dir; belə yazılmışdır: S(BP)=2.

İstiqamətləndirilmiş qrafikdə bir təpədən digərinə "keçmək" mümkün deyilsə, onlar arasındakı məsafə sonsuz adlanır (sonsuzluq simvolu ilə göstərilir). Beləliklə, Şəkil 17-də təqdim olunan qrafikin B və D təpələri arasındakı məsafə sonsuzdur: S(DB) = ∞

İqtisadiyyatda istiqamətləndirilmiş qrafiklər şəbəkə planlaşdırılmasında, riyaziyyatda - oyun nəzəriyyəsində, çoxluq nəzəriyyəsində fəal şəkildə istifadə olunur; bir çox problemləri, xüsusən də kombinator problemləri həll edərkən.

Yəqin ki, kompüter şəbəkələri haqqında bir az məlumatınız var. Ola bilsin ki, məktəbinizin informatika sinifindəki kompüterlər yerli şəbəkəyə qoşulub və ya siz internetdə işləmisiniz və ya e-poçt xidmətlərindən istifadə edirsiniz. Aydındır ki, şəbəkə yalnız kompüterlər bir-biri ilə məlumat ötürmə kanalları ilə bir-birinə bağlı olduqda formalaşır. Şəbəkə abunəçilərinin (kompüterlər və ya ona qoşulmuş digər avtomatik məlumat emalı sistemləri) yerləşdirilməsi və onların bir-birinə qoşulma üsulları şəbəkə konfiqurasiyası adlanır. Siz müxtəlif növ kompüter şəbəkəsi konfiqurasiyalarını nümayiş etdirə bilərsiniz, məsələn, qrafiklər kimi məlumat modellərindən istifadə etməklə. Qrafik xətlərlə birləşdirilən nöqtələrin toplusudur. Nöqtələrə qrafikin təpələri deyilir. Onlar nöqtələr, dairələr, düzbucaqlılar və s. ilə göstərilə bilər. Təpələri birləşdirən xətlər qövslər (istiqamət bir təpədən digərinə verilirsə) və ya kənarlar (istiqamət ikitərəflidirsə, yəni istiqamətlər) adlanır. bərabərdir). Bir kənar (qövs) ilə birləşdirilən iki təpəyə bitişik deyilir. Qrafikin təpələri və kənarları müəyyən ədədi qiymətlərlə xarakterizə edilə bilər. Məsələn, kənarın uzunluğu və ya onun boyunca “keçmənin qiyməti” məlum ola bilər. Belə xüsusiyyətlərə çəki, qrafikə isə çəkili deyilir.

Misal

Şəkil 3-də qrafiklər şəklində təqdim olunan LAN strukturlarının məlumat modelləri olan müxtəlif növ yerli şəbəkə (LAN) konfiqurasiyaları göstərilir:

* avtobus konfiqurasiyası, ayrı-ayrı abonentlər müəyyən fasilələrlə (K) açıq kanala qoşulduqda, mənbə abunəçidən gələn məlumatlar hər iki istiqamətdə kanal boyunca paylanır;

* zəng konfiqurasiyası, hər bir abunəçi birbaşa iki qonşu abunəçiyə qoşulduqda və məlumat qapalı halqa vasitəsilə, çox vaxt bir istiqamətdə ötürüldükdə;

* ulduz formalı konfiqurasiya, mərkəzində mərkəzi keçid (CC) var, o, ardıcıl olaraq abunəçiləri sorğulayır və onlara məlumat mübadiləsi hüququ verir;

* bir neçə sadə rabitə kanalını bir magistralla birləşdirərək ağaca bənzər konfiqurasiya formalaşır;

* tam şəbəkəli konfiqurasiya abunəçilər arasında ən sürətli rabitə marşrutunun seçilməsini təmin edir və idarəetmənin olduqca mürəkkəb olduğu yerlərdə rahatdır.

şək.3

Qrafik ən aydın şəkildə rəsmlə müəyyən edilir. Bununla belə, rəsmin bütün detalları eyni dərəcədə vacib deyil. Xüsusilə, kənarların həndəsi xüsusiyyətləri (uzunluq, əyrilik və s.), təpələrin forması (nöqtə, dairə, kvadrat, oval və s.) və təpələrin müstəvidə nisbi mövqeyi əhəmiyyətsizdir. Beləliklə, Şəkil 4 eyni qrafikin iki şəklini göstərir. Bütün təpələr və kənarlar tez-tez təpə və ya xətt üzərində müşayiətedici etiket kimi müəyyən edilir, lakin simvollar daxil etməklə onlar təpənin forması və ya rəngi, xəttin qalınlığı, növü və ya rəngi ilə müəyyən edilə bilər.

düyü. 4

Modelləşdirmə obyektinin elementləri arasında mövcud olan əlaqələri əyani şəkildə göstərmək üçün qrafik şəklində olan informasiya modelindən istifadə oluna bilər. Beləliklə, qrafik obyektin strukturunu modelləşdirmək üçün ən əlverişli formadır, baxmayaraq ki, bu formada obyektin həm görünüşünü, həm də davranışını modelləşdirmək mümkündür.

Misal

Şəkil 5-də hər biri C4H10 düsturu olan, yəni 4 karbon atomundan və 10 hidrogen atomundan ibarət olan butan və izobutan molekullarının modelləri göstərilir. Eyni düstura malik olan butan və izobutan fərqli kimyəvi xüsusiyyətlərə malikdir, çünki atomların birləşmə yolu (molekulların quruluşu) fərqlidir. Bir molekulda atomların müxtəlif birləşmə üsulları ilə düzülüşü qrafiklə yaxşı göstərilə bilər.

Şəkil 5

Misal

Həndəsə kursundan “Dördbucaqlılar” mövzusunun konsepsiya qrafikinə nəzər salın (şək. 6). Yaxşı bir "fırıldaqçı vərəq" deyilmi?

Şəkil 6.

Misal

Maşınla işləmə üçün qrafikləri simvolik olaraq bu kənarın hansı təpələri birləşdirdiyini göstərən kənarların siyahısı şəklində təqdim etmək daha rahatdır, həmçinin sətirlərin və sütunların təpələrin adları və xanaların qiymətləri olduğu cədvəl təsviri. bu təpələrin bağlı olub-olmadığını göstərin.

Misal

Şəkil 7-də göstərilən qrafikləri, məsələn, aşağıdakı üsullarla təsvir etmək olar. Simvolik qeyd: a(1,2) b(l,4) c(2,4) d(3,5) e(4,5) ,(3,4)

Cədvəl girişi:

Şəkil 7.

Verilənlərin ağac şəklində təqdim edilməsi

Misal

Müəssisənin (məktəb, teatr kollektivi və s.) idarəetmə modelini ağac şəklində təqdim etmək çox rahatdır.

Misal

Siz “ailə ağacı” anlayışını yaxşı bilirsiniz və ailə münasibətlərinizi bu formada təsvir edə bilərsiniz.

Misal

Aşağıdakı kimi qurulur

Əvvəlcə başqa heç bir təpədən asılı olmayan “əsas” təpəni çəkirik. Bu təpə ağacın kökü adlanır və yeganə 1-ci səviyyəli təpədir. Sonra 2-ci səviyyənin təpələrini əlavə edirik. Onların hər hansı bir sayı ola bilər və hamısı mütləq kökə bağlıdır - 1-ci səviyyənin yuxarı hissəsi, lakin bir-birinə bağlı deyil. Növbəti addımda 3-cü səviyyənin təpələrini əlavə edəcəyik. Onların hər biri 2-ci səviyyənin tam olaraq bir təpəsinə birləşdiriləcək (başqa zirvələrə deyil). 2-ci səviyyənin istənilən təpəsi 3-cü səviyyənin istənilən sayda təpəsinə (heç biri daxil olmaqla) qoşula bilər. Növbəti addım 4-cü səviyyəli təpələri əlavə etməkdir, onların hər biri tam olaraq bir 3-cü səviyyəli zirvəyə qoşulacaq (və başqa heç nə ilə əlaqəsi yoxdur). Və s. Hər addımda biz növbəti səviyyənin təpələrini əlavə edirik, onların hər biri əvvəlki səviyyənin tam olaraq bir təpəsi ilə birləşdiriləcək və başqa heç bir əlaqəsi olmayacaqdır. Yaranan qrafik "yuxarıdan aşağıya doğru böyüyən" budaqlanan kollara bənzəyir: yuxarı səviyyələrdə daha aşağı nömrələr var, aşağı olanlar daha yüksəkdir. Ümumiyyətlə, ağac istiqamətsiz bir qrafik ola bilər, lakin daha tez-tez ağac yuxarı təpələrdən aşağıya doğru yönəldilmiş qövslərlə istiqamətləndirilir. Üst təpə onun əlaqəli alt təpələrinin əcdadı, aşağı təpələrə isə müvafiq yuxarı təpənin nəsli adlanır. İstənilən ağacda əcdadı olmayan tək təpə var - kök - və nəsli olmayan istənilən sayda təpələr - yarpaqlar ola bilər. Bütün digər təpələrin tam olaraq bir əcdadı və istənilən sayda nəsli var. Əlaqələrin istiqamətini nəzərə almırsınızsa, o zaman hər hansı bir təpədən bir ağacda hər hansı digər təpəyə çatmaq üçün xətləri izləyə bilərsiniz və tək bir yol boyunca. Sistemləri aşağı təpələrin müəyyən mənada yuxarılara "tabe" olduğu bir ağac şəklində təsvir etmək rahatdır. Üst zirvə patronu, aşağı olanlar - tabeliyində olanları təmsil edə bilər; yuxarıdakılar sistemdir, aşağılar onun komponentləridir; yuxarıdakılar obyektlər toplusudur, aşağılar isə ona daxil olan alt çoxluqlardır; yuxarı təpə əcdad, aşağı təpələr nəsildir və s. Ağacın qurulması (ierarxik qrafik) halında rəsmiləşdirmə sözügedən obyektin əsas (əsas, mərkəzi) elementini (sıfır səviyyəli təpə) müəyyən etməyə gəlir. , tez-tez kök adlanır), birbaşa əsasa tabe olan elementlər (1-ci səviyyənin zirvələri). Sonra 1-ci səviyyənin təpələrinə (2-ci səviyyənin təpələri) birbaşa “tabe” olan təpələr müəyyən edilir və s. Qurulmuş əlaqələr ağacı istənilən istiqamətdə təsvir edilə bilər - bu, model tərtibatçısının estetik zövqü məsələsidir. Elmi və tədris fəaliyyətlərində ağaclar çox vaxt öyrənilən obyektlərin təsnifatını təmsil etmək üçün istifadə olunur.

Təsnifat müxtəlif obyektlər arasında naviqasiya etməyə imkan verir və onlar haqqında bilik mənbəyidir. Təsnifat əsasının seçimi çox vacibdir - yəni obyektlərin hansı əsasda siniflərə bölündüyü xarakteristikası. Müxtəlif əsasların seçilməsi müxtəlif təsnifatlara gətirib çıxarır.

Misal

Şəkil 8.

Misal

Şəkil 9-da təqdim olunan printerlərin təsnifatı müxtəlif bölmə əsaslarından istifadə etməklə qurulur

Şəkil 9

Misal

Tarixi təsnifatın mühüm növü ailə ağaclarının və ya nəsil ağaclarının tikintisidir. Onlar müxtəlif formalarda olur: yalnız birbaşa nəsilləri göstərir (şək. 10); o cümlədən arvadlar (ərlər) və onların qohumları və s.

Şəkil 10 Vladimir və Moskvanın böyük və əlavə knyazlarının ailə ağacı, XIII-XIV əsrlər (fraqment)

Həyatın məlum tarixləri mötərizədə verilmişdir; xaç ölüm ilini göstərir; Moskva taxtını tutan knyazların adları ikiqat konturda verilmişdir. Verilənlər bazalarında məlumatların təqdim edilməsi üçün yuxarıda müzakirə olunan relyativ (cədvəl), şəbəkə (qrafik) və iyerarxik (ağac) modellər əsasdır və verilənlər bazalarını yaratmağa, yeniləməyə, saxlamağa və onlar üçün istifadəçi sorğularına xidmət etməyə imkan verən proqram sistemləri relyativ adlanır. , müvafiq olaraq şəbəkə, iyerarxik verilənlər bazası idarəetmə sistemləri (DBMS). Mürəkkəb obyektləri təsvir edərkən adətən müxtəlif məlumat modellərinin kombinasiyasından istifadə olunur.