автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Разработка математического и алгоритмического обеспечения обработки информации на основе структурного анализа геодезических графов

ОДЕСЬЮШ ДВРЯАВНИЙ 1ЮЛ1ТЕХШЧШЙ УШНЕРОИТВГ

РГо ОД

На правах рукопису

ФРАССЕР САНЧЕС Карлос Енр1ке

РОЗРОБЛЕННЯ МАТЕМАТИЧНОГО I АЛГОРИШЧНОГО ЗАБЕСПЕЧЕННЯ ОБРОБКИ ШФОРМАЦП НА ОСНОВ 1 СТРУКТУРНОГО АНАЛ13У ГЕОДЕЗИЧНИХ ГРАФ! В

СпеЩашИсть 05.13._0|?-томатизован1 системи управл!ння та сиетеми обробки 1нформацп

Автор е~фер а т дисертацп на адобуття науковоро ступеня ■ кандидата Фехн1чних наук

Одеса - 1536

ДисертаЩею е рукопиь.

Робота виконана в. Одеськоыу дерлсавиому поЛ1техн1Чному ушверситет! на кафедр! "Прикладна математика".

Науковий kepibhiik:

кандидат техшчних наук, доцент Еосгров ГеорПй Николайовпч

Офицйн! опонегаи:

доктор техтчних наук, професор Шкульпан Володимир Русланович

кандидат ф!зико-математичних наук, доцент Петрушна Тетина 1ван1'вна

Пронина организация: НВД " Орбгха" институту кибернетики пл. В. 11 Глушкова HAH Украйш, м.'0деса. . '

Зйхист В1дбудеться 27 червня 19S6p. о 15.00 годин! на гаслданн! хпец1шнзовано1 вчено! ради Д 05". Q8.04 в 'Одеськоыу державному пЬлиехя1чному ушверсдхет! ва, 'адресою: 270Q44 м. Одеса, яр. Шэвченка, 1.

'Bi^ryK на автореферат у" 'двох -лрнтрииках, 'засв!дчений печаткою■установи,просимо направляти за адресов:

270044, м. Одеса, пр/Шевченка, 1,. вченому секретарю ОДПУ.

3 дисертавдею можна , ознайошшюя 'у .б1бл!отец! одеського державного по-итехнгчного 'университету за адресою: 270044, м. Одеса, пр. Шэвченка, 1,;

Автореферат роз i с дани д "¿У" - 1996р.

Вчений секретар , спецца-иаовано! вченоi ради, професор . ...

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальность теми. Ефективнють сучасних автоматизовйних• систем управления промксловлми об'ектами, Шдприемствами, ексном!чними ' c-jcremsi в гяачя!й Mipi визначаеться ршюм шформацойного забез-печення процедур прийляття рокень. Повнота онформац;иного забезпе-чення в свою чергу ааяеюгаь ид м!ри розвитку шформащйних иерея.

Створення сучасних онфоркацШшх мере к (IM) потребуе розроб-ки катеютичних метод!в, алгоритм!чного та програмного за-безпечення, ориентовакого на побудову онформацойних систем оптимально! структура, я.-ci мають власгивост! повиогн та несуперечяосп 1И'5ор>.вд1йного наповнеяня систем. Вщяшешга задач вибору оптимально! структура шформащйнкх систем винккае як на етагн проек-тузання, так i на erani експлуатацп. 1х Повнота i несуперечность обумовляються познотоя i иесуперечиютк» систем розподолених баз знанъ, sKi е нев!д'емп:ш характеристиками будь-якоо 1кформац!йко1 система.'

Вахтою властпв^стю Ш е ix _ тополопчна структура. Бона мае значинй вплиз па еййдкють обмшу !1фркац!ею «!« коркетувачзми i базами знанъ, суттено впливаз на над1йн!сть робо-ти систем, на эфект.твгисть забезпечешш збзр!гания вдастивостей, яко йаяэжагь розвгнакчпмся caMoopraai эуичямся ссотемзм. IU вяастшзост! в значшй Mipi залегать в!Д структур» циклов графа, • soöpassamoro IM, мд паяыюст! в н!3 дублкттге каналов передач! онформацп, вод три дублввання, вод блочно'о сгруктури графа. Проблема оппсу структуриих' влзстивестей {Непрактично не' зиров-зпа, • тр -тат ровышеш кетоди пошуку структур таких систем, при ягавс досягаать' мппкума або максимума впбрано *кря-терго якоси ох функпдонування. До кольгсосних показник1в якост! роботи iM налетать тш« покэзнш«! як надШисть, вартхсть проек-тузання i техпочиоо реалозацп, пэидкють передач! оНцхзрмаци та введшем. П пошуку, ' Mipa агрегутаняя, стиску шформацп та точность sä вщювлення, жпвуисть систем;!, простота структурно! рэоргашзаци. IU та багато tras-tx показнпков в той або mnift t-upi зале;-пть гад тополопчио! структур;! ÜL Пебудова мере.ч з-сг;?к-малышмп показишаки шмт' роботи вводиться до шрошекня задач дкскретноо оптшиэацП на графах. В зь'язку з д»м «еобх!д!ю кати роавпяутий математпчниП апарат теор! S граф!в, який дозволяв би ■ адекватно огшсуватп структуру 1!!, одШсявзам- достагньо прсстий nosyit структур;!, при як!П зобозпечуеться необх!дч1 показкпкп якое-Ii проектуванчя, розвитку i фунгацопування слогом такого роду.

. - А -

Найб1льш яерслзктившм подходом е вккористання структур геодезич-них 1 к-геодезичякх граф^з. Тому дооллдження структурних власти-востей 1 метод1в побудови цих клас!в графив е актуальною звуковою проблемою.

Метою дисертащйно! роботи е вивчення структури геодезичних графдв в терминах 5Х мшмалышх парних простих циклов, створення нових п1дход1Б до породження кових класяв геодезкчних 1 к-гео-дезичних графзв, розробяегам методов перелшення вс1х геодезичних граф1в, гомеоморфяих даному, розробжения мзтодгв пошуку оптимальних структур складних шформацШшх систем, створення методов структурного анал18у випадкових процесш.

Методи дослдження базузоться на ' матештичних. методах комбшаторного анад1зу? теори проектуванкя Ш, матсматичних методах анал1ау та обробки пфрыацп.

Наукова новизна.

1. Розроблено метод дородження вс1х геодезичних графив, гомео-морфних даному.

2. ДосД1д;,еио взаемозв'язок геодезичних грабив 1 грабив 1,!ура.

3. В робота показало, ар' перед!чення бс1х геодезичних граф!в, гомеоморфяил заданому геодеоичноь«у графу вводиться до пере-шчеши всIX ыатуральнкх розз'язкда лш'йко! 'дю^аитово! систем;; р;шянь, яка будиться по задацому геодевпчиому графу.

4. Побудо.вано ефэктивний алгоритм знаходкення вс!х натуральных роза'ЯКК1В'вказаног скстеми р!вкяиь. '

о. установлено взаемозв'язок м 1 лс ер!виова:ченнми нелоснимк блок-схемами та дЕохгеодеаичними Графами.

6. Описано властивссоч кишмалышх парних простих цшшв-геодезичних графив.

7. Описано опткмзльну структуру !нформац!йннх мереж для анализу та обробки гнформацгь

8.' Створено магекатичний шарах для досл!дявння структур кластеров в автоматично! клаеифшацп на основ! теорп геодезичних 1 к-геодезичних граф!в. ■

9. Розв'явана задача 'структурного анализу, шладкових процесс, як!- , описують. акустичт присюрошш судовах уурбогенераюр1в. .

Практична цшис-гь. 1 реал1зац1я .резмьтат1в .гюбот.и,,

Результат« цш дееертаци' момутъ бути вккористш як при доШдгэдн} дшамхки поведщш ададпих комбцшторких о5'ект!в шзвоыаншю! ярироди, так 1 тдчас структурного анализу сладких систем передач!, анализу та обробки шформац}!.' Одержан! теоретич {П! результата ыогсуть бути вккористат на початковому етагп проек-тування ¡нформацШю-обчкслювадъних систем для побудови регулярна, двохрегулпрних геодезичних V двохгеодези^лкх Ш, екстремзль-йих за'критериями вартоет!, над!йност! та прояускко! спрошжност;

^ топологочному р03ум1нн1.

Апробащя роботи. Результати досл!диень допов!далися на нау-кових сем1 нарах кафедри прикладное математики Одеського дер.тавного пол!техн1чного университету, на ПЫй всесоюз'Ий сгаш-семшар! "Комбтаторно-статистичн! методи аналюу 1 обробки ¡нформацп, експертне ошнювання" (10-15 вересня, 1990 р.), на науковьЗ конфе-ренцп молодих вчених ОДПУ ( 1994 р.) 1 на М1.чнародн!й на-уково-практичнШ конференци "Економиш! пробяеки розвитку про-мислового пшриемства" (Одеса, ОДПУ, 3-6 йовтня 1995 р.)

- Публ1кац! 1. За темою дисертацп опубл1ковано п'ять роб1т.

Структура та обсяг дисертацп, Дисерташя включае встуя, 4 глави, висновок 1 додаток, ям зикладен1 на 165 аркушах друко-ваного тексту, список л1тератури включае 85 назв публтацШ.

У встут обгрунтована актуалынсть проблею!, сформульоваш мета 1 задача роботи. Стисло викгздаеться змст дисертацп по главам г приведен! основа результати роботи.

№ряа глава носить оглядсеий характер. В лий зроблено анал1з результатов, як1 описан1 в литератур!. виявлйН1 оснсвн! напрямки досл1джнь геодезичних графив та IX застосуЕання.

У друпй глав1 встановлен1 необххдн! та достатн1 умови усунення негеодезичност1 вс1х пар вершин минимального пгфного простого циклу 1 розглянуто опис геодезичних графгв в тершках 5х структури. При цьому махгсься на уваэ1 властивост! геодезичних граф1В в терминах 1х мшмалышх парних простих цикл!в.

В останньому роздш дано! глави розроблено метод побудови двохгеодезичних графив, породяених , зр!внова,ю=цими неповними блок-схемами (ЗНБС) та дослужена структура таких' графхв.

У треТ1й главг розроблена процедура ", побудови лшйно!. дюфантово! системи р!енянь, яка однозначно визначаеться для'Кох-ного заданого геодезичного графа. Така система була названа системою геодезичних д!офантових р!внянь заданого геодезичного графа.

Доведено, що множина вс1Х натуральних роз в' язшв системи гео^ дезичних д]офантових р!внянь будь-якого геодезичного графа визначае клас всгх геодезичних граф1В, гомэоморфних даному.

Побудовано алгоритм знаходкення вс1х геодезичних . граф!в диаметра 0>=с1, гомеоморфних одному даному графу диаметра <1

Знайдено загальне число геодезичних граф1в, гомеоморфних поеному графу Кп I графу Петерсена.

У четверт!й глав! розглянуто два класи задач: .

1. Побудова складних 1нформац1йних мерея.

2. Розробка метод1в аастосування кластерного анализу для випчання структури . складних • аипадкових процесс, яю

описують в!броакустичн1- прискорення судових турбогенератор iE.

У зак!нченш сформульован1 головн! результата роботи.

: ЗМ1СТ РОБОТИ ""

В будь-яком/ парному простор цикл! будь-яка пара Д1аметраль-но протилежних вершин а'еднана двома найкоротшими простими шляхами, утвореними парою простих ланцюпв цикла однаково! довжини. ^ Парний лростий цикл з точки зору ¿нформащйних мереж приводить до дублшаиня качалiв передач! ¡нформацп.' Якщо необх1дна висока кад1йн!сть Ш, то така структура моке бути крашрю, апе якщо noTpiöao. MiKiMisyBaiH витратк на створення мереж при високШ пропускай спромошост i, то така структура в же не прийнятна. 1снуе можл!в1сть Л1кв1дувати дублгавання каналов, дублювання 1НформацП шляхом введения системи хорд в парний простий цикл. В геодезичному граф1 парний простий цикл'та його система хорд утворюеть мшмаль-ний парний простий цикл. ;'

Розглянуто проблему характеризащ i структура bcix KnaciB reo-, дезичних rpajiв в 1 терм!нах ' мшмальних парних простих циклов граф1в та ix взаемного перетину.

Доведено, .шр для будь-якого n а 1 або 2(mod 3), ' п>-4, !снуе двохгеодезичний блок з пг. вершинами, який мае вершину зв'язшсть, piBHy 3, з шожиною степен1в вершин (n-1,3) i д!аметром 4 або 5.

Доведено; що для кошого пг1 або-2(mod 4). п>»2, .'такого, ,шо п-1 - точний.квадрат, або пяО або 3(irod 4), п>-4, такого, шр п-1 - стел1нь деякого простого' -чисда, юнуе (п+1)-регулярний, (п+1)-зв'язний двохгеодезичний блок дшметра 4.

' ; Побудовако' алгоритм знаходженкя bcix геодезичких -граф!в ' Д1аметра D>»d, гомеоморфних заданому а д1аметром d. BiH'працюе тагам чином:

■• 1. Подати геодезичний граф G у вигляд! об'еднаннякютяка Т э

Рунами вершин 0,1,2.....d та множили ребер, як! можуть з'еднувати •

деяк! паря вершин одного pi вня С Див. рис. 1). .

Х1+Х2 +х4. -Zkx+1 . х2+хЗ +х5 -2kt +1

х4+х5+х6-2кг+1 : -\ xl+x2 +X5+X6-2D+2 ; '-л'

____\ , .• х2+хЗ+х4 +X6-2D+2

^— '^JJ ^ +хЗ+х4+х5 -2D+2 Рис. 1. Граф К4 та його система геодезичних дюфантових р1внянь.

2. Знайти цикломатичний базис,■ який складаеться в простих никл1в непарно! довжини, в^дносно кютяка Т i знайти.bci парнг jipocTl цикли графа G довжини 4,6.....2d+2.

3. Побудувати систему лшйних дюфантових р1внянь гео-дезичного графа як1 визначають вс1 прост! цикли пункта 2 1 вмзначити гранищ IX в!льних член1в. .

4. Знайти вс1 моилив! значения вектора в!льних члена системи д1офантових р1внянь геодезичного графа в.

5. Розв'язати систему для кожного з набор1в значень.

6. Вибрати Т1 розв'язки системи дюфантових р^внянь геодезичного графа Б, як1 е натуральними.

7. На основ! цкх розв'язк1в побудувати вс! геодез!чн1 графи, гомеоморфа задакому геодезичному графу б. ■ . ' '

8. Якщо потр!бно знайти вс1 геодезичн: графи, гомеоморфа да-ному, для 1ншого ф1ксованого значения Б, то перейти до пункту 4.

Доведено, шр число всгх геодезичних графив д1аметра с1, гомео-шрфних повному графу К4, дор^внюе ,

а число вс1х теодезичних графив д1аметра <1, гомеоморфних графу Пе-терсена, дор1внюе [с!+3\. • - •

I 5 I . '

На рис. 2 показан! чотири геодезичних графи Д1аметраш 6=2,3,4,5, томеоморфна графу Петерсена 1 побудован! 'за допомогою

У робот1 вперие доведено, до задача вибору оптимально! струк-?ури складних Шформащйних систем; . екстремальних за параметрами 6а,ртост1, 'пропускное спроможост! та над1йност1 в тополог1Чному розумпни, вводиться до задачх дискретно!, опттлзацп на мнокинах геддезичних 1 двохгеодезичних граф!в.

Розглянемо основш положения та визначення топологи . |М, як! грунтукться на теорп графив. »

Поставимо у в1дпов!дн!сть 1М звичайний неор1ентоваиий граф Б=(\',Е), де мнокина верном V в1дпов1дае вузлам мереж!, а мюхина ребер Е - каналам зв'язку. Позначкмо число вершин графа й через п—1VI, число ребер - через п-|Е|. Граф називаеться регулярним сте-пеня к, яги-до с!ее(у)-к для вс!х вериин графа.

Задача псбудови регуляриих 1 двохрегулярних керек э гадашш ц1амзтром <1 '. 1 числом вузл!в п. мзз 'ваяливе значения-на по-чатковсму стал! проектувапня 1)1 В1доко, цо при гаданому д|амзтр! •

- а -

с] 1 числ! верпш п Ш мае висок? над1йн!сть при мшмальному чиод» каналов з'вязку (ер мииы^ауе витрати на створення мерели) у випадку, коли граф, в1дповшшй до марели, буде регулярним. Проте, через те шр не для вснх п '1 сГ можливо побудувати од-нор! дний граф при миамальному числ! ребер, то мереж! високого р^вня над!йност! кеобх1дно шукати серед двохрегулярних по вузлам двохгеодезичних мерек, частина вузл1в яко! пс мае степень к, а ¡ни пл вузл!в - стешнь к+1.

Лропускна спромоаапсть мереж! визначаеться максимальним потоком пов1домлень, якмй мо-тй бути орган130ваний м!ж п вузлами. Показано, що. при ршпй пропускн1Й спромомюст! вузл1в 1 ребер (вузл1в комутацп повхдомлень 1 лШй эв'язку) пропускна снроможнють мере,гл обернено пропортйна середшй вддсташ мш и вузлами. Тому керехи максимально! пропускно! спроможност! - це мерек! м1н!мальио мокдивого диаметру. Ери тополог¿чному проекту-вант нас ткавлять мережа, екстремалый по кр1тер!ям вартост1 над1йност! та пропускно5 спромоглост1, тому нас будуть в першу чергу щкавити регулярна двохрегулярш двохгеодезичн! мерели м1н!мально можливого д1аметра.

Розглянуто використовування асимптотично! ошнки продук-тивнють-варпсть для вибору тополог1чно! структури Ш Анал!з проведено для таких конф^гурашй, як мапстраль повн1 графи, подвши К1льця, К1ль«я а хордами. Вартють Ш визначаеться варпстю вузл1в 1 вартютю лшй эв'язку. Гополопчн! структури, нами розглянуп, приведет ня пип. а.

Рис. 3. Тополог 1ЧН1 структури, як! використовувались для анал1зу характеристики продуктиБНЮть-вартють: а) сшльна шина п-4; б) повний граф п-4; в) подвШне к!льце; г) к ¿льде а хордами.

Рис. 4. Задезкнютьас-ПМ), Н-юлькють вуел^в тополог¡чжя структури: 1-сгидьна шина; 2-повний граф; 3-подв1йне шльце; 4-1« льде а хордами.

«ГШ

О)

Розрахопана асимпготичка продуктивность дда щм структур. Результата цих розрахунмв представлен! на рис.4.

Основною к!льк!сною характеристикою над!йностх е P(t), яка визначаеться iMOBipnicTio безв^дмовно! роботи системи, тобто iMOBipniCTjo того, що при заданих режимах i умовах експлуатац!! протягом заданого часу роботи системи вхдмова в не! не виникае (BiflMOBa -П0Д1Я, яка полягае у noBHift або. частковШ утратi праце-здатност! системи)

Pit) - PiT>t>,

де Т -напрацювання на в1дмову системи; t -заданий час; РШ -¡мо-BipniCTb поди А (у даному випадку под^я А полягае в тому, шр T>t).

По аналог!I з функщега над!йност! ."введемо функцш не-над1йност1 (iMOEipHicTb вимови) Q(t)=P-tT<»th

Б1дпов!дно визначення функц1й PCt) i Q(t) отримуемо

P( t) +Q( t) -1 або P(t)-1-Q(t). Якщо заданий час t дов1льний, то P-l-Q. 3 останньо! piBHOCTi випливае, що Mipoio Р може бути Q: 4iM вище значения Q, тим ripuie надШисть системи.

гйлькюно надШпсть мереж! визначаеться икшртстю зруйну-вання sB'HSKiB Mix Еузлами мерелй, якщо в!дом1 iMOBipiiocTi вддмов лШй зв'язку та вузл^в комутацп. При тополоПчному проектуванн! мереж звичайно вважати, що. в1дмови яких-небудь вузл1в i ребер е незалежн! випадков! поди, якГ характер!зукггься однаковими для бсix вузл!в (ql) i ребер (q2) -хмовгрностями появления. Ягацо при цих припущеннях ОбЧИСЛЯТИ iMOBipHOCTi Qij.BiflMOBH зв'язку MiÄ вузлами мереян 1,j»i,...,п, то над1йн1сть мерел1 можливо визначити виразом Q - max Qij . ' .'..■'/■' Не хай дана [n, ml-мережа (ro-n+L), частина вувл1в яко! п„ мае сте-гпнь k, a iHEii rij вуал1в - стешнь к+1. Досл1дзкно характер залежнос-Ti iMOBipHOCTi в1дшеи таких двохрегулярних tn.n+Ll-мереж biд величи-ни L. Доведено, щэ при L-0 Q2 е величина порядку q2*q2(n*n/4), а тому Q2(0) "--Ol q2*q2(n*n/4)). При L*1 Q2( 1) -0(S*n*n*?2»i}2/36). При L«n iMO-BipHicTb Biдмови оцйиоеться по формул! •

Q2( L) ->0( 2*n*n*q2*q2/( 36*L*L)). При L=n/5 Q£(n/5)=0(2*q2*q2), i такий гГорядок iMOBipHOCTi вiдмови мерели залишаеться поки l-n/2, де вона стрибком приймае значения Q2(n/2)-0(2-«|2*q2). Для L-n/2, k-[ 2( n+L)/п]-3. .

.Ц-d.ni ми маемо, up Q2( in/2)-0(2qUi ), для l<-i<«n-3. Зм1на функцп Q2(L) Mix стрибками в точках n/5, n/4,n/3,n/2 не так noMiTHa. На початку змти L в!д 0 до n/Б фушедя Q2(L) змень-шуетьея в n*rc/8 pasiB. Де лояснюе чутлившть до smihh' тополог!i

мереж багатьс/ еврхстичиик методхв пошуку екстремальних за-надШпстю 1 вартхстю 1М, якх прадюють якраз у 'цьому дхапазонх змхни Ь (рис. 5).

0*1

Рис. 5. Функцхя зм1ни надхйностх.

Зб1льшекня 1_ приводить до эб!льшення додаткових витрат на ор-ганхзацхю мережх.. Якщо збхльшення Ь не встигае за темпами збхлыден-ня п, тобто.ягацо при -.збишшенШ числа вузлхв в мере»1 зменьшуеться А(п,Ц= 61/п, де 6 =С2/С1, С1 -варгхсть вузла, С2 -вартх'сть каналу зв'язку, то п/Ь при цьому зростае. Вхдповхдно буде зростати хмов1р-нхсть вхдмови мережх. Еконбм1я засобхв приводить до поПршення тех-нхчних характеристик оптимальних систем. Але для двохрегулярних геодезичних мереж, гомеоморфних графу Петерсена з дхаметрами (1=2,3, 4,5, якх показан! на рис. 2, отримайо, що для п=10,15,20,25 мае мхсце р1ЕН1СТЬ Ь=п/2=-п/3=п/4=п/5=5=сопз1, а тому Ь/п зменшуеться при збхлыпеннх Ь, що приводить до економхг засобхв, але при цьому мереж! абер!гають високий р1вень над1йност1. У таблиЦх 1 показано параметри над1йност! та вхдноснох додатково! вартостх для вказа-них мереж, для п/5<=и-п/3., Ь=С<п-2Ь)/31].,

' ' . ' ■ ■ ' Таблица 1.*

Дхаметр Число вузлхв • Бадхйшсть • В1дн. додат. вартхеть

2 10 0.69 6/2 .

3 15 0.99 .. ¿/з ■

4 ' • 20 0.99 : . 6/ 4

5 0.99 ¿/5

