Telekommunikaciya texnologiyalari hàm kàsiplik tàlim
Qońsiliq hàm intsidentlik matritsalari. Graflardiń izomorfligi
Download 148.96 Kb.
|
Общий 20
- Bu sahifa navigatsiya:
- Marshrut, shınjır, cikller. Eyler hám Gamilton graflari Reje: Marshrut, shınjır, cikller.
Qońsiliq hàm intsidentlik matritsalari. Graflardiń izomorfligi.
Reje: Qońsiliq hàm intsidentlik 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. Marshrut, shınjır, cikller. Eyler hám Gamilton graflari Reje: Marshrut, shınjır, cikller. 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ı. Download 148.96 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling