1 модуль бойынша бақылау өткізуге арналған сұрақтар
-дәріс. Желіні суреттеудің, талдаудың және синтездеудің математикалық аппараты. Графтар теориясының элементтері. Желінің құрылымдық сенімділігі мен өміршеңдігі
жүктеу/скачать 0,55 Mb.
|
1 модуль бойынша ба ылау ткізуге арнал ан с ра тар
| 8-дәріс. Желіні суреттеудің, талдаудың және синтездеудің математикалық аппараты. Графтар теориясының элементтері. Желінің құрылымдық сенімділігі мен өміршеңдігі.
Тораптың топологиялық құрылымының математикалық моделі ретінде граф түріндегі модель жиі қолданылады (сур. 7.1). Сур. 7.1. Желі құрылымының графы Әдетте граф төбелері (1, 2, 3, 4) цифрларымен белгіленеді және КТ және/немесе ШП-мен сәйкестендіріледі, ал граф қабырғалары - (а, b, с, d, e) әріптерімен белгіленеді де, байланыс каналдарына сәйкес келеді. Символикалық формада графтар G (А, В) түрінде белгіленеді, мұндағы G белгісі осы түсінікке сәйкес логикалық мазмұнды көрсетеді; А = {а1, а2, …, aN} – граф төбелерінің жиыны; В = {bij} - aj және aj төбелері арасындағы қабырғалар жиыны. Граф төбелері көршілес деп аталады, егеролар қабырғамен байланыстырылса. Қабырғалар ориентирленген немесе бағытталған (е қабырғасы) және ориентирленбеген немесе бағытталмаған (ребра а, b, с, а) болуы мүмкін. Ориентирленген өабырға бір жақты каналға сәйкес келеді, ал ориентирленбеген қабырға – екіжақты каналға сәйкес болмақ. Графтың үш түрі бар: 1) ориентирленген графтар, барлық қабырғалары ориентирленген; 2) ориентирленбеген графтар, ориентирленген қабырғаларды қамтымайды; 3) көршілес типті графтар, онда ориентирленген де, ориентирленбеген де қабырғалар бар. Әр қабырғаға «салмақ» меншіктеледі – сан немесе сандар жиыны, ол берілген қабырғаның қандай да бір болмасын қасиетін сипаттайды. Салмақ ретінде мыналарды алуға болады, мысалы, канал ұзындығы, өткізгіштік мүмкіндігі, ақпаратты беру жылдамдығы, стандартты каналдар саны, сенімділігі, құны және т.б. Граф төбелеріне де белгілі бір салмақ меншіктелуі мүмкін. 0-граф (бос, байланыспаған граф) – қабырғалары жоқ граф. Кіріс немесе шығыс (инциденттік) қабырғалар саны r(ai) түйінінің рангы деп аталады, мұндағы i – түйін нөмірі. r(a1) = 2, r(а2) = 3. 1 ранг түйіні тұйықталған болып табылады, себебі ол арқылы ешқандай жол өте алмайды. ai түйінінен aj түйініне ij жолы – бұл қабырғалардың реттелген жиыны, ai түйінінде басталып, aj түйінінде аяқталады. Жол үшін әрбір алдыңғы қабырғаның аяғы келесі қабырғаның басымен сәйкес келеді. Жолдар өздігінен қиылыспайтын болу керек, яғни бір түйін арқылы екі рет өтпеу керек. Граф үшін 1 және 3 төбелер арасында үш жол болады: ab, cd, aed. Осы төбелер арасындағы жлдар жиыны 13 = ab и cd және aed. Қабырғалар сияқты жолдар да бағытталған және бағытталмаған болуы мүмкін. r (ij) жолының рангы дегеніміз осы жолға кіретін қабырғалар саны Жолдың минимальды рангы 1-ге тең, мысалы r (12) = 1, ал максимальды - N – 1-ге тең, мұндағы N – граф төбелерінің саны, бұл жағдайда жол барлық төбе арқылы өтетін болады. Бір төбеден басталып сол төбеде аяқталатын жол контур (цикл) деп аталады. Нақты желіде ережеге сәйкес берілген түйіндерді байланыстыру үшін барлық мүмкін болатын жолдар жыйыны қолданбайды, тек қандай да бір белгіленген көрсеткіш бойынша немесе берілген қасиеттеріне сәйкес қолданылады. Байланысқан дегеніміз –желінің кез-келген түйіні кем дегенде бір жолмен байланысқан. h байланыстылығы дегеніміз төбелердің барлық жұптарының арасындағы тәуелсіз жолдардың минимальды саны. Граф үшін h = 2. Барлық желіні байланысқан деп айта алмаймыз, тек берілген түйіндерді сонымен қатар берілген қасиеттеріне сәйкес жолдар жыйынын айтамыз. Осыған сәйкес ранг бойынша шектеу енгіземіз. Мысалы, біздің жағдайда h24 = 2, h24 (r = 1) = 1. Байланыс желісінің негізгі құрылымы мен сипаттамаларын қарастырылған: толық байланысты, бұтақ түрлес, сақиналық және т.б. Берілген құрылым (немесе граф) бойынша желіге анализ жасау кезінде мүмкін болатын жолдары, және оның сипаттамалары, сондай-ақ байланыс сенімділігі мен басқа да көрсеткіштері анықталады. Кейде есептеу машинасымен жұмыс жасағанда граф түріндегі бейнесіне оралмай- ақ байланыс жүйесін қайта анализдеу қажеттілігі туады. Байланыс жүйесінің математикалық қойылымының бір пішіні алгебралық тапсырмасы және оның құрылымдық матрица түрі болып табылады. жүктеу/скачать 0,55 Mb. Достарыңызбен бөлісу:
|