Tashkent informaciya texnologiyalari universiteti

17 Tema: Qońsiliq hàm intsidentlik matritsalari. Graflardiń izomorfligi.
Reje:

1. 
   Qońsiliq hàm intsidentlik matritsalari.
   
2. 
   Qońsiliq matritsalari.
   

Endi grafdiń basqa bir beriliwi usılı negizinde yotuvchi graf úshleri qońsılaslıǵı matritsasi túsinigin qaray shıǵamız.
- úshleri sanı ga teń bolǵan belgilengen, sirtmoqsiz hám márteli qırlarsız graf bolsın.
Elementleri
kóriniste anıqlanǵan (; ) matritsani grafning úshleri qońsılaslıǵı matritsasi dep ataymız.
Bul tariypdan sirtmoqsiz hám márteli qırları bolmaǵan graf úshleri qońsılaslıǵı matritsasining bas qiyiqida tek nollar bolıwı, qatarlarındaǵı birler sanı bolsa uyqas úshlerdiń dárejelerine teńligi kelip shıǵadı.
1- mısal. 1- formada suwretlengen grafgning úshleri qońsılaslıǵı matritsasi kóriniste boladı.
Úshleri sanı ga teń bolǵan belgilengen oriyentirlangan grafning úshleri qońsılaslıǵı -matritsasi dep elementleri kóriniste anıqlanǵan (,) matritsaga aytıladı.
2- mısal. 2- formada suwretlengen orgrafning úshleri qońsılaslıǵı matritsasi tómendegishe boladı :. Endi úshleri bolǵan belgilengen oriyentirlanmagan multigraf bolsın. elementleri grafning hám úshlerin tutastiruvchi qırlar sanına teń bolǵan () matritsa oriyentirlanmagan multigrafning úshleri qońsılaslıǵı matritsasi dep ataladı.
3- mısal. 1- formada suwretlengen oriyentirlanmagan multigraf úshleri qońsılaslıǵı matritsasi tómendegishe boladı :. Márteli ayqulaqları bolǵan sirtmoqsiz orgraf úshleri qońsılaslıǵı matritsasi túsinigin da joqarıdagiga uqsas tariyplew múmkin.

18 Tema: Marshrut, shınjır, cikller. Eyler hám Gamilton graflari


Reje:

1. 
   Marshrut, shınjır, cikller.
   
2. 
   Eyler hám Gamilton graflari
   

Baylanısqan graflar. Marshrut, shınjır, cikller
Bir-biri menen ústpe-úst tushmaydigan qálegen eki úshleri baylanısqan
graf baylanısqan 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 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 komponentleri dep atalıwshı baylamlı bólimlerdiń birlespesi dep
qaraw múmkin.
Tegis G  (v, Ol) graf ushın m r 1 n  k
teńlik orınlı bolıp tabıladı, bunda m  v, n  Ol, r - jaqlar sanı,
k - baylamlılıq komponentalar sanın uzınlıqtaǵı marshrut dep n ta qırdıń bos bolmaǵan izbe-izligine aytıladı. Qońsılas ayqulaqlar izbe-izligi jol, qońsılas qırlar izbe-izligi shınjır dep ataladı. Basqasha tariyplansa, qayta qırlarǵa iye bolmaǵan marshrut shınjır dep ataladı. Jabıq shınjır bolsa cikl dep ataladı.
Eyler grafi. Gamilton grafi. Ápiwayı shınjırlardı anıqlaw
Yo'naltirilmagan G graf berilgen bolsın. Eyler sikli sonday siklki, ol jaǵdayda
grafning málim bir uchidan shıǵıp, barlıq qırlardan tek bir ret ótip, taǵı
sol uchga qaytıp keliwi kerek.
Grafda Eyler sikli ámeldegi bolıwı ushın :
a) Graf baylanısqan bolıwı ;
b) Grafning barlıq úshleriniń dárejeleri jup bolıwı kerek;
Grafda Eyler shınjırı ámeldegi bolıwı ushın :
a) Graf boglangan bolıwı ;
b) Grafning 2 uchi dárejeleri toq bolıp, qalǵan barlıq úshleriniń dárejeleri jup
bolıwı kerek.
Grafning barlıq qırlarınan bir retten ótken shınjır eyler shınjırı
dep ataladı.