Graf tu’rleri. Awırlıqqa iye bolǵan graf (weighted graph) – bul qabırǵaları awırlıqları menen bеrilgen graf esaplanadı. (i,j) qabırǵanıń awırlıǵı wij túrinde bеlgilenedi Tolıq graf (complete graph) – bul qálegen túyinleri qońsı bolǵan graf esaplanadı. (barlıq túyinler óz-ara birlestirilgen)Graftı toltırıwshı anıq bir túyinler hám anıq bir qabırǵalardan quralǵan hám bar graftı tolıq bolıwın támiyinlewshi grafqa aytıladı.
Tolıq, baǵdarlanbaǵan grafta qabırǵalar sanı: (n(n-1))/2 D graftıń toyınǵanlıǵı (density):D=2m/(n(n-1)) Toyınǵan graf (dense graph) – bul qabırǵalar sanı bolıwı múmkin bolǵan maksimalǵa tеń bolǵan graf esaplanadı. (D>0.5) Siyrek raf (sparse graph) – bul qabırǵalar sanı túyinler sanına jaqın bolǵan graf esaplanadı. (D<0.5) Eyler grafı. Bizge baǵıtlandırılmaǵan G graf berilgen bolsın. Eyler tsiklında graftıń qandayda bir túyininen shıǵıp barlıq barlıq qabırǵalarınan tek bir márte ótip yaǵnıy usı túyinge qaytıp keliwi kerek.Grafta Eyler tsiklı payda bolıwı ushın: a) Graf baylanǵan bolıwı;b) Graftıń barlıq túyinleriniń lokal dárejeleri jup bolıwı kerek; Grafda Eyler shınjırı payda bolıwı ushın: a) Graf baylanǵan bolıwı;b) Graftıń 2 túyini(baslanıwı hám aqırǵı) lokal dárejeleri taq bolıp, qalǵan barlıq túyinleriniń lokal dárejeleri jup bolıwı kerek. Eger G baǵıtlanbaǵan grafta Eyler tsiklı bar bolsa, bunday grafqa Eyler grafı dep
15. qon’silasliq matritcasi.Meyli G graf baǵdarlanbaǵan bolsın. Graftıń qońsılas matritsasında Aij dıń baǵanalarına hám qatarlarınada graftıń túyinlerine sáykes qoyamız. Ol jaǵdayda
Aij= G baǵıtlanǵan graf bolsın. Ol jaǵdayda qońsılas matritsası Aij dıń qatarlarınada hám baǵanalarınada túyinlerin sáykes qoyamız. Ol jaǵdayda
Aij=
16.Insedentlik matritcasi Baylanıs (incidentlik) matritsası. Bizge G baǵıtlanbaǵan graf berilgen bolıp, ol shekli bolsın. Meyli (a1,…,an), G graftıń qabırǵaları bolsın. Onda baylanıs matritsası ||Aij||, i=1,m, j=1, n m sanlı qatar hám n sanlı baǵanadan ibarat boladı, Aij matritsanıń baǵanalarına G nıń túyinleri, qatarlarına G nıń qabırǵaların sáykes qoyamız. Ol jaǵdayda
Aij=
qaǵıydadan paydalanıp baylanıs matritsasın payda etemiz.Eger G baǵıtlandırılǵan graf bolsa, onda
Aij=
