Jlantirish vazirligi toshkent axborot texnologiyalari universiteti urganch filiali
Tekis grafga izomorf graf planar graf deb ataladi
Download 401.28 Kb.
|
multimediya trafiklarini zamonaviy darajadagi marshrutizatsiyalash
|
Tekis grafga izomorf graf planar graf deb ataladi.
Grafning maxsus turdagi ko‘phad yordamida berilishi. Grafni maxsus turdagi ko‘phad yordamida ham berish mumkinligini ta’kidlaymiz. Uchlari to‘plami V = [vi,v2,...,vm] bo‘lgan G graf berilgan
bo‘lsin. G grafning yakkalangan uchlari yo‘q deb faraz qilamiz,. Bu grafni m ta x1,x2,...yxm o‘zgaruvchilarga bog‘liq i ko‘rinishdagi ko‘phad yordamida tasvirlash mumkin, bu yerda ko‘paytma i < j shartni qanoatlantiruvchi barcha (i, j) juftlar bo‘yicha amalga oshiriladi, x, o‘zgaruvchi v, eV uchga mos keladi, ay - v, va v7 uchlarni tutashtiruvchi qirralar soni, (7, - v, uchdagi sirtmoqlar soni. Qo‘shnilik matritsalari. Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo‘shniligi matritsasi tushunchasini qarab chiqamiz. G = (V, U) - uchlari soni m ga teng bo‘lgan belgilangan, sirtmoqsiz va karrali qirralarsiz graf bo ‘lsin. Elementlari l,agar i va j uchlar qo'shni bt/lsa, O^aks holda. ko‘rinishda aniqlangan A = (aj) (i = 1,2,...,m; j = l,2,...,m) matritsani grafning uchlari qo‘shniligi matritsasi deb ataymiz. Bu ta’rifdan sirtmoqsiz va karrali qirralari bo‘lmagan graf uchlari qo‘shniligi matritsasining bosh diagonalida faqat nollar bo‘lishi, satrlaridagi birlar soni esa mos uchlarning darajalariga tengligi kelib chiqadi. Uchlari soni m ga teng bo‘lgan belgilangan oriyentirlangan G = (V, U) grafning uchlari qo‘shniligi m x m -matritsasi deb elementlari _ fl,agar (7, j)^Ubo'lsa, a*J I 0, aks holda. ko ‘rinishda aniqlangan A = (aj) (i = 1,2,..., m, j = 1,2,..., m) matritsaga aytiladi. Endi G uchlari 1,2,..., m bo‘lgan belgilangan oriyentirlanmagan multigraf bo‘lsin. an elementlari G grafning i va j uchlarini
tutashtiruvchi qirralar soniga teng bo‘lgan A = (aj) (i, j = 1,2,..., m) matritsa oriyentirlanmagan multigrafning uchlari qo‘shniligi matritsasi deb ataladi. Karrali yoylari bo‘lgan sirtmoqsiz orgraf uchlari qo‘shniligi matritsasi tushunchasini ham yuqoridagiga o‘xshash ta’riflash mumkin. teorema. Graflar faqat va faqat uchlari qo'shniligi matritsalari bir- birlaridan satrlarining o 'rinlarini va ustunlarining o 'rinlarini mos almashtirishlar yordamida hosil bo 'lsagina izomorf bo 'lishadi. Shunday qilib, manfiymas butun sonlardan tashkil topgan va graf uchun uchlari qo‘shniligi matritsasi bo‘lgan kvadrat matritsa bilan graf orasida bir qiymatli moslik (izomorflik aniqligida) bor degan xulosa va, bundan, graflar nazariyasi bo‘yicha izlanishlar maxsus shartlarni qanoatlantiruvchi mat-ritsalarni tadqiq qilishga keltirilishi mumkinligi kelib chiqadi. Ui, 112,..., u„ (n > 1) qirralarga ega yakkalangan uchlari, sirtmoq va karrali qirralari bo ‘lmagan graf uchun elementlari agar и; va iij qirralar umumiy uchga ega bo'lsa, agarUi = Uj boMsayoki ularning umumiy uch i bo'lmas a, quyidagicha aniqlangan C = (cij) (i = 1,2,..., n, j = 1,2,...,n) nxn -matritsa grafning qirralari qo‘shniligi matritsasi deb ataladi. Ravshanki, sirtmoqsiz va karrali qirralarsiz graf qirralari qo‘shniligi matritsasi bosh diagonalga nisbatan simmetrik kvadrat matritsadir va uning bosh diagonali nollardan iborat.
Insidentlik matritsalari. Uchlari 1,2,...,m va qirralari u1,u2,...,un (n 1) bo‘lgan belgilangan graf berilgan bo‘lsin. Bu grafning uchlariga satrlari, qirralariga esa ustunlari mos keluvchi va elementlari ko‘rinishda aniqlangan B = (by) (i = 1,2,..., m, j = 1,2,..., n) matritsa grafning insidentlik matritsasi deb ataladi. Endi uchlari 1,2va qirralari Ui,ii2,...,un (n > 1) bo‘lgan belgilangan sirtmoqsiz orgrafni qaraymiz. Elementlari ko‘rinishda aniqlangan B = (bij) (i = 1,2,...,m, j = 1,2,...,n) matritsaga grafning insidentlik matritsasi deb ataladi. teorema. Graflar (orgraflar) faqat va faqat insidentlik matritsalari bir-birlaridan satrlarining o'rinlarini va ustunlarining o'rinlarini mos almashtirishlar yordamida hosil bo 'lsagina izomorf bo'lishadi. 1.4Masalaning qo‘yilishi Telekommunikatsiya tarmoqlari va tarmoq tugunlarining faoliyati samaradorligi asosan marshrutlash masalalarini echish bilan aniqlanadi. Odatda Bajardi: bet: Kutliboyev T.Q. marshrutlash algoritmlari yoki amallari ikki bosqichni ko‘zda tutadi: Tayyorlov va marshrutlash jarayonining o‘zi. Tarmoqlarda marshrutlash masalalarini echish uchun yuqori o‘xshashlikka ega, biroq shu bilan birga tarmoqning notekis yuklashga olib keladigin taqsimlangan boshqaruvga asoslangan algoritmlar qo‘llaniladi. Paketlarni uzatish samaradorligini ta’minlashga imkon beradigan, shuningdek mavjud taqsimlangan marshrutlash usullari bilan uyg‘unlashgan yangi metodlarga extiyoj paydo bo‘lmoqda. Bunday masalalarini echishi mumkin bo‘lgan yondashuvlardan biri tarmoq sigmentlarda garflar nazariyasi Deykstra algoritm asosida axborotlarni marshrutlash, taqsimlash vazifasini bajaruvchi mavjud marshrutlash algoritmlariga qo‘shimcha funksiyalarni kiritish bo‘lishi mumkin. Bunday yondashuvni amalga oshirishda, tarmoqdagi yuklamalarni muvozanatlovchi usullarini yaratishdagi quyidagi masalalarni amalga oshirish lozim bo‘ladi: marshrutlash jarayonining tavsifi; marshrutlash protokollari ; marshrutlash jarayonini graflarda ifodalash marshutlash masalalarida yuklamalarni taqsimoti; yuklama taqsimlashning mezonlari; dinamik marshrutlash usullari tadqiqi.
II.Bob.Asosiy qism.
Telekommunikatsiya tarmoqlarida marshrutlash asoslari. Marshrutizatorlar o‘zaro yo‘nalish axboroti bilan almashish protokolining paketini etkazib berish uchun tarmoq darajasi protokoli ishlatiladi, chunki faqat u turli tarmoqlardagi marshrutizatorlar orasidagi axborotni uzatishi mumkin. Marshrutizatorlar yo‘nalish axborotlari bilan almashish protokollari yordamida tavsilotning u yoki bu darajadagi tarmoqlararo aloqasining jadvalini tuzadi va to‘g‘ri yo‘l tashkil etish uchun marshrutlash algoritmi yordamida paketni keyingi marshrutizatorlarning qaysi biriga uzatish kerakligi to‘g‘risida qaror qabul qiladi. Shunday qilib, tarmoqda paketlar marshrutlarini aniqlash, yo‘nalish jadvali asosida marshrutizatorlar tomonidan tarmoq darajalaridagina amalga oshiriladi. Yo‘nalishni to‘g‘ri tanlash uchun marshrutizator aloqa xolati o‘zgaruvchanligini inobatga olgan holda, marshrutlash algoritmi va jadvalini korrektirovkalash yo‘nalish axborotlarini almashish protokollari asosida amalga oshiriladi. Demak, tarmoq darajasining asosiy vazifasi bo‘lib yo‘nalishni belgilash jarayoni ya’ni, tarmoqlardagi mavjud ikkita tugun orasida paketlarni uzatish hisoblanadi. 1.4 - rasmda ko‘rsatilgan tarmoq misolida marshrutlash asoslarini ko‘rib o‘tamiz. Berilgan tarmoqda 18 ta alohida tarmoqni (S1,S2,...,S18 - tarmoq nomeri) 20 ta marshrutizator umumiy tarmoqqa birlashtiradi. Marshrutizatorlar, lokal tarmoqlar ulanadigan bir nechta portlarga ega. Marshrutizatorning har bir portiga turli manzillar biriktirilganligi uchun har bir portni tarmoqning alohida tuguni deb qarash mumkin: bunda unga ulangan tarmoqda o‘z tarmoq adresiga va lokal adresga ega, masalan: 1- marshrutizator 3 portga ega ekanligi va unga S1, S2, S3 tarmoqlari ulanganligi ko‘rsatilgan.
Rasmda 3 ta portlarning tarmoq manzillari R1(1), R1(2), R1(3) bilan belgilangan. R1(1) porti S1 nomerli, R1(2)-S2 nomerli, R1(3)-S3 nomerli lokal manzilga egadirlar. Demak, marshrutizatorni har biri o‘z tarmog‘iga kiruvchi bir nechta tugunlar yig‘indisi deb qarash mumkin. Marshrutizator bir yaxlit qurilma bo‘lganligi uchun, u alohida tarmoq manziliga ham, hech qanday lokal manzilga ham ega emas. Transport tarmoqlarida, ikki tugun o‘rtasida paketlarni uzatish uchun bir qancha muqobil yo‘nalishlar odatda har doim mavjud bo‘ladi. Yo‘nalish - bu uzatuvchi nuqtadan qabul qiluvchi nuqtagacha paket o‘tishi kerak bo‘lgan marshrutizatorlar ketma-ketligidan iborat yo‘l yoki masofa hisoblanadi. Demak, berilgan rasmda A oxirgi tugundan B tuguniga uzatilgan paket 17, 12, 5, 4 va 1 yoki 17, 13, 7, 6 va 3 marshrutizatorlari orqali uzatish mumkin. A va B tugunlari orasida yana bir qancha marshrut yo‘llarini topish mumkin. Imkoniyat mavjud bo‘lgan, yo‘nalishni belgilash masalasini marshrutizatorlar va oxirgi tugunlar ishlab chiqadi. Zaruriy yo‘nalishni tanlashda ushbu qurilmalarda tarmoqning joriy konfiguratsiyasi to‘g‘risida ma’lumotiga qarab, hamda yo‘nalishni tanlashning belgilangan omili asosida bajariladi, asosan belgilangan omil sifatini alohida paketlarning yo‘nalish o‘tishidagi tutilishlar yoki paketlarinig ketma-ketligi uchun marshrutning o‘rtacha o‘tkazuvchanlik qobiliyati bajaradi. Ko‘p hollarda marshrut, o‘tilgan oraliq marshrutizatorlar sonini hisobga oluvchi (metrika), juda oddiy omil qo‘llaniladi. Agar qabul qiluvchi tugun tarmog‘ining manzili bo‘yicha, paketning keyingi uzatilishidagi to‘g‘ri marshrut tanlansa, har qanday oxirgi tugun va marshrutizator maxsus axborot tuzilishini taxlil qilib marshrutlash jadvali tuzadi. - rasmda berilgan tartibda, marshrutizatorlarning tarmoq manzili va tarmoq nomerlari uchun maxsus shartli belgilardan foydalanib,
marshrutizatorlarda marshrutlash jadvali qanday ko‘rinishda bo‘lishini ko‘rib o‘tamiz. - Rasm. Tarmoqda marshrutlash asoslari.
Download 401.28 Kb. Do'stlaringiz bilan baham: 
|