Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Тақырып 7. Желіні суреттеудің, талдаудың және синтездеудің математикалық аппараты. Графтар теориясының элементтері.




Тораптың топологиялық құрылымының математикалық моделі ретінде граф түріндегі модель жиі қолданылады (сур. 7.1).

 

Сур. 7.1. Желі құрылымының графы

 

Әдетте граф төбелері (1, 2, 3, 4) цифрларымен белгіленеді және КТ және/немесе ШП-мен сәйкестендіріледі, ал граф қабырғалары - (а, b, с, d, e) әріптерімен белгіленеді де, байланыс каналдарына сәйкес келеді. Символикалық формада графтар G (А, В) түрінде белгіленеді, мұндағы G белгісі осы түсінікке сәйкес логикалық мазмұнды көрсетеді; А = {а1, а2, …, aN} – граф төбелерінің жиыны; В = {bij} - aj және aj төбелері арасындағы қабырғалар жиыны. Граф төбелері көршілес деп аталады, егеролар қабырғамен байланыстырылса. Қабырғалар оиентарленген немесе бағытталған (е қабырғасы) және ориентирленбеген немесе бағытталмаған (ребра а, b, с, а) болуы мүмкін. Ориентирленген өабырға бір жақты каналға сәйкес келеді, ал ориентирленбеген қабырға – екіжақты каналға сәйкес болмақ.

Графтың үш түрі бар: 1) ориентирленген графтар, барлық қабырғалары ориентирленген; 2) ориентирленбеген графтар, ориентирленген қабырғаларды қамтымайды; 3) көршілес типті графтар, онда ориентирленген де, ориентирленбеген де қабырғалар бар. Әр қабырғаға «салмақ» меншіктеледі – сан немесе сандар жиыны, ол берілген қабырғаның қандай да бір болмасын қасиетін сипаттайды. Салмақ ретінде мыналарды алуға болады, мысалы, канал ұзындығы, өткізгіштік мүмкіндігі, ақпаратты беру жылдамдығы, стандартты каналдар саны, сенімділігі, құны және т.б. Граф төбелеріне де белгілі бір салмақ меншіктелуі мүмкін.

Кіріс немесе шығыс (инциденттік) қабырғалар саны r(ai) түйінінің рангы деп аталады, мұндағы i – түйін нөмірі. r(a1) = 2, r(а2) = 3. 1 ранг түйіні тұйықталған болып табылады, себебі ол арқылы ешқандай жол өте алмайды.

ai түйінінен aj түйініне mij жолы – бұл қабырғалардың реттелген жиыны, ai түйінінде басталып, aj түйінінде аяқталады. Жол үшін әрбір алдыңғы қабырғаның аяғы келесі қабырғаның басымен сәйкес келеді. Жолдар өздігінен қиылыспайтын болу керек, яғни бір түйін арқылы екі рет өтпеу керек. Граф үшін 1 және 3 төбелер арасында үш жол болады: ab, cd, aed. Осы төбелер арасындағы жлдар жиыны m13 = ab и cd және aed. Қабырғалар сияқты жолдар да бағытталған және бағытталмаған болуы мүмкін.

r (mij) жолының рангы дегеніміз осы жолға кіретін қабырғалар саны Жолдың минимальды рангы 1-ге тең, мысалы r (m12) = 1, ал макси­мальды - N – 1-ге тең, мұндағы N – граф төбелерінің саны, бұл жағдайда жол барлық төбе арқылы өтетін болады.

Бір төбеден басталып сол төбеде аяқталатын жол контур (цикл) деп аталады.

h байланыстылығы дегеніміз төбелердің барлық жұптарының арасындағы тәуелсіз жолдардың минимальды саны. Граф үшін h = 2.

Құрылымның графтар көмегімен бейнеленген негізгі сипаттамалары. Қалааралық және халықаралық байланыстардың қосымша торабының құрылымын құру үшін беріліс жолын анықтау қажет. Екінші торап үшін беріліс жолы – белгілі бір талап етілген сапаға жауап беретін, ақпараттарды (электросигналдар, электртолқындар – эфир, жарық сәулелері, рентген-сәулесі) беруге арналған сәйкес сфера. Беріліс жолы бастапқы желі нүктесінде басталып, аяқталады, онда энергияны енгізуге және шығаруға мүмкіндік алуға болады. Мұндай нүктелерге тораптық түйіндер (сонымен бірге ауыстырып қосу пункті), бастапқы желінің шеткі станциялары, бастапқы жергілікті тораптың шығыстары жатады.

Сызық (желі, линия) – бастапқы торап үшін қолданылатын кейбір жол, өзінің құрамына оған екі жағынан қосылған екінші (қосымша) тораптың техникалық құрылғыларын қамтиды.

Торап құрылымын анықтау мыналарға байланысты:

1. бастапқы қалааралық тораптың шеткі түйіндерінің орналасқан орны берілген;

2. осы түйіндердің саны және осы түйіндердегі құрылғылар типтері анықталған;

3. есептеу бастапқы тораптағы (орны сол сәтте әлі анықтала қоймаған) басқа шеткі түйіндердің пайда болу мүмкіндігін ескере отырып жүргізіледі.

Қалааралық байланыстың бірінші торабы берілген тиянақты түйіндер негізінде, немесе берілген тиянақты территорияда дамиды. Бірінші құрылым сондықтан да бірінші тораптың графтық моделі деп аталады, ал екіншісі қалааралық байланыстың территориялық-бағытталған торабы деп аталады.

Екінші (қосымша) каналдарының шоғырын ұйымдастыру жолын және трассасын анықтау. Желі түйіндері арасындағы мүмкін болатын жолдарды анықтаудың бірнеше тәсілдері бар.

Соның ішіндегі ыңғайлысы және жеңіл программаланатыны – жол бұтағын құру болып табылады. Желі түйіндері өзара жолмен байланысады, оны бұтақ түрінде жеңіл көрсетуге болады.

Бұтақ – циклсыз жекелеген граф.

Маршрут – төбелер мен қабырғалардың ақырғы кезектесетін тізбегі.

Маршрут ашық және тұйықталған болуы мүмкін.

Желіні құрған кезде маршрут үнемі ашық болады.

Жолдағы қабырғалар саны жол ұзындығы деп аталады. Жол ұзындығы осы жолға кіретін ұзындықтар қосындысымен анықталады.

Жол сыйымдылығы – осы жолға кіретін тармақтардың минимальды сыйымдылығы.

Бұтақты құру алгоритмі. Бұтақты беру үшін байланыс матрицасын құру қажет, бұл – екі төбенің байланысын анықтайтын матрица, себебі желі – тармақсыз ақырғы граф.

Берілген желі үшін байланыс матрицасын құралық.

B – байланыс матрицасы, желіде қанша қатар және қанша баған бар. Қосымша диагонал – түйіндердегі (қажет емес) тармақтар.

 

1. k=1, 2, 3, 4, 5 түйінін таңдаймыз (ол қажетті бұрышпен тікелей байланыспаған) k - шы қатарды таңдаймыз;

2. осы жолдың бағандар нөмірін теріп жазамыз, ондағы матрица элементтерінің мәндері bij=1 және k түйінімен түзілген бірінші рангты түйіндердің ішкі жиынын аламыз;

3. осындай ішкі жиынды екінші рангты түйіндерден де аламыз;

4. бұтақты құрған кезде бағандар нөмірлері (осыған сәйкес ішкі жиын түзілген боладтын);

5. құру n=3 (байланыс торабы үшін) рангына дейін жалғасады, мұнда үшінші рангтан жоғарылары цикл түзе бастайды;

Жол бұтағын иемдене отырып, тиянақталған түйіндер арасындағы мүмкін болатын барлық жолдарды жеңіл табуға болады. Төменде 1,2-ші түйіндерге арналған бұтақ тұрғызылғын.

 

Негізгі әдебиет: 5 [45-64]

Қосымша әдебиет: 14 [60-75]

Бақылау сұрақтары:

1. Граф қалай жазылуы мүмкін?

2. Подграф дегеніміз не?

3. Нуль граф дегеніміз не?






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных