Байланысграф теория. Аырып Кіріспе
 Скачать 408 Kb.
|
|
Құрылымның графтар көмегімен бейнеленген негізгі сипаттамалары.Қалааралық және халықаралық байланыстардың қосымша торабының құрылымын құру үшін беріліс жолын анықтау қажет. Екінші торап үшін беріліс жолы – белгілі бір талап етілген сапаға жауап беретін, ақпараттарды (электросигналдар, электртолқындар – эфир, жарық сәулелері, рентген-сәулесі) беруге арналған сәйкес сфера. Беріліс жолы бастапқы желі нүктесінде басталып, аяқталады, онда энергияны енгізуге және шығаруға мүмкіндік алуға болады. Мұндай нүктелерге тораптық түйіндер (сонымен бірге ауыстырып қосу пункті), бастапқы желінің шеткі станциялары, бастапқы жергілікті тораптың шығыстары жатады. Сызық (желі, линия) – бастапқы торап үшін қолданылатын кейбір жол, өзінің құрамына оған екі жағынан қосылған екінші (қосымша) тораптың техникалық құрылғыларын қамтиды. Торап құрылымын анықтау мыналарға байланысты: 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. Нуль граф дегеніміз не? Дәріс 14. АЖЖ әзірлеу негіздері. АЖЖ құрамы және құрылымы. Жобалау – әлі пайда болмаған объектіні берілген шарт бойынша құру үшін (осы объектіні және (немесе) оның жұмыс алгоритмін бастапқы сипаттау негізінде) қажетті сипаттамаларды құрастыру процесі. Жобалау мынадай жұмыстар кешенін қамтиды: іздену, зерттеу, есептеу және құрастыру. Жобалау – адам қызметінің күрделі де ерекше түрі, терең ғылыми білімге, творчестволық ізденіске, жинақталған тәжрибені қолдануға және белгілі бір саладағы тәжрибелерге негізделген, дегенмен көп еңбектенуді талап ететін жұмысты орындау қажеттілігінен де шет қалмаған. Жобалауды автоматтандыру (ЖА) – жобалау процедурасы ЭЕМ-мен тығыз байланыста жүргізіліп, жобаны әзірлеу процесі. ЖА – жобалаушы мен ЭЕМ арасындағы жұмысты рационалды үлестіру кезінде, тапсырманы машиналық шешу тәсілдерін дұрыс таңдауға негіздеп, есептеу техникасы жабдықтарын жүйелі түрде пайдалану. Адам мен ЭЕМ арасындағы функцияларды рационалды үлестіру дегенді – адам негізінен творчестволық тапсырмаларды орындау керек, ал ЭЕМ – дәстүрлі қолмен есептеу тәсілімен салыстырғанда жоғары тиімділікке қол жеткізетін алгоритм түрінде сипатталған тапсырмаларды шешуі қажет деп түсіну қажет. Жобалаудың машиналық тәсілінің елеулі артықшылығы – ЭЕМ-де қымбат тұратын физикалық модельдеуден бас тартып немесе оны қысқартып, жобалау объектілерін математикалық модельдеуге эксперимент жүргізу мүмкіндігі. АЖ мақсаты – сапаны жоғарылату, материалдық шығындарды азайту, жобалау мерзімін қысқарту, жобалаумен айналысатын инженерлік-техникалық жұмысшылар санының өсуіне жол бермеу, олардың еңбек өнімділігін көтеру. АЖ нақты техникалық пәндері: есептеу математикасы мен ЕТ жетістіктерінің негізінде туындады. Нақты техникалық пәндерде техникалық объектілер құру принципі, жобалық тапсырмаларды орындаудың типтік реті мен тәсілдері, жобаланатын объектілер терминдері, жіктемелері мен олардың бағалану принциптері туындап, дамуға ие болды. Көптеген дәстүрлі инженерлік жобалау ережелері, принциптері және тәсілдері автоматтандыру талаптарымен сәйкес және қазіргі заманғы автоматтандырылған жобалау әдістемесіне белгілі бір әсерін тигізіп отыр. Дегенмен, дәстүрлі жобалау кезінде қолмен есептеуге бағытталу көптеген жобалау процедураларының орындалу негізіне есептеу тәсілдерін қолдануға мүмкіндік бермеді. Сондықтан, автоматтандырылмаған жобалау процесінде зерттеудің эксперименталдық тәсілдері және жобалық шешімдер сапасын бағалау (инженерлік тәжерибе негізінде және формальды әдістерді қолданусыз интуицияға сүйеніп алынған шешімдер) кеңінен қолданылады. Жобаланатын объектінің күрделіленуіне байланысты, мұндай жобалаудың мерзімі мен құны өте үлкен. Сондықтан, физикалық эксперимент жүргізуден математикалық модельдеуге көшу қажеттілігі пайда болды (бағалаудың эвристикалық тәсілдерін ауыстыру, параметрлерді анықтау және алгоритмделген процедуралармен құжаттарды дайындау қажеттілігі туындады). Есептеу математикасы – танымал математикалық интерпретацияны қамтитын бірқатар жобалық процедураларды алгоритмдеуге және автоматтандыруға мүмкіндік берді. |