Texnologiyalari ha’m kommunikatsiyani rawajlandiriw ministirligi muxammed al-xorezmiy atindag’i tashkent informatsiyaliq texnologiyalari universiteti

TEXNOLOGIYALARI HA’M KOMMUNIKATSIYANI RAWAJLANDIRIW MINISTIRLIGI MUXAMMED AL-XOREZMIY ATINDAG’I TASHKENT INFORMATSIYALIQ TEXNOLOGIYALARI UNIVERSITETI

NO’KIS FILIALI

«Telekommunikaciya texnologiyaları » fakulteti « Telekommunikaciya texnologiyaları » tálım baǵdarı
3003-20 sırtqı 3-basqısh studentı Shukirallaev Ixlas
«Mag’luwmatlar du’zilmesi ha’m algoritm»páninen
Ózbetınshe jumısı
Qabıllaǵan: ___________ G.Aimbetova
Orınlaģan: ____________I.Shukirallaev

Nókıs 2022
Graflardi ańlatıw usılları
Reje:


1. Graflar teoriyasınıń tiykarǵı túsinikleri
2. Graflarni ańlatıw usılları
3. Graflarda kórik ótkeriw


1. Graflar teoriyasınıń tiykarǵı túsinikleri
Matematikalıq teoriyada hám informatikada graf — bul túyinler (úshler) den ibarat bolǵan bos bolmaǵan jıynaq hám túyinlerdi birlestiruvchi ayqulaqlar kompleksi bolıp tabıladı.
Graf - bul quramalı sızıqsız ko'pbog'lamli dinamikalıq struktura bolıp, quramalı ob'ektlerdiń qásiyetleri hám munasábetlerin sáwlelendiredi.
Ob'ektler túyin yamasa graf uzellari kórinisinde hám munasábetler ayqulaq yamasa baǵdarlanǵan qırlar sıyaqlı ańlatpalanadı.
«Graf» túsinigin birinshi márte 1936 jıl Vengriya matematigi Denni Kyonig kirgizgen. Lekin graflar teoriyası boyınsha 1-jumıs Leonard Eylerga tiyisli bolǵan hám ol 1736 jılda orınlanǵan edi.
XvIII asirde ataqlı shvetsariyalik matematikalıq, mexanik hám fizikalıq Leonard Eyler (1707-1783 yy) Kyonigsberg ko'prigi haqqındaǵı máseleni sheshiw ushın birinshi ret graf túsiniginen paydalanadı.

1.-su'wret. Eski Kyonigsberg qalası sxeması

Graflar teoriyası diskret matematika pániniń bir bólimi bolıp, ol jaǵdayda máseleler sheshimleri sızılmalar formasında ızlenedi. Keyingi payıtlarda hár qıylı diskret ayrıqshalıqlarǵa iye bolǵan esaplaw apparatların proektlestiriwde graflarning áhmiyeti jáne de asdı.
(v, E) sanlar juftligiga graf dep ataladı, bul jerde v - qálegen bos bolmaǵan jıynaq, E bolsa dıń bólim kompleksi, bunda v jıynaq elementleriniń tártiplenbegen juplıqları kompleksi.
v - jıynaq elementleri grafning úshleri dep ataladı.
E - jıynaq elementleri bolsa grafning qırları dep ataladı.
Eger v chekli bolsa, graf chekli dep ataladı, keri jaǵdayda sheksiz graf dep ataladı.
Jol (path) - bul qandayda bir túyinnen basqa bir túyinge shekem bolǵan qasında jaylasqan túyinler izbe-izligi bolıp tabıladı.

B

2.-su'wret. Grafning tiykarǵı belgileri
Grafning úshleri hám qırları kompleksin uyqas túrde hám sıyaqlı belgilenedi. bul jıynaqta úshler berilgen boladı. kompleksinde bolsa qirallarning qushni úshler juftligi menen anıqlanadı.
Mısalı :
Bul halda grafning grafik kórinisi tómendegishe boladı (3.-su'wret):

3.-su'wret. Grafga mısal
Qır eki úsh menen anıqlanadı. Ulıwma uchga iye bolǵan eki qır qońsılas esaplanadı. Eger grafning eki uchi qır menen tutastirilgan bolsa, bul úshler qońsılas úshler dep ataladı. Grafning bir úshten shıqqan eki qırı qońsılas qırlar dep ataladı. Eger grafda bası hám aqırı bir túyinde tutasatuǵın qır ámeldegi bolsa, oǵan qıstırıp qoyıwlı qır dep ataladı.

4.-su'wret. Qır túsinigi
Eger grafda qayta (márteli) qırlar ámeldegi bolsa, bunday grafga multigraf dep ataladı. Eger grafda márteli qırlar menen birge uchni óz-ózi menen tutastiruvchi qıstırıp qoyıwlar da ámeldegi bolsa, bunday grafga psevdograf dep ataladı (5.-su'wret).
5.-su'wret. A) multigraf; B) psevdograf
Qálegen túyinnen basqa qandayda bir túyinge shaqırıq ámeldegi hám shaqırıq óz-ara bolsa, bul halda bunday graf jóneltirilmagan graf (graph) dep ataladı (6.-su'wret. A).
Eger graf túyinleri óz-ara baylanısqan bolsa, lekin bul ayqulaqlar arqalı munasábet tek bir tárepleme bolsa, ol túrde bunday graflar jóneltirilgen graflar (oriented graph) dep ataladı (6.-su'wret. B).
6.-su'wret. A) jóneltirilmagan graf; B) jóneltirilgen graf
Salmaqlıqqa (vaznga) iye bolǵan graf (weighted graph) - bul qırları (yo'ylari) salmaqları menen berilgen graf esaplandı. (i, j) qırdıń salmaǵı wij sıyaqlı belgilenedi (7.-su'wret).

7.-su'wret. Salmaqlıqqa iye bolǵan graf
Eger v jıynaqtıń quwatı n ga teń bolsa, n sanı grafning tártibi dep ataladı. Eger v jıynaqtıń quwatı n ga teń bolsa, E jıynaqtıń quwatı m ga teń bolsa, graf (n, m) graf dep ataladı.
Túyin dárejesi (vertex degree) - bul odan shıǵıwshı ayqulaqlar sanı esaplanadi. deg (7) = 2, deg (1) = 3
Halqa (cycle) - bul bası hám aqırı tutasıwshı túyinnen ibarat jol esaplanadı : (4, 6, 7, 8, 3, 4) (1. 2. 8.-su'wret).
G (v, E) grafda onıń barlıq túyinleri dárejeleri jıyındısı - jup, grafning qırları sanınıń ikkilanganiga teń.
Túyinler dárejesine salıstırǵanda jup yamasa toq dep ataladı, eger olardıń dárejeleri uyqas túrde jup yamasa toq bahaǵa teń bolsa.
8.-su'wret. Grafning halqa hám túyin dárejesine mısal
Tolıq graf (complete graph) - bul qálegen túyinleri qońsılas bolǵan graf esaplanadi yaǵniy barlıq túyinler óz-ara birlestirilgen. (9. a-su'wret)
Grafni tolıqlawıshsı bul áyne bir túyinler, atap aytqanda bir qırlardan shólkemlesken hám ámeldegi grafni tolıq bolıwın támiyinleytuǵın grafga aytıladı. (9. b-su'wret)a)

b)

9.-su'wret. a) tolıq graf b) graf jáne onıń tolıqlawıshsı
Tolıq, jóneltirilmagan grafda qırlar sanı tómendegi formula (1) arqalı anıqlanadı :
(1)
Qayda n - ayqulaqlar (túyinler) sanı.
D grafning to'yinganligi (density) grafning qırlrining túyinler qatnasına tolıqlıq munasábet koefitsientini belgileydi hám tómendegi formula (2) arqalı anıqlanadı :
(2)
Qayda n - grafning túyinler sanı, m - grafning qırlar sanı.
Grafning to'yinganligi koefitsientiga qaray eki hil graf kórinisi anıqlaw múmkin: to'yingan graf hám siyrek graf (10.-su'wret).
To'yingan graf (dense graph) - bul qırlar sanı bolıwı múmkin bolǵan maksimalǵa teń bolǵan graf esaplanadi. (D>0. 5)
Siyrek graf (sparse graph) - bul qırları sanı túyinler sanına jaqın bolǵan graf bolıp tabıladı. (D<0. 5)

1. 
   b)
   
2. 
   

10 -súwret. a) to'yingan graf (D=0. 9 ) b) siyrek graf (D=0. 33)
Tómende túrli kórinistegi graflar keltirilgen.
11-súwret. a-d ápiwayı graf, c-tolıq graf, e-multigraf, f-psevdograf, g-digrafdagi shınjır, h-digrafda sheńber.