Якшр при зб1льшекн1 п пхдтримувати постШними додатков1 витрати А( то. регулярн! мерекх з великим числом вуал1 в 1 великим

р1вном надхйностх е регулярном двохгеодезичними або трьохгеодезич-ними мережами.' Прикладами таких двохгеодезичних мереж е регулярн!

- и - ...

мереж!, як! побудовано нами у'друг!й глав! га допоксгою ЗНЕС. Для трьохгеодеаично! мереж!, зображено! на рис. б,. n-32, m-n+L-32+16,■ a L-n/2. В цьому випадку справедливо Q2(n/2)=0(2*c!*q).

На рис. 7 показана схема Ш Одеського пол!техн!чногб**ун!верси-тету. Ш ОДПУ мае деревовидно-шинну структуру в 32 вершинами ! д!а-метром d=4. З.граф!ку, показаного на рис.4, видно, ер вона мае б1льш низький р!вень продуктивности hik 1нш! ровглянутi структурк, хоча й менш дорога. Тому, з тополопчно'! точки вору, крас» було би органi-зувати а у вигляд1 регулярной трьохгеодезичко* мереж! з 32 вершина-., ми i д!аметром d-4, яка показана ка рис. 6. очевидно, щр ьона мае ви» сокий ревень над1йиост1 з в!дносно невисокою вартютю (див. табл. 2),

Рис. 6. Регулярна трьохгеодеэична мерезга д1аметром d-4. ■ '

■ : ■ Таблица 2.

Параметри , . ; ш одпу • , Пропонуемий вар!ант

Число вузл1в ■ '■■К - 32

Число канал!в. . 48

Д!аметр ; ; 4

Вартють 16(2*01+02) 16(2*01+3*02)

Продуктивнють 1/(3*5п)" 2/( 5*Sn)

Еад!йн1сть: 0. 999132

Sn - 1нтервал часу, на протяз! якого Л1нп вв'язку зайнят1 noBi-ом.1. "нями.

У робот! створено математичний апарат для досд!дження стру^ ур кластер!в на ochobi георп геодезичних i k-геодезичних граф!r Задача автоматично i класиф!кацп вводиться до розбиття мне

■ /600/ (r+w)/2 , 3Com /360/ e2000

кини кластеров на гпдмножши, як! не леретинакчьея, яри у.мов1, що кластеры, як1 налегать р1зним класам тек но перетияаються.

Виршення задач! структурного анал1зу кластер1в в значн1Й М1 р1 залегать в1д зшстового значения поняття мастера такого фор-мал!зацп. Найбьтыл зм^стово зрозумияэ та легко формализуете поняття будуеться на основ! теорп максимальнпх повних граф!в. або граф1В гомеоморфних 1м.

Нехап. В={В1,... ,Вк> - мнокяна об'екпв, як! гидлягають ¡иаси-ф1кац11, коншй з яких описуеться в деякому п-вишрному просторь Нехай задана матриця

попарнах в!деталей шж об'ектама шжшя В. Елберемо делкий поо1г 6 >0 ! побудуемо матрицю 0г, •елементаш -ягах е 1 ! 0-в!дпов!дно до правила

(1, якщо сИз<= $ ;

'Л] - 4

[о, в 1пго».у випадку. Матрица е матриця сум!:.зюст! дзякого графа '

Розгляномо падачу гокрнття графа п5 пори'Г'и робэр::о-пояг-ретпяаз';:::.:::^! шдгр&'аии. Та;: як чло-ча г"р!в:;т!в пскапття мае порядок ОГЕ'1), то впитае проблема зиберу нзнкра^зго гер^анту искриста. для цього розницею функглопол

де г'5(уу) - ьагова.фуйкц1я, ар задана' па шошп ресер повного графа Кз, 1 -Шлыасть негюретпиаючпхея повних шдграфГв графа 6(У<-, Е/).

Будеко розгдядатя всю р!'зистн!та!схь.Р вар^шшв покрпття иовними реберно-иеперетинавчшися п!дграфа^х -СК1,... ,Кз>. 3 ус!х вар!ант>в покрцття виберемо той, на якочу функщонал прпймае найб!льш значения. икогш вершш повних Шдграф^Б, як!, входять у покриттз б(У,,Ег), максимюуючэ Фувкцюнад будемо називати ба-8овою системою кластер!в. р!вня о. В результата макс;;м1зацп Функщокала при задапому значенн! одэрауемо мнохину повних' гпдгр-аф^з, мнохшш верзш яких утворшгь розбиття шожгаш сб'еклчв {В1,...,Вк} на шдшояши. Так!. шдмномнш е кластери. .

Одерг-ли! теореткчн!. рэзультати були • використан! • для класифигацп стан!в , часовпх ряд!в,. як! описуоть вкустичн! прискорення судових турбогенератор!з.'

У вияадку великих масив1в данях IX стохастична залэжн!сть описуеться ыатр;щш1 г.од!бносп . або • бжаьксст! велико' росм!рност1. Одшеи г задач кластерного апаизу тагах.матрицъ вивчання !х структури . У робот! -докедеко, с;о структура адекват) описуеться геодезичнгят графам.

■ ЗАКЛЮЧЕНИЯ

Оеновн1 результата, як1 отриман1 в писерташтпй роГтОть

1. Створено метод породження всох геодезичних графов, го-месморфнкх даному.

2. Дослужено взаемозв'язок геодезичних граф!в 1 грабив

Мура.

, 3. Приведено достатн! умови геодезичност! графив, гомео-морфних графам Мура.

4. Показано, и;о передочення вс!х геодезичних граф!в, гомеоморфних заданому геодезичному графу, вводиться до пе-релхчення во1х катуральних розв'язк1в ' .шийно* дюфантово! спстеми р!внянь,' яка будуеться по эаданому геодезичному графу.

5. Дослхджено взаемозв'язок м!» лхшйними ' доофанто-вими скстекзш р!внянь геодезичних графов та графами Мура.

6. Побудовано ефективклй алгоритм знаходженкя всох натуральна: роЕв'язков вказано! сиотеми р!внянь.

7. Створено_ алгоритм зааходжевня вс1х геодезичних графов д!аметра . 1Э>—<3,' гомеоморфних заданому геодезичному графу дхамэтра (1.

8. Знайдено загадъне число геодезичних .граф!в, гомеоморфакх повкому графу о графу Пе-терсена.

9. Естановлеко вземовв'язок' мой врх'вноваженими неповнимп блок-схемами о двохгеодезпчними графами.

10. Остановлено необхлДгИ 'та достатно умови лхквхдацп не-геодезичностх всхх пар вершин мономального парного простого цшслу.

.И. Розглянуто окис геодезкчних' графив в терминах !х структур;;. При цьому мазться на усазо властивост.о геодезичних графов у терминах мушш&шгс парик простих циклХв.

12. £ослшзио. застооуванкя ;•;-геодезичних графов для про-октуьаннл хнфэрмацп;:;;;;: '¡.ера;.;, яко макмь вкеок! параметр;; нкосхх 1х робот;;.-- •

• 13. Закропоноваио. яовий г.ор!иит побудови онформзцхйно! мер к» 0)Ш у ьпглядо ?;)юхрогулярпо1 трьохгеодезично!- мэрек1, яка мае вксок1 норамотрл надхшюсто та продуктглнсст! при не велики"; в1дйосн1й • дод-^гковой ьартост!.

14. Ероблоно . пласифокацхв .стать часових ряд1в, якх спксують дппамхку ;змШ1 значень параметров робот;; еудових ' турбогенератор! в за до.помогоэ гсорп геодезичних граф!в.

Основний змют яисертацп в1добрялгено у .таких публ1кашяхи

1. Еостров Г. 11, Фрассер К. Блок-схемы, геодезические графы и автоматическая классификация // Тези допов1дей Ш-о! всесоюзно! шоли-семшару "Кокб1наторко-статисти'Ш1 ¡.<етоди анал1зу'та обробки шформацН, експсртне ощнюзалня". - Одеса: ОДПУ, 1990. -с. 84.

2. Фрассер К. Оптимальные' структуры ин^рмацтгонимх систем в области анализа и обработки сощ^ально-экокомической информации // Тези наувово-практично! конференцп молодих вчених. - Одеса: ОДПУ, 1994. -с. 44-45..

3.' Еостров Г. Е , Фрассер К. Геодезические графы и информационные сети // Тези допов1дей »л «народног .науково-прак-тичной конференцП "Екожшчш проблеют розвитку промисдового виробництва". - Одеса: ОДПУ, 1995. -с. 152-153.

4. Бостров Г. Е , Фрассер К. О породязнпи и перечислении некоторых классов геодезических графов. - Одеса: ОДПУ, 1895. -Деп. у ДНТБ УкраЧнп 05. 07. 95, Ко. 1663 -Ук95.

5. Востроп Г. Е , 'Грассор К Улрактсригглпя геодезичесгаге графов. - Одеса: ОДПУ, 1995. -Деп. у ДКТВ Украпга-05.07.95, Но. 1664 -Ук95. ' •

Аннотация

Фрассер Санчес К. Э. Разработка математического и алгоритма геского обеспечения, обработки' информации на основе структурного шализа геодезических графов. ■Диссертация на соискание-ученой стегани кандидата технических наук по специальности 05.13.04 - Автоматизированные системы управления к системы обработки информации, )десский государственный политехнический университет, Одесса, 1996.

Целью диссертационной работы является изучение структуры. геодезических графов в терминах их мшшм&шшх четных простых циклов, юздание новых подходов к- порождению новых.икассов геодезических и ;вухгеодезичес1шх графов, разработка методов перечисления Есех геодезических графов, ' гоиеоморфньк любому .заданному геодезическому рафу, структурный анализ сложных скстеу передачи, анализа и обра-, отки информации на основе теории геодезических графов. Исследовано рименение теории к-геодезических графов для проектирования инфор-ациокных сетей.и анализа случайных процессов, разработан алгоритм остроения геодезических информационных: сетей,- экстремальных по араметрам стоимости, надежности й .пропускной 'способности в топо-огическом смысле. .

Abstract

Frasssr Sanchez С. E, Elabox^atlon of Mathematical and algorithmic methods of' information processing based on the structural analysis of geodetic graphs. The theses . for applying for PhD's degree on the speciality 05.13.04 Automated Control Systems and Information . Processing Systems, Odessa State Polytechnic University, 1996.

The goals of the dissertation work are to research the structural description of geodetic graphs in terms of their minimal even circuits, establish a new approach to the problem of constructing new classes of geodetic and bigeodetic graphs, elaborate enumeration methods of geodetic graphs which are homeomorphic to a given one, perform the structural analysis of information transmission complex systems and information processing systems based on geodetic graph theory. k-Geodetic graph theory is used to construct inexpensive information networks of higher security and higher speed of Information transmission in the topological sense.

KJE040B1 СЛОВА

Геодезичний граф, дюфантова система, ЗНБС, Ш, алгоритм, кластер.

Шдписано до друку «¿Л.ио.Уо. 4'ормат 0Uxb4/lb.iIanlp газетнии. Друк офсеткий.0,93 ум.друк.арк., 1,00 обл.-вид.арк. Тираж 100-прим. Замовлення