1. Kirisiw Graflar teoriyası haqqında túsinik Tiykarǵı bólim

Tema: Graflar teoriyasınıń tiykarǵı túsinikleri.Graflardıń bazi túrleri.Graftıń beriliw usılları.Qońsılıq hám intsidentlik matricaları.Graflardıń izomorflıǵı

Rejesi:

1.Kirisiw
1. 1. Graflar teoriyası haqqında túsinik
2.Tiykarǵı bólim
2.1. Graflardıń abstrakt anıqlaması hám baslanǵısh túsinikler
2.2. Graflardıń túrleri hám beriliw usılları
3.Juwmaqlawshı bólim
3.1 Graflardıń izomorflıǵı hám súwretleniwi

4.Paydalanılǵan ádebiyatlar

Kirisiw
1736 jılda L. Eyler tárepinen sol dáwirde qızıqlı ámeliy máselelerden biri esaplanǵan Kyonigsberg kópirleri haqqındaǵı máseleniń qoyılıwı hám sheshiliwi graflar teoriyasınıń payda bolıwına tiykar boldı.

Kyonigsberg qalasındaǵı Pregel dáryası ústinde qurılǵan jei kópirler jaylasıwı 1- formadaǵı áyyemgi kartada suwretlengen hám qurılısı tártibinde 1, 2, 3, 4, 5, 6 hám 7 nomerler menen belgilengen. Pregel dáryası Kyonigsberg qalasın sol dáwirde tórt bólimde bolǵan. Qalanıń qálegen bóleginde jaylasqan uyden shıǵıp jeti kópirlerden tek bir retten ótip, taǵı sol uyge qaytıp keliw múmkinbe? Kyonigsberg kópirleri haqqındaǵı bul máseleni sheshiw processinde graflarda arnawlı marshrut (házirgi waqıtta graflar teoriyasında bul marshrut Eyler sikli atı menen júritiledi, bar ekenligi shártleri de tapildi. Bul nátiyjeler daǵaza etilgen tariyxıy ilimiy jumıstıń birinshi beti 2- formada keltirilgen. L. Eylerdiń bul maqalası júz jıldan kóp waqıt dawamında graflar teoriyası boyınsha birden-bir ilimiy jumıs bolıp keldi.

XIX ásirdiń ortalarında graflar teoriyası menen baylanıslı izertlewler G. Kirxgof hám A. Keli jumıslarında payda boldı. “Graf” sóz dizbegi D. Kyonig tárepinen 1936 jılda graflar teoriyasına arnalǵan dáslepki sabaqlıqta ushıraydı.
Graflar teoriyası boyınsha izertlewler nátiyjeleri insan iskerliginiń túrli tarawlarında qollanıladı. Olardan geyparaları tómendegiler bolıp tabıladı: bas qatırmalardı sheshiw; qızıqlı oyınlar ; jollar, elektr shınjırları, integral sxemaları hám basqarıw sistemaların proektlestiriw; avtomatlar, blok -sxemalar hám kompyuter ushın programmalardı izertlew hám taǵı basqa.
Áwele, graftıń abstrakt matematikalıq túsinik retindegi tariypin hám basqa birpara ápiwayı túsiniklerdi keltiremiz. V qanday da bos emes toplam bolsın. Onıń hám elementlerinen dúzilgen kórinistegi barlıq juplıqlar (kortejlar) kompleksin ( V toplamtıń óz-ózine Dekart kóbeymesin ) menen belgileymiz.
Graf dep sonday juplıqqa aytıladı, bul jerde hám - – ( , ) kórinistegi juplıqlar korteji bolıp, toplamnıń elementlerinen dúzilgen bolıp tabıladı.
Endigiden grafni belgilewde jazıw ornına jazıwdan paydalanamız. Graftıń qurawshıların kórsetiw zárúrli bolmasa, ol halda onı latin álipbesiniń bir hárıbi, mısalı, G menen belgileymiz.
Graflar hám olardıń súwretleniwi
Graf - bul túyinler hám qırlar (túyinler juplıǵını birlestiruvchi) kompleksinen ibarat bolǵan abstrakt matematikalıq obyekt bolıp tabıladı.

Graftıń elementleri quramı hám munasebetler dúzilisi beriledi. Graftıń strukturalıq bólimleri bul onıń túyinleri hám qırları bolıp tabıladı.

Tarmaq
Bir neshe jup túyinler aralıq qırlardan ibarat bolǵan túrlishe jollar kompleksi ámeldegi bolıwı múmkin. Jabıq jollar - cikllerdiń ámeldegi bolıwı tarmaqlarǵa tán ózgeshelik bolıp tabıladı.

Jóneltirilmegen graf yamasa simmetrik baylanıslılıq qır ayqulaqlar

Qıstırıp qoyıw - áyne bir túyinnen shıǵıp, taǵı sol túyinge kiretuǵın qır.
Eger graftıń ushlarina qanday da belgiler mısalı sanlari sáykes qoyilǵan bolsa, ol belgilengen graf dep ataladi.
Eger va graflardıń úshlari toplamlari, yaǵnıy hám toplamlar arasida uhlartıń qo‘shnilik munosabatini saqlaydigan o‘zaro bir qiymatli moslik o‘rnatish mumkin bo‘lsa, u holda va graflar izomorf graflar dep ataladi. Bul anıqlamanı tómendegishe ańlatıw múmkin: eger hám olarǵa sáykes bolǵan ( , ) ushın ( , ) bolsa, ol jaǵdayda va graflar izomorf esaplanadı. Eger izomorf graflardan biri oriyentirlengen bolsa, ol halda ekinshisi da, álbette, oriyentirlengen bolıwı hám olardaǵı uyqas ayqulaqlardıń baǵdarları da bir-birlerine uyqas bolıwları shárt.
Graf ushına insident qırlar sanı sol ushtıń lokal dárejesi, yamasa, qısqasha, dárejesi, yamasa valentligi dep ataladı. Grafdagi ushtıń dárejesin menen belgileymiz.Sirtmoqqa insident bolǵan ushtıń dárejesin anıqlawda sonı itibarǵa alıw kerek, qaralayotgan máselege baylanıslı halda sirtmoqni bir qır dep da, eki qır dep da esaplaw múmkin. Ayqınki, bóleklengen ushtıń dárejesi nolǵa teń. Dárejesi birge teń úsh shettegi (yamasa osilgan) úsh dep ataladı. Shettegi (osilgan) ushqa insident qır da shettegi (yamasa osilgan) qır dep ataladı.
Eger graftıń barlıq úshleri birdey dárejege iye bolsa, ol halda bunday graf dárejeli regulyar graf dep ataladı. Úsh dárejeli regulyar graf kubik (yamasa úsh valentli) graf dep ataladı.graf nol dárejeli regulyar graf ekenligin, bolsa () dárejeli regulyar graf ekenligin aytymiz.
Kórinip turıptı, olda, oriyentirlenbegen grafda barlıq úshler dárejeleriniń jıyındısı qırlar sanınıń eki eseine teń jup san boladı, sebebi qırlardı sánegenda hár bir qır esapta eki ret qatnasadı. Sonday etip, XVIII asirde aq L. Eyler tárepinen tastıyıqlanǵan tómendegi tastıyıq orınlı bolıp tabıladı.
Eseli ayqulaqları bolǵan sirtmaqsiz orgraf úshleri qońsılaslıǵı matritsasi túsinigin da joqarıdagiga uqsas tariyplew múmkin.
Sonday etip, teris emes pútin sanlardan shólkemlesken hám graf ushın ushlari qońsılaslıǵı matritsasi bolǵan kvadrat matritsa menen graf arasında bir bahalı uyqaslıq (izomorflik anıqlıǵında ) bar degen juwmaq hám, bunnan, graflar teoriyası boyınsha izertlewler arnawlı shártlerdi qánaatlantıratuǵın mat-ritsalarni izertlewge keltiriliwi múmkinligi kelip shıǵadı.
( ) qırlarǵa iye jalǵızlanǵan úshleri, sirtmoq hám márteli qırları bolmaǵan graf ushın elementleri
Tómendegishe anıqlanǵan
( , ) -matritsa graftıń qirlari qońsıshılıǵı matritsasi dep ataladi.
Oriyentirlangan graflar ushın da odaǵı ayqulaqlardıń baǵdarın (oriyentatsiyasini) inabatqa almastan oriyentirlanmagan marshrut, shınjır hám ápiwayı shınjır túsiniklerin kirgiziw múmkin. Lekin, oriyentirlangan graflar ushın oriyentirlangan marshrut túsinigin kirgiziw tábiy bolıp tabıladı.
Ayqulaqlardıń oriyentatsiyalari esapqa alınǵan ayqulaqlar hám úshler izbe-izligi oriyentirlangan marshrut dep ataladı.
Oriyentirlangan marshrut ushın shınjır túsinigine uqsas jol (yamasa oriyentirlangan shınjır ) túsinigin da kirgiziw múmkin. Baslanǵısh hám aqırǵı úshleri ústpe-úst túsetuǵın oriyentirlangan shınjır kontur dep ataladı.
Marshruttagi eki qońsı qırlarǵa tiyisli úsh ishki úsh yamasa aralıq úsh dep ataladı. Marshrutda qırlar hám úshler tákirarlanıwı múmkin bolǵanı ushın marshruttıń ishki ushi, bir waqtıniń ózinde, onıń baslanǵısh hám (yamasa ) aqırǵı ushi bolıwı da múmkin hám terissi, marshruttıń baslanǵısh hám (yamasa ) aqırǵı ushi onıń ishki ushi bolıwı da múmkin.Tuwrısıda, marshrut:
- baslanǵısh ushqa da aqırǵı ushqa da iye bolmawi múmkin (bunday marshrut óz-ara sheksiz marshrut dep ataladı );
- baslanǵısh ushqa iye bolıp, aqırǵı ushqa iye bolmawi múmkin yamasa, kerisinshe, aqırǵı ushqa iye bolıp, baslanǵısh ushqa iye bolmawi múmkin (bir tárepleme sheksiz marshrut);
- birden-bir qırdan ibarat bolıwı múmkin (notrivial marshrut);
- qandayda-bir de qırǵa iye bolmawi múmkin (nol marshrut yamasa trivial marshrut).
Marshruttıń uzınlıǵı dep odaǵı qırlar sanına aytıladı.
Túrli qırlardan shólkemlesken marshrutga shınjır dep ataladı. Eger shınjırdıń shetlerinen tısqarı barlıq úshleri túrlishe bolsa, ol halda onı ápiwayı shınjır dep ataydı.
Graftıń baylamliligi túsinigi. Eger oriyentirlanmagan grafda shetleri hám úshlerden ibarat marshrut tapılsa, bul hám úshler baylanısqan dep, marshruttıń ózi bolsa hám úshlerdi baylaw marshrut depataladi.
Tuwrısıda, eger qanday da úshlerdi baylaw marshrut qandayda bir úshten bir neshe ret o'tsa, ol halda marshruttıń siklik bólegin alıp tastap (bunda siklik bólektiń ornına marshrutda tek úsh qaldıriladi) taǵı sol úshlerdi baylaw ápiwayı shınjır kórinistegi marshrutni payda etiw múmkin. Sol sebepli, marshrut menen baylanısqan úshler mudami ápiwayı shınjır menen de bo'glangan boladı degen juwmaqqa kelamiz.
Bir-biri menen ústpe-úst tushmaydigan qálegen eki úshleri baylanısqan graf baylamlı graf dep ataladı.
Eger grafdagi eki uchni qandayda bir ápiwayı shınjır menen tutastırıw múmkin bolsa, ol halda bul eki úsh ekvivalent (baylanısqan ) dep ataladı. Bunday úshler kompleksi grafda ekvivalentlik munasábeti menen anıqlanǵan dep esaplanadı. Úshler kompleksi boyınsha ekvivalentlik munasábetin inabatqa alǵan halda berilgen grafni baylamlılıq komponentalari (qısqasha, komponentalari) dep atalıwshı baylamlı bólimlerdiń birlespesi dep qaraw múmkin. Bul jerde berilgen graf baylamlılıq komponentalariga bóleklandi (ajıratıldı ) dep búydew múmkin. Tastıyıqlaw múmkin, hár qanday graf óziniń baylamlılıq komponentalaritıń diz'yunktiv birlespesi retinde ańlatılıwı múmkin, bunda graftıń baylamlılıq komponentalariga bólekleniwi bir bahalı anıqlanadı.
Gollandiyalıq alım Edsger Deykstra algoritmı graftıń baslanǵısh berilgen túyininen baslap qalǵan barlıq túyinlerge shekem bolǵan barlıq eń qısqa jollardı tabadı. Onıń járdeminde, eger barlıq zárúr maǵlıwmatlar berilgen bolsa, mısalı, neft hám sol sıyaqlı ónimlerdi kirip qılıw ushın bir qaladan basqa qalalardıń hár birine barıw ushın qaysı jollar izbe-izligin tańlaw abzallaw ekenligin bilip alıw múmkin. Algoritmdı programmalıq támiynatın ámelge asırıw ushın eki dızbek kerek boladı : logikalıq taypa daǵı visited - kelilgen túyinler haqqındaǵı maǵlıwmatlardı saqlaw ushın hám tabılǵan eń qısqa jollar kirgizetuǵın pútkil taypadaǵı - distance. G={v, E} graf berilgen bolsın. V jıynaqǵa tiyisli barlıq túyinler daslep kelilmegen dep belgilenedi, yaǵnıy visited dızbeginiń elementlerine false baha berip shıǵıladı. Eń ábzal joldı tabıw máselesi qaralıp atır. Distance dızbeginiń hár bir elementine sonday baha beriledi, qálegen potensial joldan úlken bolsın (ádetde, bul bahanı sheksiz úlken baha dep qaraladı, biraq programmada berilgen taypanıń bahalar diapazonındaǵı eń úlken baha retinde alınadı ). Baslanǵısh noqat retinde s túyin saylanadı hám oǵan nol jol belgilenedi: distance [s] = 0, sebebi s-den s-ge shekem hesh qanday qır joq (bul usılda qıstırıp qoyıwlar qaralmaydi).
Sonnan keyin, barlıq qońsılas túyinler tabıladı (s den shıǵıwshı qırlar arqalı ) [ularni t hám ol dep belgileylik] hám olar Birma -bir tekserip kóriledi, yaǵnıy s túyinnen hár bir túyinge shekem Birma -bir marshrut bahası esaplanadı :
- distance[t]=distance[s]+ s hám t arasındaǵı qırdıń salmaǵı ;
- Distance[u]=distance[s]+ s hám ol arasındaǵı qırdıń salmaǵı.
Itimal ol yamasa bul túyinge s den bir qansha jollar bolıwı múmkin. Usınıń sebepinen, distance dızbeginde bul túyinge bolǵan joldıń salmaǵın qayta kórip shıǵıw kerek boladı. Bul usıldıń unamsız tárepi sonda, keri salmaqqa iye bolǵan qırları ámeldegi bolǵan graflardi qayta islew imkaniyatınıń joqlıǵı, yaǵnıy, mısalı, birpara sistema qandayda-bir kompaniya ushın paydasız bolǵan marshrutlardi usınıs qilsa, ol halda ol menen islew ushın Dijkstraniń algoritmınan paydalanıp bolmaydı.
Eger grafning úshler kompleksin óz-ara kesilispeytuǵın sonday eki bólim jıynaqlar (bólekler) ga ajıratıw múmkin bolsaqı, grafning qálegen qırı bul jıynaqlardıń birinen alınǵan qanday da uchni ekinshi jıynaqtan alınǵan qandayda úsh menen tutastiradigan bolsa, ol halda bunday graf eki bp 'lakli graf (bixromatik yamasa Kyonig graft), dep ataladı. Tariypdan kórinip turıptı, olda^ eki bólekli grafning hár bir bólegindegi qálegen eki úsh qońsılas bola almaydı. Qandayda bóleginde tek bir úsh bolǵan tolıq eki bólekli graf juldız, dep ataladı.
Eger eki bólekli graimngturli bóleklerine tiyisli qálegen eki uchi qońsılas bolsa, ol halda bul graf tap 'la eki bo 'lakli graf dep ataladı. Tolıq eki bólekli grafni Kmnbilan belgileymiz, bul jerde, m van menen grafning bóleklerindegi úshler sanları belgilengen. Kmn= (v, Ol) graf ushın| v\=m+n hám| v\^mn bolıwı ayqın, bul jerde| v\ —Kmngrafning úshleri sanı,| Ol[— onıń qırları sanı.
Grafning eki bólekli graf bolıwı haqqındaǵı birpara qosımsha maǵlıwmatlar (Kyonig teoremasi) bul baptın 4-paragrafında keltirilgen. Ikkidan úlken qálegen natural kson ushın kbo 'lakli graf túsinigin da kirgiziw múmkin.
1-mısal. Ózbekistof Respublikası aymaǵındaǵı aeroportlar kompleksin Fbilan, qalalar arasında belgilengen waqıt dawamında ámelge asırılıp atırǵan sjraio^^yj. rning ushıp -qonıw hádiyselerl kortejini Ol menen belgileymiz. Ol halda (v, Ol) juplıqtı graf, dep qaraw múmkin. Bul jerde grafning úshlerine aeroportlar, ayqulaqlarına bolsa samolyotlardıń ushıp -qonıw hádiyseleri sáykes keledi. Tuwrısıda, (v, Ol) grafda márteli ayqulaqlar bolıwı múmkin, eger qanday da sebepke kóre, samolyot uchgan aeroportqa qaytıp qo'nsa, ol halda bul hádiysege qaralayotgan grafdagi sirtmoq sáykes keledi. \
2-mısal. Áyyemgi boshqotirma máseleler qatarına kiretuǵın tómendegi máseleni qaraymız. Qandayda ıdıs daǵı kólemi 8 birlik suyıqlıqtı tek sol ıdıs hám de 5 hám 3 birlik kólemli ıdıslar jardeminde teń eki bólekke bolıń1. 8, 5 hám 3 birlik kólemli ıdıslar daǵı suyıqlıq kólemin, uyqas túrde, a, b hám s Qadaǵan belgilep, arnawlı bir bir waqıt ushın ıdıslar daǵı suyıqlıqtıń kólemleri tiykarında qaralayotgan sistemanıń jaǵdayın ańlatiwshı úshlıqlardı dúzemiz. Máseleniń shártiga kóre, a, b vaso'zgaruvchilar pútkil bahalar qabıl etken halda 0<#<8, 0 < 5 hám 0
Jaǵdaylar kompleksin v menen belgileymiz. Suyıqlıqtı (yamasa onıń bir bólegin) ıdıslardıń birinen basqa qandayda birsine quyılıw nátiyje-sida sistema bir jaǵdaydan basqa jaǵdayǵa ótiwi mumkiri. Atap ótiw kerek, joqarıdaǵı jaǵdaylardıń qálegensidan basqa qandayda birsine tikkeley yamasa tikkeley bolmaǵan ótiw múmkinshiligi ámeldegi bolmawi de múmkin. Sistemanıń bir jaǵdaydan basqa jaǵdayǵa tikkeley ótiwleri kompleksin Ol menen belgileymiz. Nátiyjede payda bolǵan (v, Ol) juplıqtı graf, dep qaraw múmkin. Bul grafning úshleri sistema jaǵdaylarına, ayqulaqları (qırları ) bolsa, tikkeley ótiwlerge sáykes keledi.
Berilgen máseleni sheshiw ushın (v, v) grafning ayqulaqlarınan shólkemlesken sonday izbe-izlik dúziw kerek, bul izbe-izliktiń birinshi hadi <8, 0, 0>, aqırǵı hadi bolsa <4, 4, 0> bolsın. Bunday izbe-izliklardan bin tómende keltirilgen:
<8, 0, 0>, <5, 0, 3>, <5, 3, 0>, <2, 3, 3>, <2, 5, 1>, <7, 0, 1>, <7, 1, 0>, <4, 1, 3>, <4, 4, 0>.