Kpi.ua



НАЦ?ОНАЛЬНИЙ ТЕХН?ЧНИЙ УН?ВЕРСИТЕТ УКРА?НИ?КИ?ВСЬКИЙ ПОЛ?ТЕХН?ЧНИЙ ?НСТИТУТ ?мен? ?ГОРЯ С?КОРСЬКОГО??НСТИТУТ ПРИКЛАДНОГО СИСТЕМНОГО АНАЛ?ЗУКАФЕДРА МАТЕМАТИЧНИХ МЕТОД?В СИСТЕМНОГО АНАЛ?ЗУ?До захисту допущено?В.О. Зав?дувача кафедри__________ О.Л. Тимощук“___”_____________20__ р.Дипломна роботана здобуття ступеня бакалавраз? спец?альност? 6.040303 Системний анал?зна тему: ?Задача пошуку шлях?в з використанням спектрально? теор?? граф?в?Виконала: студентка IV курсу, групи КА-53Шульженко Яна Олег?вна Кер?вник:доцент, к.ф-м.нСтусь О. В. Консультантз економ?чного розд?лу:доцент, к.е.н. Шевчук О. А. Консультантз нормоконтролю:доцент, к.т.н. Коваленко А. ?. Рецензент: Засв?дчую, що у ц?й дипломн?й робот? нема? запозичень з праць ?нших автор?в без в?дпов?дних посилань.Студентка _____________Ки?в – 2019 рокуНац?ональний техн?чний ун?верситет Укра?ни?Ки?вський пол?техн?чний ?нститут ?мен? ?горя С?корського??нститут прикладного системного анал?зуКафедра математичних метод?в системного анал?зуР?вень вищо? осв?ти – перший (бакалаврський)Спец?альн?сть (спец?ал?зац?я) – 6.040303 Системний анал?з (Системи ? методи прийняття р?шень)ЗАТВЕРДЖУЮВ.О. Зав?дувача кафедри__________ О.Л. Тимощук ?___?_____________20__ р.ЗАВДАННЯна дипломний роботу студентуШульженко Ян? Олег?вн?1. Тема роботи ?Задача пошуку шлях?в з використанням спектрально? теор?? граф?в?, кер?вник роботи Стусь Олександр В?кторович к.ф-м.н., доцент,затверджен? наказом по ун?верситету в?д ?___?_________ 20__ р. №_____2. Терм?н подання студентом роботи 3. Вих?дн? дан? до роботи 4. Зм?ст (дипломно? роботи) розрахунково-пояснювально? записки (перел?к завдань, як? потр?бно розробити)5. Перел?к граф?чного (?люстративного) матер?алу (з точним зазначенням обов’язкових кресленик?в, плакат?в, презентац?й тощо) 6. Консультанти розд?л?в проекту (роботи)Розд?лПр?звище, ?н?ц?али та посада консультантаП?дпис, датазавдання видавзавданняприйняв7. Дата видач? завдання Календарний план№ з/пНазва етап?в виконання дипломно? роботиТерм?н виконання етап?в роботиПрим?ткаСтудентка ________________________________(п?дпис)(?н?ц?али, пр?звище)Кер?вник проекту (роботи)________________________________(п?дпис)(?н?ц?али, пр?звище)РЕФЕРАТДипломна робота м?стить: 80 с., 6 табл., 30 рис., 2 дод. та 20 джерел. ОР??НТОВНИЙ, НЕОР??НТОВНИЙ ГРАФ, СПЕКТР, МАТРИЦЯ СУМ?ЖНОСТ?, ШЛЯХ, ДОВЖИНА ШЛЯХУ.Задача пошуку шлях?в ? дуже важливою у нашому житт?. Метою дано? роботи ? створення програмного продукту, який буде обчислювати к?льк?сть шлях?в ф?ксовано? довжини. Для розв’язку дано? задач? використову?ться спектральна теор?я граф?в. Об’?ктом досл?дження ? шляхи у граф?. Предметом досл?дження ? спектральна теор?я граф?в.Для наочного прикладу актуальност? дано? задач?, було сформульовано та розв’язано задачу пошуку маршруту з м?н?мальною к?льк?стю пересадок. В якост? графа виступа? схема low-cost ав?ал?н?й, де вершини графа – це м?ста, а ребра – шляхи сполучень м?ж м?стами. Для подальшого досл?дження ? вдосконалення дано? роботи можливо добавити до вх?дних даних ц?ни б?лет?в або час польоту ? тривал?сть перебування у м?ст? пересадки, щоб знайти не т?льки шлях з м?н?мальною к?льк?стю пересадок, а й найдешевший ? найшвидший вар?анти польоту. ABSTRACTThesis contains: 80 p., 6 tables, 30 fig., 2 add. and 20 references.ORIENTAL, UNIONED GRAPH, SPECTRUM, MATRIX OF COMPATIBILITY, WAYS, LENGTH OF A WAY.The theme: “The problem of finding paths with using spectral graph theory”.The task of finding ways is very important in our lives. The purpose of this work is to create a software product that will calculate the number of paths of fixed length. For the solution of this problem, the spectral theory of graphs is used. The object of the study is the paths in the graph. The subject of the study is the spectral theory of graphs.For a clear example of the relevance of this task, the problem of finding a route with the minimum number of transplants was formulated and solved. As a graph, the scheme is low-cost airlines, where the top of the graph - is the city, and ribs - the routes of connections between cities.For further research and improvement of this work, it is possible to add to the input data the price of the tickets or the flight time and the duration of stay in the city of the transfer, in order to find not only the path with the minimum number of transmissions, but also the cheapest and fastest variants of the flight.ЗМ?СТ TOC \o "1-3" \h \z \u ВСТУП PAGEREF _Toc11021737 \h 8РОЗД?Л 1 ТЕОРЕТИЧН? ОСНОВИ ЗАДАЧУ ПОШУКУ ШЛЯХ?В М?Ж ВЕРШИНАМИ ГРАФА ТА ПОНЯТТЯ СПЕКТРУ ГРАФА PAGEREF _Toc11021738 \h 101.1Задача пошуку м?н?мальних в?дстаней PAGEREF _Toc11021739 \h 101.1.1 Деяк? способи знаходження маршрут?в у граф?. PAGEREF _Toc11021740 \h 121.2 Спектри граф?в ? основн? визначення PAGEREF _Toc11021741 \h 171.3 Операц?? над графами PAGEREF _Toc11021742 \h 201.4 Висновки до розд?лу PAGEREF _Toc11021743 \h 21РОЗД?Л 2 ПОШУК МАРШРУТ?В ЗА ДОПОМОГОЮ СПЕКТРАЛЬНО? ТЕОР?? ГРАФ?В PAGEREF _Toc11021744 \h 222.1 Про к?льк?сть маршрут?в PAGEREF _Toc11021745 \h 222.2 Перетворення граф?в ? к?льк?сть маршрут?в PAGEREF _Toc11021746 \h 252.3 Використання у комб?наториц? PAGEREF _Toc11021747 \h 272.4 Висновки за розд?лом PAGEREF _Toc11021748 \h 32РОЗД?Л 3 РОЗРОБКА ПРОГРАМНОГО ПРОДУКТУ ПОШУКУ К?ЛЬКОСТ? ШЛЯХ?В ДОВЖИНИ PAGEREF _Toc11021749 \h 333.1 Дан? для роботи PAGEREF _Toc11021750 \h 333.2 Опис програми PAGEREF _Toc11021751 \h 343.3 Практичне застосування PAGEREF _Toc11021752 \h 373.4 Висновки до розд?лу PAGEREF _Toc11021753 \h 44РОЗД?Л 4 ФУНКЦ?ОНАЛЬНО-ВАРТ?СНИЙ АНАЛ?З PAGEREF _Toc11021754 \h 454.1 Постановка задач? техн?ко-економ?чного анал?зу PAGEREF _Toc11021755 \h 464.1.1Об?рунтування функц?й програмного продукту PAGEREF _Toc11021756 \h 474.1.2Вар?анти реал?зац?? основних функц?й PAGEREF _Toc11021757 \h 474.2 Об?рунтування системи параметр?в програмного продукту PAGEREF _Toc11021758 \h 494.2.1 Опис параметр?в PAGEREF _Toc11021759 \h 494.2.2 К?льк?сна оц?нка параметр?в PAGEREF _Toc11021760 \h 504.2.3 Анал?з експертного оц?нювання параметр?в PAGEREF _Toc11021761 \h 52ВИСНОВОК PAGEREF _Toc11021762 \h 64ПЕРЕЛ?К ПОСИЛАНЬ PAGEREF _Toc11021763 \h 65ДОДАТОК А Л?СТИНГ ПРОГРАМНОГО ПРОДУКТУ PAGEREF _Toc11021764 \h 67ДОДАТОК Б ПРЕЗЕНТАЦ?Я ДИПЛОМНО? РОБОТИ PAGEREF _Toc11021765 \h 71ВСТУПГрафи ? важливою складовою майже у вс?х областях математики. За допомогою граф?в можна зручно представити вза?мозв’язок м?ж елементами р?зноман?тних складних систем. Теор?я граф?в ма? велике практичне застосування та використову?ться в таких сферах як:?нформатика та програмування (блок-схема програми); б?олог??;х?м?я (описання структур, складних реакц?й, молекулярн? графи);ф?зика (печатн? схеми, будова кристал?чно? реш?тки);у теор?? планування та управл?ння (задач? представляють у вигляд? граф?в, що допомага? вир?шити до якого м?сця треба д?йти, ? який шлях до нього обрати);у математичн?й л?нгв?стиц? тощо. Теор?я граф?в активно використову?ться для вир?шення задач у сфер? телекомун?кац?й. Оск?льки кожна мережа може бути представлена у вигляд? графа – зваженого або незваженого, ор??нтовного або неор??нтовного – теор?я граф?в може використовуватися для пошуку шлях?в у мереж?. З часом, коли мереж? становилися все б?льше та складн?ше, задача пошуку м?н?мальних в?дстаней набувала сво?? популярност?. Найб?льш наглядним прикладом використання граф?в ? комун?кац?йн? ? транспортн? системи, а також маршрутизац?я даних в ?нтернет?. Наприклад, схема метропол?тену, вершинами графа ? станц?? метро, а ребрами – л?н?? м?ж ними. Таку ж структуру мають схеми ав?ал?н?й, карти дор?г або руху морських суден. Застосування математичного апарату до таких граф?в дозволя? знайти найкоротший шлях, оптим?зувати маршрут транспортного руху.Пересування у великих м?стах зазвичай займа? багато часу, тому виника? необх?дн?сть оптим?зац?? маршрут?в. У цьому й поляга? актуальн?сть задач? пошуку шлях?в.У робот? задача пошуку шлях?в вир?шу?ться з використанням спектрально? теор?? граф?в. Спектральна теор?я граф?в з’явилася в результат? застосування л?н?йно? алгебри до теор?? граф?в. РОЗД?Л 1 ТЕОРЕТИЧН? ОСНОВИ ЗАДАЧУ ПОШУКУ ШЛЯХ?В М?Ж ВЕРШИНАМИ ГРАФА ТА ПОНЯТТЯ СПЕКТРУ ГРАФАЗадача пошуку м?н?мальних в?дстанейТеор?я граф?в – це, в к?нц?-к?нц?в, вивчення в?дношень. Враховуючи наб?р вузл?в ? з’?днань, як? можуть абстрагувати все що завгодно, в?д макет?в м?ст до комп’ютерних даних. Теор?я граф?в представля? корисний ?нструмент для к?льк?сно? оц?нки та спрощення багатьох рухомих частин динам?чних систем.У програмн?й ?нженер?? графи в?дом? як довол? розповсюджена структура даних, названа деревами р?шень. У св?т? електротехн?ки ц?ла дисципл?на оберта?ться навколо створення, розрахунку й обслуговування багатокомпонентних електричних ланцюг?в – часто побудованих на д?аграмах, дотримуючись принцип?в теор?? граф?в. Тим часом в област? молекулярно? б?олог?? вчен? екстраполюють модел? прогнозування для в?дстеження розповсюдження захворювань або моделей розмноження. А в суперечливому св?т? анал?зу соц?альних мереж ми явля?мося св?дками теор?? граф?в, яку використовують для стандартних функц?й, таких як ступен? розд?лення ? рекомендац?? друз?в в Facebook.Означення. Граф G(V,E) – це ск?нченна непорожня множина V вершин сум?сно з ск?нченною множиною E ор??нтованих чи неор??нтованих ребер, що з’?днують деяк? пари вершин. Ребра, що з’?днують одну й ту саму вершину, називають петлями. Ребра, що з’?днують одну й ту саму пару вершин, називають мультиребрами [1]. Приклад зображення графа наведено на рисунку 1.1.Рисунок 1.1 - Простий граф, повний графВиди граф?в: простий (не м?стить мультиребер та петель);мультиграф (допускаються мультиребра та петл?);ор??нтовний або орграф (ус? ребра ор??нтовн?);неор??нтовний (ус? ребра неор??нтовн?);зм?шаний (зустр?чаються ор??нтовн? ? неор??нтовн? ребра);зв’язний (м?ж будь-якою парою вершин ?сную хоча б один шлях);повний (будь-як? дв? вершини з’?днан? ребром);зважений (кожному ребру графа в?дпов?да? деяке число, яке назива?ться вагою ребра);Вершини позначатимемо л?терою v, ребра – л?терою e.Важливим числом, яке зв’язано з кожною вершиною графа, явля?ться ?? степ?нь, яка визнача?ться числом ребер, що входять або виходять ?з не?. Наприклад, ус? вершини графу, що зображен? на рис 1. мають степ?нь 2, тод? як вершини повного графа на рис 2. мають степ?нь 3. Знання к?лькост? вершин у повному граф? характеризу? його ?стотну природу. З ц??? ж причини повн? графи зазвичай позначають Kn, де n – число вершин, ? вс? вершини графу мають степ?нь n – 1. Означення. Нехай задано граф G(V,E). Якщо вершини v1 та v2 з’?днан? одним ребром e∈E, то вершини v1 та v2 ? сум?жними. Тод? вершини v1 та v2 ?нцидентн? ребру е, а ребро е ?нцедентне вершинам v1 та v2 [2].Маршрутом назива?ться будь-яка посл?довн?сть прямуючих один за одним ребер мультиграфа або мультиорграфа у напрямку ?х ор??нтац??. Довжина маршруту – це к?льк?сть йог ребер. Маршрут назива?ться замкненим, якщо v1=v2. Вершини маршруту не обов’язково р?зн?. Окр?м цього, ребра, по яким проходить маршрут, також не обов’язково мають бути р?зними.Шляхом у неор??нтовному граф?, що почина?ться у вершин? v1 ? зак?нчу?ться у вершин? v2, називають посл?довн?сть вершин та ребер вигляду v1ei1vi1ei2vi2ei3…vin-1einv2, де кожне ребро ?нцидентне обом вершинам, як? ? для нього сус?дн?ми в посл?довност?. Для орграф?в шлях визнача?ться з урахуванням посл?довност? ребер [1]. Простий шлях – це шлях, що не м?стить повторень вершин ? ребер.Циклом назива?ться замкнений шлях, тобто v1=v2. Простий цикл – це простий замкнений шлях.1.1.1 Деяк? способи знаходження маршрут?в у граф?. Задача пошуку маршрут?в ма? довгу ?стор?ю ? вважа?ться одн??ю з класичних проблем у теор?? граф?в. Перш? досл?дження проводились ще у 19 стол?тт?. Задача набула популярност? на початку 50-х рок?в минулого стол?ття у контекст? альтернативно? маршрутизац??, тобто пошуку другого м?н?мального маршруту, якщо перший такий маршрут заблоковано.?сну? багато р?зноман?тних формулювань задач? про пошук маршрут?в у граф?. Одн??ю з найважлив?ших ? задача пошуку м?н?мально? в?дстан? м?ж двома вершинами зваженого графу, тобто необх?дно знайти найкоротший шлях з найменшою сумою ваг ребер.Актуальн?сть ц??? задач? п?дтверджу? ?? обширне застосування у реальному житт?. Прикладом може бути нав?гатор у вашому смартфон?. Користувач вказу? сво? м?сцезнаходження та пункт призначення – це вершини графу, а дороги м?ж ними – ребрами. Нав?гатор обчислю? суму довжин дор?г м?ж пунктами, якщо сума найменша, то знайдено найкоротший шлях.Розглянемо основн? методи пошуку м?н?мального маршруту у зваженому граф?.Алгоритм Беллмана-Форда. Знаходить найкоротш? шляхи з одн??? вершини зваженого графа до вс?х ?нших, при цьому вага ребер може бути в?д’?мною, але нема? бути цикл?в з в?д’?мною сумою ваг ребер (якщо в граф? ? в?д’?мний цикл, то може ?снувати незм?рно короткий шлях, оск?льки при кожному проход? циклу зменшу?ться довжина шляху).Алгоритм Флойда-Уоршелла. Знаходить найкоротш? шляхи м?ж ус?ма вершинами зваженого ор??нтовного графа. Ваги можуть бути в?д’?мними, але нема? бути цикл?в з в?д’?мною сумою ваг ребер.Хвильовий алгоритм (Алгоритм Л?). Знаходить шлях м?ж двома заданими вершинами графа, який м?стить найменшу к?льк?сть пром?жних вершин.Алгоритм Джонсона. Знаходить найкоротш? шляхи м?ж ус?ма парами вершин зваженого ор??нтовного графа, при цьому повинн? бути в?дсутн?ми цикли з в?д’?мною вагою.Алгоритм пошуку А* (А з з?рочкою). Дозволя? знайти шлях ?з найменшою варт?стю м?ж двома вершинами за допомогою алгоритму пошуку по першому найкращому зб?гу на граф?.Алгоритм Дейкстри. Знаходить найкоротший шлях у граф? в?д задано? вершини до вс?х ?нших, при цьому ваги ребер не можуть бути в?д’?мними. Даний алгоритм достатньо часто використовують у лог?стиц? [3]. За умови наявност? вс?? необх?дно? ?нформац?? за допомогою алгоритму Дейкстри можна, наприклад, д?знатися яку посл?довн?сть дор?г краще обрати для того, щоб д?статися з одного м?ста в ?нше, або нав?ть у як? кра?ни виг?дн?ше експортувати той чи ?нший продукт. Розглянемо цей алгоритм детальн?ше на приклад?. Знайдемо найкоротший шлях у граф?, який зображено на рисунку 1.2.Рисунок 1.2 - Заданий зважений графБудемо шукати шляхи в?д першо? вершини до вс?х ?нших. Позначимо кожну вершину м?ткою, яка буде в?дпов?дати найкоротшому шляху ?з вершини 1 – рисунок 1.3.Рисунок 1.3 - Граф з м?ткамиСус?дн?ми до вершини 1 ? вершини 2, 3 ? 6. Наступною п?сля вершини 1 буде вершина 2, оск?льки довжина шляху до не? найменша. Довжина шляху до вершини 2 через вершину 1 буде дор?внювати 0 + 7 = 7, де 0 – це найменша в?дстань до вершини 1, а 7 – довжина шляху в?д 1 до 2. Значення 7 менше, н?ж ∞, тому нова м?тка 2-? вершини буде 7.Зам?на м?тки друго? вершини показана на рисунку 1.4.Рисунок 1.4 – Зам?на м?тки друго? вершини.Так само поступимо з вершинами 6 ? 3 – рис. 1.5.Рисунок 1.5 – Зам?на м?тки вершин 3 ? 6.Отже, ус? сус?дн? вершини до вершини 1 перев?рен?, пом?ча?мо ?? та переходимо до вершини 2 – рисунок1.6.Рисунок 1.6 – Перех?д до вершини 2.Сус?дн?ми до вершини 2 ? вершини 1, 3, 4. Вершина 1 вже перев?рена, тому з нею н?чого не робимо. Шлях до вершини 3 через 2-гу вершину буде дор?внювати 7 + 10 = 17. Оск?льки 9 < 17, то м?тка не зм?ню?ться див рис.1.7. Рисунок 1.7. Перев?рка шляху до вершини 3.Шлях до вершини 4 через 2-гу вершину буде дор?внювати 7 + 15 = 22 < ∞, тому нова м?тка вершини 4 буде 22 – рисунок 1.8.Рисунок 1.8 – Перев?рка вершини 4.Ус? сус?ди 2-? вершини перев?рен?, пом?ча?мо ?? як пройдену та переходимо до наступно? вершини 3. Застосову?мо цей алгоритм до вершин, що залишилися 6, 4, 5 в?дпов?дно.Виконання алгоритму завершу?ться, коли будуть викреслен? вс? вершини. У результат? отрима?мо, що найкоротший шлях ?з вершини 1 до вершини 2 дор?вню? 7, до вершини 3 – 9, до вершини 4 – 20, до вершини 5 – 20, до вершини 6 – 11.Якщо у даному приклад? зам?нити вс? ваги ребер на d = 1, то отрима?мо задачу, яку не можна однозначно вир?шити за допомогою вище описаних алгоритм?в. Ця проблема виника? через те, що на першому кроц? ?сну? безл?ч вар?ант?в вибору наступно? вершини. Тому рац?ональн?ше буде вир?шувати таку задачу з використанням спектра графа. Алгоритм задач? пошуку шлях?в довжини k представлений у розд?л? 2.1.2 Спектри граф?в ? основн? визначенняСпектральна теор?я граф?в ма? довгу ?стор?ю. На початку свого ?снування матрична теор?я та л?н?йна алгебра використовувались для анал?зу матриц? сум?жност? граф?в. Алгебра?чн? методи особливо ефективн? для регулярних ? симетричних граф?в.Так само як астрономи вивчають спектри з?рок для того, щоб досл?дити зм?ст в?ддалено? з?рки, одна з основних ц?лей в теор?? граф?в поляга? у тому, щоб вивести основн? властивост? ? структуру графа за допомогою його спектра. Спектральна теор?я граф?в вивча? властивост? граф?в за допомогою анал?зу:власних значень;власних вектор?в;характеристичних пол?ном?в;матриць, як? зв’язан? з графами:матриця сум?жност?;матриця Лапласа;матриця ?нцендентност?.Причинами зац?кавленост? у вивченн? спектр?в графу стали так? явища.В квантов?й х?м?? скелети деяких ненасичених вуглеводн?в представляються у вигляд? граф?в. Енергетичн? р?вн? електрон?в у так?й молекул? являються власними значеннями в?дпов?дного графа. Ст?йк?сть молекули, а також ?нш? важлив? х?м?чн? властивост? т?сно пов’язан? з? спектром графа ? в?дпов?дними власними векторами.В теор?? граф?в ? комб?наториц? ?сну? багато теорем, при доведенн? яких застосовуються спектри граф?в. Отже, використання спектр?в граф?в гра? роль достатньо важливого метода, який назива?ться спектральним.Ще одним аспектом ? обчислювальний. Спектр – ск?нченна посл?довн?сть числових ?нвар?ант?в. З цього виплива?, що ?нформац?я, яка ц?кавить (або ?? значна частина) нас м?ститься у спектр?, тобто зам?сть графа можна використовувати його спектр.Також ц?кавим ? характер повед?нки власних значень при деяких перетвореннях граф?в, особливо в тих випадках, коли спектр складного графа можна представити через спектри елементарних граф?в.Означення. Матриця сум?жност? А мультиграфа (мультиорграфа) G з множиною вершин {v1, v2…, vn} – це квадратна матриця порядку n, у як?й значення елементу aij, розташованого на м?сц? (i, j), дор?вню? к?лькост? ребр, з початком у вершин? vi ? к?нцем у вершин? vj [4]. Нехай дано граф, що зображено на рисунку 1.9.Рисунок 1.9 – Заданий граф.Матриця сум?жност? графу, зображеного на малюнку матиме такий вигляд:A= 011011111011111100001111110111110110.Зрозум?ло, що граф G однозначно визнача?ться матрицею сум?жност? А, але в протилежному напрямку це твердження не працю?, тому що вершини графа можуть бути пронумерован? в будь-якому порядку. Означення. Характеристичний многочлен |λI-A| матриц? сум?жност? А графа G назива?ться характеристичним многочленом графа G ? познача?ться PG(λ). Власн? значення матриц? А (нул? многочлена |λI-A|) ? спектр матриц? А (склада?ться з власних значень) називаються в?дпов?дно власними значеннями та спектром графа G. Якщо λ1, …, λn – власн? значення графа G, то весь спектр познача?ться через SPG=[λ1, …, λn] [4].Власн? значення матриц? А також можна визначити як так? числа λ, що задовольняють р?вняння Ax =λx, для яких ?сну? ненульовий вектор x. Кожен такий вектор x назива?ться власним вектором матриц? А (графа G), як? в?дпов?дають власному значенню λ.Для графа G, зображеного на рисунку 1.9, обчислимо знайдемо характеристичний многочлен та спектр:PGλ= λ-1-1 λ-1-1-1-1-1 0-1-1-1-1-1-1 λ 0 0 λ-1-1-1-1-1-1 0-1-1-1-1-1 λ-1-1 λ= λ6-13λ4-24λ3-12λ2 Тод? отрима?мо такий спектр графа: SPG= -2, -1, 0, 32-332, 32+332.1.3 Операц?? над графами Доповненням графа G назива?ться граф G з тими самими вершинами, що ? граф G, ? з тими ? т?льки з тими ребрами, як? необх?дно добавити до графа G, щоб отримати повний граф.Пряма сума G1+G2 граф?в G1(V1,E1) ? G2(V2,E2) (V1∩V2=?) ? графом G(V,E), де V=V1∪V2 ? E=E1∪E2.Нехай Ai – матриця сум?жност? графа Gi (i = 1, 2), тод? матриця сум?жност? А графа G =G1+G2 ма? виглядA= А100 А2,тобто А =А1+А2, де знак + означа? пряму суму матриць.Нехай в?дом? характеристичн? многочлени PG1(λ), PG2(λ) граф?в G1 ? G2 в?дпов?дно. Тод? характеристичний многочлен графа PG1+G2(λ) можна зайти за допомогою формули PG1+G2λ= PG1λ* PG2λ. Узагальнений випадок. Якщо G1, G2, …, Gn – компоненти графа G, а кожен граф ? пряма сума його компонент, тоPGλ= PG1λ* PG2λ* … * PGnλ. Повний добуток G1?G2 граф?в G1(V1,E1) ? G2(V2,E2) ? граф, отриманий з G1+G2 в результат? з’?днання кожно? вершини графа G1 з кожною вершиною графа G2.Для повного добутку характеристичний многочлен визнача?ться наступною формулою:PG1?G2λ= (-1)n2PG1λPG2-λ-1+(-1)n1PG2λPG1-λ-1- -1n1+n2PG1-λ-1PG2-λ-1.Граф назива?ться елементарним, якщо в?н зв’язний ? не може бути представлений у вигляд? повного добутку двох граф?в, як? не перетинаються. Клас елементарних граф?в достатньо великий. За допомогою таких граф?в можуть бути утворен? ?нш? графи з використанням наведених у цьому пункт? операц?й [4]. 1.4 Висновки до розд?луУ даному розд?л? було розглянуто основн? теоретичн? в?домост? теор?? граф?в ? наведено головн? визначення спектрально? теор?? так? як: матриця сум?жност?, характеристичний многочлен ? спектр графу. Також були розглянут? алгоритми пошуку шляху м?н?мально? довжини: алгоритм Беллмана-Форда, Джонсона, Флойда-Уоршелла, Дейкстри, хвильовий алгоритм, алгоритм пошуку А*. Для алгоритму Дейкстри було наведено приклад.Було розкрито актуальн?сть використання спектру графа, як потужного ?нструмента для вир?шення р?зноман?тних задач. Також актуальн?сть задач? пошуку м?н?мальних шлях?в у граф? та наведено приклади практичного застосування.РОЗД?Л 2 ПОШУК МАРШРУТ?В ЗА ДОПОМОГОЮ СПЕКТРАЛЬНО? ТЕОР?? ГРАФ?В2.1 Про к?льк?сть маршрут?вМультиграф G ?з симетричною матрицею сум?жност? повн?стю визнача?ться власними значеннями та власними векторами. Якщо x1, x2, x3…, xn – повна система вза?мно ортогональних нормованих власних вектор?в матриц? А, що в?дпов?дають спектру [λ1, …, λn], X = x1, x2, x3…, xn=(xij) ? ?= (δijλi). Х – ортогональна матриця ( X-1=XT) ? A=X?XT [4].За допомогою спектрально? теор?? граф?в можна визначити число маршрут?в довжини k, використовуючи матрицю сум?жност? та спектр графа.Нехай А – матриця сум?жност? мультиорграфа G з вершинами 1, 2, …, n ? Ak=aijk; нехай Nk(i,j) познача? число маршрут?в довжини k, як? починаються у вершин? i та зак?нчуються у вершин? j [4]. Тод? Nki,j=aij(k) (k = 0, 1, 2, …).При k = 1 матриця сум?жност? м?стить число шлях?в довжини 1 м?ж кожною парою вершин.Нехай тепер G познача? мультиграф ? X = x1, x2, x3…, xn=(xij) – ортогональна матриця власних вектор?в матриц? А. Тод?aij(k)= ν=1nxiνxjvλνk.Число вс?х маршрут?в довжини k в граф? G Nk= i,jNk(i,j)= i,jaij(k)=ν=1n(i=1nxiν)2λνk. (2.1)Дивлячись на формулу (2.1), можна зробити висновок, що для пошуку к?лькост? вс?х маршрут?в графа довжини k не обов’язково мати граф?чне представлення, достатньо знати значення його спектра ? власних вектор?в. Знайдемо число вс?х маршрут?в довжини k = 2 для графа, зображеного на рисунку 1.10 за допомогою матриц? сум?жност?Рисунок 2.1 – Заданий графМатриця сум?жност? для цього графаA= 0110011101110110.Тод? матриця A2, де N2i,j=aij(2) – к?льк?сть маршрут?в довжини 2, як? починаються у вершин? i та зак?нчуються у вершин? j, матиме виглядA2= 2113211221122113.Отрима?мо N2= i,jN2(i,j)=26 – число вс?х маршрут?в графа довжини k = 2.Тепер знайдемо спектр матриц? та власн? вектори, скориста?мося формулою ? пор?вня?мо результати.PGA= λ-1-1 λ 0-1-1-1 0-1-1-1 λ-1-1 λ= λ4-5λ2-4λ.Спектр графа SPG=[1+172, 1-172 , -1, 0].Влаcн? вектори:x1=[-0,44; -0,56; -0,44; -0,56]; x2=[0,56;0,44; -0,56; -0,44]; x3=[0, -1, 0, 1];x4=[-1, 0, 1, 0]. Тод? к?льк?сть шлях?в довжини k = 2 графа за формулою (2.1) буде р?внаN2=ν=14(i=14xiν)2λν2 = (-0,44-0,56-0,44-0,56)2*2,562++0,56+0,44-0,56-0,442*-1,562+0-1+0+12*-12++(-1+0+1+0)2*0≈26 .В?дпов?д? зб?глися, отже результат отримали в?рний.Нехай тепер G - неор??нтовний зважений граф з n вершинами, ? задано ц?ле число k. А – матриця сум?жност? графа G розм?ру n х n, де кожен елемент aij м?стить довжину ребра з вершини i до вершини j. Якщо м?ж вершинами нема? ребра, то в?дпов?дний елемент матриц? будемо вважати р?вним неск?нченност? ∞. Нехай Dk(i,j) число найкоротших шлях?в ?з вершини i до вершини j, як? складаються р?вно з k ребер. Тод? Dki,j= aij?k, де ? - операц?я множення двох матриць визна?ться як A B=C, Cij = minp=1…n(Aip+Bpj) [5].Число вс?х найкоротших шлях?в в граф? G, як? складаються р?вно з k реберDk=i,jaij?k. Зрозум?ло, що при k = 1 – матриця сум?жност? м?стить довжини найкоротших шлях?в м?ж кожною парою вершин, або неск?нченн?сть ∞, якщо шляху довжини k = 1 не ?сну?.2.2 Перетворення граф?в ? к?льк?сть маршрут?вВикористовуючи методи представлен? у попередньому пункт? зрозум?ло, що знайти число вс?х маршрут?в Nk елементарних граф?в не склада? труднощ?в. Але якщо граф складний, то знайти спектр цього графу буде не так просто. Доц?льно буде представити такий граф через елементарн? графи за допомогою перетворень.Розглянемо метод вир?шення дано? задач? з використанням тв?рно? функц?? для числа маршрут?в.Тв?рна функц?я (генератриса) посл?довност? a0, a1, a2…– це формальний степеневий рядG(z) = n=0∞anznВизначимо тв?рну функц?ю для числа маршрут?в графа HG(t), де G – граф з доповненням G.HGt= k=0∞Nktk,де Nk – число маршрут?в довжини k у граф?.З цього твердження сл?ду?, що к?льк?сть маршрут?в Nk графа G можна виразити за допомогою тв?рно?:Nk= HG(n)(0)n!,де HG(n)(0) n-та пох?дна тв?рно? HGt у точц? t = 0.Генератриса для числа маршрут?в графа визнача?ться через його характеристичн? многочлени та доповненняHGt= 1t -1nPG-t+1tPG1t-1. Важливу роль у теор?? граф?в в?д?грають графи, як? отримують за допомогою елементарних перетворень таких як: доповнення G, пряма сума G1+G2, повний добуток G1?G2 та додавання до кожно? вершини графа одн??? петл? G`. Для таких граф?в мають м?сце наступн? формули визначення генератрисиHG`t= 11-tHG11-t,HGt= HG( - tt+1)t+1-tHG(- tt+1),HG1+G2t= HG1t+ HG2t, HG1?G2t= HG1t+HG2t+2tHG1tHG2t1-t2HG1tHG2t.Отже, знаючи формули генератриси елементарних граф?в, можна знайти сумарну к?льк?сть маршрут?в Nk довжини k у дов?льному граф? G.2.3 Використання у комб?наториц?Задача пошуку маршрут?в у граф? знайшла застосування й у комб?наториц?. Розглянемо дек?лька таких задач.Перестановка k-го класу з повторенням елемент?в ?з множини X={x1, x2, …, xn} ? дов?льною впорядкованою k-кою (x1, …, xik), де ij∈ {1, 2, …, n} (j = 1, 2, …, k). К?льк?сть таких перестановок з повторенням елемент?в Vnk= nk.Перестановка з обмеженням. Нехай Xi (i = 1, 2, …, n) – с?мейство п?дмножин X. Пара (xi, xj) назива?ться допустимою тод? ? т?льки тод?, коли xj∈ Xi. Квадратна матриця A= (aij)1n, де (aij)=1, якщо (xi, xj) допустима пара, ? (aij)=0 якщо (xi, xj) не ? допустимою парою, назива?ться матрицею допустимих пар. Матриця обмежень A отриму?ться з A у результат? зам?ни 0 на 1, а 1 на 0.А – перестановкою з повтореннями k-го класу назива?ться k-ка (xij,…, xik), де xij∈ Xij-1 (j = 2, 3, …, k). Число Vnk(A) – це число А-перестановок з повтореннями k-го класу з множини, що м?стить n елемент?в [6]. Якщо матрицю А визначити як матрицю сум?жност? орграфа G з вершинами x1, x2, …, xn, то число Vnk(A) буде дор?внювати числу маршрут?в довжини k-1 у граф? G. VnkA= Nk-1.Нехай задано граф G на рисунку 2.2, визначимо число А-перестановок з повтореннями 2-го класу.Рисунок 2.2 – Заданий графВизначимо матрицю сум?жност? для графа G:A= 0110111111110110.Знайдемо спектр ? власн? вектори.PGA= λ-1-1 λ-1-1-1-1-1-1-1-1 λ-1-1 λ= λ4-6λ2-8λ-3. Спектр графа SPG=[-1, 3, -1, -1].Власн? вектори:x1=-0,87;0,29;0,29;0,29; x2=[0,5;0,5;0,5;0,5]; x3=0,22; -0,86;0,32;0,32; x4=0;0; -0,71;0,71. Отже, число А-перестановок буде дор?внюватиV42A= N1= ν=14(i=14xiν)2λν1= (-0,87+0,29+0,29+0,29)2*-1++0,5+0,5+0,5+0,52*3+0,22-0,86+0,32+0,322*-1+0+0--0,71+0,712*-1=12. Ц?кавою ? задача про шахового короля. Необх?дно знайти к?льк?сть способ?в, за допомогою яких король може зробити сер?ю з k крок?в на одном?рн?й шахов?й дошц?. Будемо вважати, що пересування короля ? графом на задан?й шахов?й дошц?. Вершинами такого графа ? квадратами шахово? дошки, дв? вершини сум?жн? тод? ? т?льки тод?, коли король може перейти з одного квадрата в ?нший за один х?д. Тод? в?дпов?дним графом буде простий ланцюг Pn [7]. Простий ланцюг Pn явля?ться зв’язним графом з n вершинами, дв? з яких ? п?дв?сними, а ?нш? n – 2 вершин мають степ?нь 2. Шлях ма? n -1 ребро [8].Матриця сум?жност? ланцюга Pn зображена на рисунку 2.3.Рисунок 2.3 – Матриця сум?жност? ланцюга Pn.Власними значеннями ? λi=2cosiπn+1 (i = 1, 2, …, n). Вираз uij= 2n+1sinijπn+1 (j = 1, 2, …, n) визнача? координати нормал?зованого власного вектору uj, в?дпов?дного власному значенню λi [4]. К?льк?сть маршрут?в довжини k у простому ланцюгу Pn визнача?ться якNkn= 2k+1n+1l=1(n+1)/2ctg22l-1n+1π2cosk2l-1nπ.Число Nkn ? буде в?дпов?ддю на задачу про шахового короля.Задача пошуку шляху та спектр графа також використовуються для визначення комб?нац?й з повтореннями. Розглянемо комб?нац?? p-го класу з повтореннями, для яких dj ∈M j=1, …, p, M ?{1, …, n}, де dj = xj+1- xj ? найб?льший елемент m ?з M задовольня? умову pm<2n [9]. Якщо множину x1, …, xn представити у вигляд? вершин ор??нтовного графа G, у якому ор??нтовне ребро з вершини xi у вершину xj ?сну? тод? ? т?льки тод?, коли (i-j) (mod n)∈M. Кр?м цього у кожно? вершини графа G ? петля. Кожн?й ?з таких комб?нац?? в?дпов?да? в точност? p замкнутих маршрут?в довжини p. Не в?дпов?дають жодн?й з комб?нац?й т?льки т? маршрути, як? через наявн?сть петл? не покидають вершину, у як?й починаються. К?льк?сть таких маршрут?в дор?вню? m. Якщо [λ1,…, λn]– спектр графа G, то к?льк?сть таких комб?нац?й можна знайти за допомогою наступно? формули1pi=1nλip-n.Для прикладу розглянемо ор??нтовний граф G з n = 5 вершинами. Знайдемо комб?нац?? p-го класу з повтореннями, де p = 2. Визначимо множину M=2, 3?{1, 2, 3, 4, 5}. Перев?римо справедлив?сть умови pm<2n:2*3 = 6 < 10 = 2*5 – умова викону?ться.Побуду?мо граф в?дпов?дно умов? ?снування ребер (i-j) (mod n) ∈M.(1-2) (mod 5) = 4 ? M – ребра нема?.(1-3) (mod 5) = 3∈M – ребро ?сну?.(1-4) (mod 5) = 2∈M – ребро ?сну?.(1-5) (mod 5) = 1 ? M – ребра нема?.Перев?ря?мо таким чином ус? вершини графа та буду?мо в?дпов?дний граф – рисунок 2.4.Рисунок 2.4 – Побудований граф.Побуду?мо матрицю сум?жност? для отриманого графа.A= 1010101011101110011011001.Спектр такого графу буде SPG=[3;1,62;1,62; -0,62; -0,62 ].Тод? к?льк?сть комб?нац?й буде дор?внювати1pi=1nλip-n= 12i=15λi2-5=129+5,25+0,77-5≈5. Наведен? приклади п?дтверджують значим?сть задач? пошуку шлях?в не т?льки у теор?? граф?в, а ? у такому розд?л? дискретно? математики, як комб?наторика. 2.4 Висновки за розд?лом У даному розд?л? була розглянута задача пошуку маршрут?в з використанням спектрально? теор?? граф?в. Головна мета поляга? у тому, щоб наочно показати спектральну теор?ю як потужний математичний апарат для вир?шення р?зного роду задач.Основним ?нструментом спектрально? теор?? ? спектр графа, за допомогою якого можна д?знатися про структуру та властивост? самого графа. У дан?й робот? спектр використову?ться для пошуку шлях?в ф?ксовано? довжини. Також представлен? деяк? приклади використання спектру графа у задачах комб?наторики.Найважлив?шим моментом ? те, що як ? безпосередньо сама теор?я граф?в, так ? спектральна теор?я довол? часто використову?ться на практиц? у реальному житт?.РОЗД?Л 3 РОЗРОБКА ПРОГРАМНОГО ПРОДУКТУ ПОШУКУ К?ЛЬКОСТ? ШЛЯХ?В ДОВЖИНИ3.1 Дан? для роботиДля того, щоб показати роботу програмного продукту в якост? вх?дних даних було обрано схему low-cost ав?ал?н?й. Бюджетн? ав?акомпан?? набувають все б?льше популярност? по всьому св?ту. Принцип роботи таких компан?й поляга? у тому, що вони надають можлив?сть придбати квитки за низькою ц?ною, натом?сть вам доведеться в?дмовитись в?д б?льшост? звичних пасажирських послуг, наприклад, ?з багажу можна брати т?льки ручну поклажу визначених розм?р?в, ?жа на борту дуже дорога, у квитках не вказан? м?сця, тобто м?сце треба займати як у звичайному автобус? тощо. Як вже було сказано, схему ав?ал?н?й можна зобразити у вигляд? графу, де вершинами являються аеропорти у певному м?ст?, а ребрами – шляхи сполучення м?ж ними. Будемо вважати, що ребро з вершини xi у вершину xj ?сну? тод? ? т?льки тод?, коли м?ж м?стами xi ? xj ?сну? прямий рейс. Мета роботи поляга? у тому, щоб визначити яка м?н?мальна к?льк?сть пересадок знадобиться, щоб потрапити з одного м?ста в ?нше, якщо прямого рейсу не ?сну?. Нехай дано 11 м?ст: Ки?в (0), Париж (1), Прага (2), Брюссель (3), Мюнхен (4), Москва (5), Рим (6), Лондон (7), Осло (8), Варшава (9), Дубл?н (10) – вершини графу. Для визначення ?снування прямих рейс?в м?ж цими м?стами було використано карту рейс?в на сайт? [10]. Отже, будемо вир?шувати задачу з використанням спектрально? теор?? граф?в, в?дпов?дно до вх?дних даних.3.2 Опис програмиДля вир?шення задач? пошуку шлях?в довжини k у граф? G було створено програмний продукт. В?н дозволя? знайти спектр графу, власн? вектори та вс? шляхи довжини k у граф?.Програма розроблена на мов? програмування Python. Python включа? в себе велику к?льк?сть б?бл?отек ? вбудованих функц?й, що значно може спростити сприймання програми. За допомогою б?бл?отеки matplotlib.pyplot досить легко будувати графи. Перейдемо до описання функц?й.grafgen – буду? граф на основ? задано? матриц? сум?жност?.paths – п?драхову? к?льк?сть ус?х шлях?в задано? довжини k, використовуючи формулу (2.1).np.linalg.eig – знаходить власн? числа (спектр графа) та власн? вектори задано? матриц? сум?жност?.np.linalg.matrix_power(mat,k) – зводить матрицю у степ?нь k.Розглянемо роботу програми на невеликому приклад?.Нехай дано граф G з матрицею сум?жност? А.A= 0111001000110010101010000.П?д час запуску програми з’явиться в?кно, у яке треба ввести задану матрицю. Вводити треба по строках, в?докремлюючи елементи один в?д одного проб?лом, як зображено на рисунку 3.1. Програма визнача? розм?р матрицю за к?льк?стю елемент?в першого введеного рядку, оск?льки матриця сум?жност? графа завжди ? квадратною рис.3.2.Рисунок 3.1 – Вв?д першо? строчки матриц? сум?жност?Рисунок 3.2 – Введена матрицяП?сля цього програма обчислю? значення спектру графу (власних чисел) ? власних вектор?в та виводить ?х значення. Власн? вектори ? нормованими та ортогональними рис. 3.3. Рисунок 3.3 – Значення власних чисел ? власних вектор?в.Також програма в?зуал?зу? граф, використовуючи матрицю сум?жност?. Зв?сно, граф може мати зовс?м ?нший вигляд через те, що пронумерувати вершини графу можна безл?ччю р?зними способами. Але головне тут побачити як з’?днан? м?ж собою вершини графу – рисунок 3.4.Рисунок 3.4 – Зображення графу.Дал? необх?дно ввести довжину шляху k, к?льк?сть яких потр?бно знайти рис 3.5.Рисунок 3.5 – Вв?д значення довжини шляху.Нарешт?, отриму?мо к?льк?сть шлях?в довжини k, а також матрицю сум?жност? у ступен? k – рис 3.6, рис 3.7.Рисунок 3.6 – К?льк?сть вс?х шлях?в довжини 2, матриця сум?жност? у ступен? 2.Рисунок 3.7 - К?льк?сть вс?х шлях?в довжини 3, матриця сум?жност? у ступен? 3Перев?рити правильн?сть в?дпов?д? можна склавши вс? елементи матриц?. Наприклад, для k = 2 отрима?мо наступне 2+ 1 + 1 + 1 + 2 + 1 + 2 + 1 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 22.Отже, отримана в?дпов?дь ? в?рною.3.3 Практичне застосуванняОск?льки пошук шлях?в буде зд?йснюватися ?з застосуванням спектру графа та власних вектор?в, то сам граф зображати не обов’язково. Тому одразу буду?мо матрицю сум?жност?.A= 0010011101001101011110100010111011100001101100010001010100000010000110110001000101000100000100000111001001011001100100000.Отриману матрицю сум?жност? пода?мо як вх?дн? дан? для програми - рис 3.8.Рисунок 3.8 – Матриця сум?жност?.Отриму?мо значення спектру графа ? власних вектор?в – рисунок 3.9.Рисунок 3.9 – Значення власних чисел ? власних вектор?в.А також граф, який в?зуал?зу? зв’язки м?ж м?стами рис.3.10.Рисунок 3.10 – Отриманий граф.Тепер перейдемо безпосередньо до визначення м?н?мально? к?лькост? пересадок. Будемо вважати, що для того, щоб пройти шлях довжиною k, треба зд?йснити k-1 пересадку. Тод? будемо перебирати значення k, поки не отрима?мо в?дпов?дь в?дм?нну в?д нуля.Виберемо будь-яку пару (i, j) м?ст, для яких не ?сну? прямого рейсу, тобто таких, щоб елемент матриц? (i, j) був р?вним нулю.Нехай ц??ю парою буде Ки?в(0) – Париж(1). Вводимо значення i, j= (0,1) та k = 2 (рис. 3.12). Програма виводить к?льк?сть шлях?в довжиною 2, тобто шлях?в з одною пересадкою, з Ки?ва до Парижу – рисунок 3.11. Рисунок 3.11. – К?льк?сть ус?х шлях?в довжини 2 ? матриця у степен? 2.Рисунок 3.12 - К?льк?сть шлях?в довжини 2 для пари м?ст (0,1)Отриманий результат св?дчить, що ?сну? 2 таких шляхи. Якщо проанал?зувати матрицю сум?жност?, можна пом?тити, що ? з Ки?ва, ? з Парижа ? прям? рейси до Праги та Брюсселю. Зв?дси робимо висновок, що отриман? 2 шляхи ? Ки?в – Прага – Париж,Ки?в – Брюссель – Париж. Для пари Осло(8) – Москва(5) отрима?мо т?льки один шлях з одн??ю пересадкою (рис. 3.13). Одночасно з Осло та Москви можна потрапити т?льки у Брюссель, тому шуканим шляхом будем Осло – Брюссель – Москва.Рисунок 3.13 - К?льк?сть шлях?в довжини 2 для пари м?ст (8,5)Виберемо ?ншу пару м?ст – Дубл?н(10) – Брюссель(3) ? повторю?мо описаний вище алгоритм д?й. Отримали значення р?вне нулю (рис. 3.14) – це означа?, що шляху довжини 2 не ?сну?, тому з Дубл?на потрапити до Брюсселю з одн??ю пересадкою неможливо.Рисунок 3.14 – К?льк?сть шлях?в довжини 2 для пари м?ст (10,3) Введемо тепер k = 3 – рисунок 3.15.Рисунок 3.15 -Отримали 4 шляхи довжиною 3, тобто з Дубл?на до Брюсселя можна потрапити 4 шляхами з двома пересадками.Рисунок 3.16 - К?льк?сть шлях?в довжини 3 для пари м?ст (10,3) Так само анал?зуючи матрицю сум?жност? знайдемо ц? шляхи. Бачимо, що з Дубл?на ? т?льки один прямий рейс – рейс до Лондона. Шука?мо м?ста в як? можна попасти як з Лондона, так ? з Брюсселю. Цими м?стами ? Париж, Прага, Мюнхен, Рим. Шуканими шляхами будуть Дубл?н – Лондон – Париж – Брюссель, Дубл?н – Лондон – Прага – Брюссель, Дубл?н – Лондон – Мюнхен – Брюссель, Дубл?н – Лондон – Рим – Брюссель.Так само для пари Дубл?н(10) – Москва(5) не ?сну? шляху з одн??ю пересадкою, але ?снують 2 шляхи з двома пересадками (рис. 3.17). Рисунок 3.17 – К?льк?сть шлях?в довжини 3 для пари м?ст (10,5)З матриц? сум?жност? бачимо, що з Дубл?на прямим рейсом можна потрапити т?льки у Лондон. Одночасно з Москви та Лондона можна потрапити до Праги та Мюнхену. Отже, потр?бними шляхами ? Дубл?н – Лондон – Прага – Москва, Дубл?н – Лондон – Мюнхен – Москва.3.4 Висновки до розд?лу У даному розд?л? було продемонстровано роботу та опис програмного продукту. Наведено простий приклад для того, щоб ознайомитися з програмою. Подаючи, як вх?дн? дан?, матрицю сум?жност? графа, у результат? отрима?мо п?драхован? спектр графа, власн? вектори та к?льк?сть ус?х шлях?в довжиною k, а також граф, що в?зуал?зу? зв’язки м?ж вершинами графу.Як б?льш практичний приклад було обрано схему low-cost ав?ал?н?й. Графом вважа?ться сама схема, вершинами такого графу – м?ста, а ребрами – шляхи сполучень м?ж м?стами. Метою даного прикладу було показати як за допомогою спектрально? теор?? граф?в можна визначити яка м?н?мальна к?льк?сть пересадок потр?бна, щоб потрапити з одного м?ста в ?нше, якщо прямого рейсу не ?сну?.РОЗД?Л 4 ФУНКЦ?ОНАЛЬНО-ВАРТ?СНИЙ АНАЛ?ЗУ даному розд?л? проводиться оц?нка основних характеристик програмного модуля, призначеного для пошуку числа шлях?в довжини k у граф? G. Даний продукт розроблений на мов? програмування Python у середовищ? Jupyter Notebook в якост? модуля, який можна вбудовувати у веб-застосунок. Програмний продукт призначено для використання в першу чергу на персональних комп’ютерах. Нижче наведено анал?з р?зних вар?ант?в реал?зац?? модулю з метою вибору оптимального, з огляду при цьому як на економ?чн? фактори, так ? на характеристики продукту, що впливають на продуктивн?сть роботи ? на його сум?сн?сть з апаратним забезпеченням. Для цього було використано апарат функц?онально-варт?сного анал?зу. Функц?онально-варт?сний анал?з (ФВА) – це технолог?я, яка дозволя? оц?нити реальну варт?сть продукту або послуги незалежно в?д орган?зац?йно? структури компан??. Як прям?, так ? поб?чн? витрати розпод?ляються по продуктам та послугам у залежност? в?д потр?бних на кожному етап? виробництва обсяг?в ресурс?в. Виконан? на цих етапах д?? у контекст? метода ФВА називаються функц?ями. Мета ФВА поляга? у забезпеченн? правильного розпод?лу ресурс?в, вид?лених на виробництво продукц?? або надання послуг, на прям? та непрям? витрати. У даному випадку – анал?зу функц?й програмного продукту й виявлення ус?х витрат на реал?зац?ю цих функц?й. Фактично цей метод працю? за таким алгоритмом: ?Визнача?ться посл?довн?сть функц?й, необх?дних для виробництва продукту. Спочатку – вс? можлив?, пот?м вони розпод?ляються по двом групам: т?, що впливають на варт?сть продукту ? т?, що не впливають. На цьому ж етап? оптим?зу?ться сама посл?довн?сть скороченням крок?в, що не впливають на ц?нн?сть ? в?дпов?дно витрат.Для кожно? функц?? визначаються повн? р?чн? витрати й к?льк?сть робочих годин.Для кожно? функц?? на основ? оц?нок попереднього пункту визнача?ться к?льк?сна характеристика джерел витрат.П?сля того, як для кожно? функц?? будуть визначен? ?х джерела витрат, проводиться к?нцевий розрахунок витрат на виробництво продукту.4.1 Постановка задач? техн?ко-економ?чного анал?зу У робот? застосову?ться метод ФВА для проведення техн?ко-економ?чного анал?зу розробки.В?дпов?дно до цього варто обирати ? систему показник?в якост? програмного продукту. Техн?чн? вимоги до продукту наступн?:програмний продукт повинен функц?онувати на персональних комп’ютерах, а також на серверах (дроплетах) ?з стандартним набором компонент;забезпечувати високу швидк?сть обробки великих об’?м?в даних у реальному час?;забезпечувати зручн?сть ? простоту вза?мод?? з користувачем або з розробником програмного забезпечення у випадку використовування його як модуля;передбачати м?н?мальн? витрати на впровадження програмного продукту.4.1.1Об?рунтування функц?й програмного продуктуГоловна функц?я F? – розробка програмного продукту, який п?драхову? к?льк?сть шлях?в довжини k заданого графа G з використанням спектрально? теор?? граф?в, де як вх?дн? дан? переда?ться матриця сум?жност? заданого графу. Виходячи з конкретно? мети, можна вид?лити наступн? основн? функц?? ПП:F1 – виб?р мови програмування;F2 – розп?знавання вх?дних даних;F3 – ?нформац?йне в?кно.Кожна з основних функц?й може мати дек?лька вар?ант?в реал?зац??.Функц?я F1:а) мова програмування С++;б) мова програмування Python.Функц?я F2:а) введення даних вручну як аргумент;б) написання нового модулю розп?знавання даних.Функц?я F3:а) виведення результат?в роботи в окремий файл;б) реал?зац?я в?зуально-граф?чного модуля.4.1.2Вар?анти реал?зац?? основних функц?йВар?анти реал?зац?? основних функц?й наведен? у морфолог?чн?й карт? системи (рис. 4.1). На основ? ц??? карти побудовано позитивно-негативну матрицю вар?ант?в основних функц?й (таблиця 4.1).Морфолог?чна карта в?дображу? вс? можлив? комб?нац?? вар?ант?в реал?зац?? функц?й, як? складають повну множину вар?ант?в ПП.Рисунок 4.1 – Морфолог?чна картаТаблиця 4.1 – Позитивно-негативна матрицяОсновн? функц??Вар?анти реал?зац??ПеревагиНедол?киF1АВелика швидкiсть роботиЗайма? бiльше часу при написанн? кодуБЗайма? менше часу при написанн? кодуПовiльна швидкiсть роботиF2АПростий у реал?зац??В?дсутн?сть в?зуально-граф?чних результат?вБЗручний у використанн?Займа? б?льше часу при написанн? кодуF3АПростий у реал?зац??В?дсутн?сть в?зуально-граф?чних результат?вБСтаб?льний та зручний у використанн?Займа? б?льше часу при написанн? кодуНа основ? анал?зу позитивно-негативно? матриц? робимо висновок, що при розробц? програмного продукту деяк? вар?анти реал?зац?? функц?й варто в?дкинути, тому, що вони не в?дпов?дають поставленим перед програмним продуктом задачам. Ц? вар?анти в?дзначен? у морфолог?чн?й карт?.Функц?я F1:Оск?льки розрахунки проводяться з великими об’?мами даних, то час написання програмного коду ? дуже необх?дним, тому вар?ант а) ма? бути в?дкинутий.Функц?я F2:Оск?льки плану?ться реал?зувати прикладну задачу з широким спектром р?зноман?тних вх?дних вар?ант?в даних то, б) може бути в?дкинутий.Функц?я F3:Оск?льки обидва вар?анти п?дходять для реал?зац?? програмного продукту, то сл?д розглянути а) ? б).Таким чином, будемо розглядати так? вар?анти реал?зац?? ПП: F1б – F2а – F3аF1б – F2а – F3бДля оц?нювання якост? розглянутих функц?й обрана система параметр?в, описана нижче.4.2 Об?рунтування системи параметр?в програмного продукту4.2.1 Опис параметр?вДля того, щоб охарактеризувати програмний продукт, будемо використовувати наступн? параметри:X1 – швидкод?я мови програмування;X2 – об’?м пам’ят? для збереження даних;X3 – час обробки даних;X4 – потенц?йний об’?м програмного коду.X1: В?добража? швидкод?ю операц?й залежно в?д обрано? мови програмування. X2: В?добража? об’?м пам’ят? в оперативн?й пам’ят? персонального комп’ютера, необх?дний для збереження та обробки даних п?д час виконання програми.X3: В?добража? час, який витрача?ться на д??.X4: Показу? розм?р програмного коду який необх?дно створити безпосередньо розробнику.4.2.2 К?льк?сна оц?нка параметр?вГ?рш?, середн? ? кращ? значення параметр?в вибираються на основ? вимог замовника й умов, що характеризують експлуатац?ю ПП як показано у таблиц? 4.2.Таблиця 4.2 – Основн? параметри ППНазвапараметраУмовн? позначенняОдиниц? вим?руЗначення параметраг?рш?середн?кращ?Швидкод?я мови програмуванняX1с1172Об’?м пам’ят? для збереження данихX2мб32168Час обробки даних алгоритмомX3мс40025080Об’?м програмного кодуX4к?льк?сть строк коду30001800800За даними таблиц? 4.2 будуються граф?чн? характеристики параметр?в (рис. 4.2 – рис. 4.5).Рисунок 4.2 – Х1, швидкод?я мови програмуванняРисунок 4.3 – Х2, об’?м пам’ят? для збереження данихРисунок 4.4 – Х3, час обробки даних алгоритмомРисунок 4.5 – Х4, потенц?йний об’?м програмного коду4.2.3 Анал?з експертного оц?нювання параметр?вП?сля детального обговорення й анал?зу кожний експерт оц?ню? ступ?нь важливост? кожного параметру для конкретно поставлено? ц?л? – розробка програмного продукту, який да? найб?льш точн? результати при знаходженн? параметр?в моделей адаптивного прогнозування ? обчислення прогнозних значень. Значим?сть кожного параметра визнача?ться методом попарного пор?вняння. Оц?нку проводить експертна ком?с?я ?з 7 людей. Визначення коеф?ц??нт?в значимост? передбача?:визначення р?вня значимост? параметра шляхом присво?ння р?зних ранг?в;перев?рку придатност? експертних оц?нок для подальшого використання;визначення оц?нки попарного пр?оритету параметр?в;обробку результат?в та визначення коеф?ц??нту значимост?.Результати експертного ранжування наведен? у таблиц? 4.3.Таблиця 4.3 – Результати ранжування параметр?вПозн. параметраНазва параметраОд. вим?руРанг параметра за оц?нкою експертаСума ранг?в RiВ?дхилення ΔiΔi21234567X1Швидкод?я мови програмуванняс212112211-6.542.25X2Об’?м пам’ят? для збереження данихмб121221110-7.556.25X3Час обробки даних алгоритмомМс3334434246.542.25X4Потенц?йний об’?м програмного кодук?льк?сть строк коду4443343257.556.25Разом10101010101010700197Для перев?рки степен? достов?рност? експертних оц?нок, визначимо наступн? параметри:а) сума ранг?в кожного з параметр?в ? загальна сума ранг?в :Ri=j=1NrijRij=Nnn+12=70,де N – число експерт?в, n – к?льк?сть параметр?в;б) середня сума ранг?в:T=1nRij=17.5.в) в?дхилення суми ранг?в кожного параметра в?д середньо? суми ранг?в:?i=Ri-T.г) загальна сума квадрат?в в?дхилення:S=i=1N?i2=197.Пораху?мо коеф?ц??нт узгодженост?:W=12SN2n3-n=12?1977243-4=0.804>Wk=0,67.Ранжування можна вважати достов?рним, тому що знайдений коеф?ц??нт узгодженост? перевищу? нормативний, котрий дор?вню? 0,67.Скориставшись результатами ранжирування, проведемо попарне пор?вняння вс?х параметр?в ? результати занесемо у таблицю 4.4.Таблиця 4.4 – Попарне пор?вняння параметр?вПараметриЕкспертиК?нцева оц?нкаЧислове значення1234567X1 ? X2><><<>>>1,5X1 ? X3<<<<<<<<0,5X1 ? X4<<<<<<<<0,5X2 ? X3<<<<<<<<0,5X2 ? X4<<<<<<<<0,5X3 ? X4<<<>><><0,5Числове значення, що визнача? ступ?нь переваги i–го параметра над j–тим, aij визнача?ться як:З отриманих числових оц?нок переваги складемо матрицю A=║ aij ║.Для кожного параметра зробимо розрахунок вагомост? Kв?:Kв?=bii=1nbi, де bi=i=1Naij.В?дносн? оц?нки розраховуються дек?лька раз?в доти, поки наступн? значення не будуть незначно в?др?знятися в?д попередн?х (менше 2%).На другому ? наступних кроках в?дносн? оц?нки розраховуються за наступними формулами Kв?=bi'i=1nbi' , де bi'=i=1Naijbj.Як видно з таблиц? 4.5, р?зниця значень коеф?ц??нт?в вагомост? не перевищу? 2%, тому б?льшо? к?лькост? ?терац?й не потр?бно.Таблиця 4.5 – Розрахунок вагомост? параметр?вПараметри xiПараметриxjПерша ?тер.Друга ?тер.Третя ?терХ1Х2Х3Х4biKв?bi1Kв?1bi2Kв?2Х11,01,50,50,53,50,21812,250,20844,8750,208Х20,51,00,50,52,50, 1569,250,15734,1250,158Х31,51,51,00,54,50,28116,250,27559,1250,274X41,51,51,51,05,50,34421,250,36077,8250,361Всього:16159121614.3 Анал?з р?вня якост? вар?ант?в реал?зац?? функц?йВизнача?мо р?вень якост? кожного вар?анту виконання основних функц?й окремо.Абсолютн? значення параметр?в Х2(об’?м пам’ят? для збереження даних) та X1 (швидкод?я мови програмування) в?дпов?дають техн?чним вимогам умов функц?онування даного ПП.Абсолютне значення параметра Х3 (час обробки даних) обрано не найг?ршим (не максимальним), тобто це значення в?дпов?да? або вар?анту а) 250 мс або вар?анту б) 80 мс.Коеф?ц??нт техн?чного р?вня для кожного вар?анта реал?зац?? ПП розрахову?ться так (таблиця 4.6): KKj=i=1nKвi,jBi,j,де n – к?льк?сть параметр?в;Kвi– коеф?ц??нт вагомост? i–го параметра;Вi – оц?нка i–го параметра в балах.Таблиця 4.6 – Розрахунок показник?в р?вня якост? вар?ант?в реал?зац?? основних функц?й ППОсновн? функц??Вар?ант реал?зац?? функц??Абсолютне значення параметраБальна оц?нка параметраКоеф?ц??нт вагомост? параметраКоеф?ц??нт р?вня якост?F1(X1)Б340,2080,832F2(X2)А1040,1580,632F3(X3,Х4)А25020,2740,548150020,3610,722Б15040,2741.096100030,3611.083За даними з таблиц? 4.6 за формулою:KK=KТУF1k+KТУF2k+...+KТУFzkвизнача?мо р?вень якост? кожного з вар?ант?в:КК1 = 0,832+0,632+0,548+0,722= 2,734КК2 = 0,832+0,632+1,096+1,083= 3,643Як видно з розрахунк?в, кращим ? другий вар?ант, для якого коеф?ц??нт техн?чного р?вня ма? найб?льше значення.4.4 Економ?чний анал?з вар?ант?в розробки ППДля визначення вартост? розробки ПП спочатку проведемо розрахунок трудом?сткост?.Вс? вар?анти включають в себе два окремих завдання:1. Розробка проекту програмного продукту;2. Розробка програмно? оболонки;Завдання 1 за ступенем новизни в?дноситься до групи А, завдання 2 – до групи Б. За складн?стю алгоритми, як? використовуються в завданн? 1 належать до групи 1(алгоритми оптим?зац?? та моделювання систем ? об’?кт?в); а в завданн? 2 – до групи 3.Для реал?зац?? завдання 1 використову?ться дов?дкова ?нформац?я, а завдання 2 використову? ?нформац?ю у вигляд? даних.Проведемо розрахунок норм часу на розробку та програмування для кожного з завдань.Проведемо розрахунок норм часу на розробку та програмування для кожного з завдань. Загальна трудом?стк?сть обчислю?ться за формулою:ТО = ТР? КП? КСК? КМ? КСТ? КСТ.М,де ТР – трудом?стк?сть розробки ПП;КП – поправочний коеф?ц??нт;КСК – коеф?ц??нт на складн?сть вх?дно? ?нформац??; КМ – коеф?ц??нт р?вня мови програмування;КСТ – коеф?ц??нт використання стандартних модул?в ? прикладних програм;КСТ.М – коеф?ц??нт стандартного математичного забезпечення.Для першого завдання, виходячи ?з норм часу для завдань розрахункового характеру степеню новизни А та групи складност? алгоритму 1, трудом?стк?сть дор?вню?: ТР =90 людино-дн?в. Поправочний коеф?ц??нт, який врахову? вид нормативно-дов?дково? ?нформац?? для першого завдання: КП = 1.7. Поправочний коеф?ц??нт, який врахову? складн?сть контролю вх?дно? та вих?дно? ?нформац?? для вс?х семи завдань р?вний 1: КСК = 1. Оск?льки при розробц? першого завдання використовуються стандартн? модул?, враху?мо це за допомогою коеф?ц??нта КСТ = 0.8. Тод?, за формулою 5.1, загальна трудом?стк?сть програмування першого завдання дор?вню?:Т1 = 90?1.7?0.8 = 122.4 людино-дн?в.Проведемо аналог?чн? розрахунки для подальших завдань.Для другого завдання (використову?ться алгоритм третьо? групи складност?, степ?нь новизни Б), тобто ТР =27 людино-дн?в, КП =0.9,КСК = 1,КСТ =0.8:Т2 = 27 ? 0.9 ? 0.8 = 19.44 людино-дн?в.Склада?мо трудом?стк?сть в?дпов?дних завдань для кожного з обраних вар?ант?в реал?зац?? програми, щоб отримати ?х трудом?стк?сть:ТI = (122.4 + 19.44 + 4.8 + 10.8) ? 8 = 1328.64 людино-годин;ТII = (122.4 + 19.44 + 6.91 + 10.8) ? 8 = 1345.52 людино-годин.Найб?льш високу трудом?стк?сть ма? вар?ант II.В розробц? беруть участь один програм?ст з окладом 12000 грн., один ф?нансовий анал?тик з окладом 16000грн. Визначимо зарплату за годину за формулою:СЧ=МTm?tгрн,де М – м?сячний оклад прац?вник?в;Tm – к?льк?сть робочих дн?в тиждень;t – к?льк?сть робочих годин в день.СЧ=12000+160003?21?8=55.55 грн.Тод? розраху?мо зароб?тну плату за формулою СЗП=Сч?Тi?КД,де СЧ– величина погодинно? оплати прац? програм?ста;Тi – трудом?стк?сть в?дпов?дного завдання; КД – норматив, який врахову? додаткову зароб?тну плату.Зарплата розробник?в за вар?антами становить:СЗП = 55.55? 1328.64 ? 1.2 = 88567.14 грн;СЗП = 55.55? 1345.52 ? 1.2 = 89692.36 грн.В?драхування на соц?альний внесок становить 22%:СВ?Д = СЗП ? 0.22 = 88567.14 ? 0.22 = 19484.77 грн;СВ?Д = СЗП ? 0.22 = 89692.36 ? 0.22 = 19732.32 грн.Тепер визначимо витрати на оплату одн??? машино-години (СМ).Так як одна ЕОМ обслугову? одного програм?ста з окладом 12000 грн., з коеф?ц??нтом зайнятост? 0,2 то для одн??? машини отрима?мо:СГ = 12?M?KЗ = 12 ? 12000? 0,2 = 28800 грн.З урахуванням додатково? зароб?тно? плати:СЗП =СГ? (1+ KЗ) = 28800? (1 + 0.2)= 34560 грн.В?драхування на соц?альний внесок:СВ?Д= СЗП ? 0.22 = 34560? 0.22 = 7603.2 грн.Амортизац?йн? в?драхування розрахову?мо при амортизац?? 25% та вартост? ЕОМ – 20000 грн.СА = КТМ? KА?ЦПР = 1.15 ? 0.25 ? 20000 = 5750 грн,де КТМ– коеф?ц??нт, який врахову? витрати на транспортування та монтаж приладу у користувача; KА– р?чна норма амортизац??; ЦПР– догов?рна ц?на приладу.Витрати на ремонт та проф?лактику розрахову?мо як:СР = КТМ?ЦПР ? КР = 1.15 ? 20000 ? 0.05 = 1150 грн,де КР– в?дсоток витрат на поточн? ремонти.Ефективний годинний фонд часу ПК за р?к розрахову?мо за формулою:ТЕФ =(ДК – ДВ – ДС – ДР) ? tЗ? КВ = (365 – 104 – 8 – 16) ? 8 ? 0.9 = 1706.4,де ДК – календарна к?льк?сть дн?в у роц?; ДВ, ДС – в?дпов?дно к?льк?сть вих?дних та святкових дн?в; ДР – к?льк?сть дн?в планових ремонт?в устаткування; t –к?льк?сть робочих годин в день;КВ– коеф?ц??нт використання приладу у час? протягом зм?ни.Витрати на оплату електроенерг?? розрахову?мо за формулою:СЕЛ ?= ТЕФ? NС? KЗ? ЦЕН =1706,4 ? 0,156 ? 0,85 ? 2,7515= 622,57 грн,(4.16)де NС - середньо-споживча потужн?сть приладу; KЗ - коеф?ц??нт зайнятост? приладу; ЦЕН - тариф за 1 КВт-годин електроенерг??.Накладн? витрати розрахову?мо за формулою:СН = ЦПР?0.67 = 20000? 0,67 =13400 грн.Тод?, р?чн? експлуатац?йн? витрати розрахову?мо за формулою:СЕКС =СЗП+ СВ?Д+ СА + СР+ СЕЛ + СН,СЕКС = 34560 + 7603.2 + 8050 + 1610 + 622.57 + 13400 = 65845.77 грн.Соб?варт?сть одн??? машино-години ЕОМ дор?внюватиме:СМ-Г = СЕКС/ ТЕФ = 65845.77 /1706.4 = 38.59 грн/час.Оск?льки в даному випадку вс? роботи, як? пов‘язан? з розробкою програмного продукту ведуться на ЕОМ, витрати на оплату машинного часу, в залежност? в?д обраного вар?анта реал?зац??, склада?:СМ = СМ-Г ?T,СМ = 38.59 ? 1328.64 = 51272.22 грн,СМ = 38.59 ? 1345.52 = 51923.62 грнНакладн? витрати складають 67% в?д зароб?тно? плати:СН = СЗП ? 0,67,СН = 88567.14 ? 0,67 = 59339.98грн,СН = 89692.36 ? 0,67 = 60093.88 грн.Отже, варт?сть розробки ПП за вар?антами становить:СПП = СЗП+ СВ?Д+ СМ +СН,СПП = 88567.14 + 19484.77 + 51272.22 + 59339.98 = 218664.11 грн,СПП = 89692.36 + 19732.32 + 51923.62 + 60093.88= 221442.18 грн.4.5 Виб?р кращого вар?анта ПП техн?ко-економ?чного р?вняРозраху?мо коеф?ц??нт техн?ко-економ?чного р?вня за формулою:КТЕРj =ККj?СФj,КТЕР1 = 2,734/ 218664.11 = 0,125?10-4,КТЕР2 = 3,643/ 221442.18 = 0,165?10-4.Як бачимо, найб?льш ефективним ? другий вар?ант реал?зац?? програми з коеф?ц??нтом техн?ко-економ?чного р?вня КТЕР2= 0,165?10-4.4.6 ВисновкиУ даному розд?л? проведено повний функц?онально-варт?сний анал?з ПП, який було розроблено в рамках дипломного проекту. Процес анал?зу можна умовно розд?лити на дв? частини.В перш?й з них проведено досл?дження ПП з техн?чно? точки зору: було визначено основн? функц?? ПП та сформовано множину вар?ант?в ?х реал?зац??; на основ? обчислених значень параметр?в, а також експертних оц?нок ?х важливост? було обчислено коеф?ц??нт техн?чного р?вня, який ? дав змогу визначити оптимальну з техн?чно? точки зору альтернативу реал?зац?? функц?й ПП.Другу частину ФВА присвячено вибору ?з альтернативних вар?ант?в реал?зац?? найб?льш економ?чно об?рунтованого. Пор?вняння запропонованих вар?ант?в реал?зац?? в рамках дано? частини виконувалось за коеф?ц??нтом ефективност?, для обчислення якого були обчислен? так? допом?жн? параметри, як трудом?стк?сть, витрати на зароб?тну плату, накладн? витрати.П?сля виконання функц?онально-варт?сного анал?зу програмного комплексу що розроблю?ться, можна зробити висновок, що з альтернатив, що залишились п?сля першого в?дбору двох вар?ант?в виконання програмного комплексу оптимальним ? перший вар?ант реал?зац?? програмного продукту. У нього виявився найкращий показник техн?ко-економ?чного р?вня якост? КТЕР = 0,165?10-4.Цей вар?ант реал?зац?? програмного продукту ма? так? параметри:мова програмування – Python;реал?зац?я в?зуально-граф?чного модуля;введення даних вручну як аргумент.Даний вар?ант виконання програмного комплексу да? користувачу непоганий функц?онал ? швидкод?ю.ВИСНОВОКУ дан?й дипломн?й робот? було розглянуто таку важливу задачу, як пошук шлях?в довжини k у граф?. Для пошуку маршруту м?н?мально? довжини зваженого графа було розглянуто алгоритм Беллмана-Форда, Джонсона, Флойда-Уоршелла, Дейкстри, хвильовий алгоритм, алгоритм пошуку А*. Для алгоритму Дейкстри було наведено приклад. Представлен? алгоритми достатньо добре працюють, але у випадку, коли вс? ваги дор?внюють 1,отрима?мо задачу, яку не можна однозначно вир?шити за допомогою вище описаних алгоритм?в. Ця проблема виника? через те, що на першому кроц? ?сну? безл?ч вар?ант?в вибору наступно? вершини. Тому рац?ональн?ше буде вир?шувати таку задачу з використанням спектра графа.Задача пошуку шлях?в довжини k у граф? було вир?шено з використанням спектрально? теор?? граф?в. Для розум?ння сут? ц??? теор?? було наведено коротк? теоретичн? в?домост? ? прост? приклади матриц? сум?жност?, характеристичного многочлена, спектра графу. Також було розроблено програмний продукт для вир?шення дано? задач?.В якост? практичного прикладу було обрано задачу пошуку м?н?мально? к?лькост? пересадок для того, щоб потрапити з одного м?ста в ?нше, якщо прямого рейсу не ?сну?. У дан?й задач? графом ? схема low-cost ав?ал?н?й, де вершини графу – це м?ста, а ребра – шляхи сполучень м?ж ними. Така задача ? дуже актуальною у наш час, тому що нараз? low-cost ав?ал?н?? користуються величезною популярн?стю, особливо для людей, що часто подорожують або ?здять у в?дрядження. Для подальшого досл?дження ? вдосконалення дано? роботи можливо добавити до вх?дних даних ц?ни б?лет?в або час польоту ? тривал?сть перебування у м?ст? пересадки, щоб знайти не т?льки шлях з м?н?мальною к?льк?стю пересадок, а й найдешевший ? найшвидший вар?анти польоту. ПЕРЕЛ?К ПОСИЛАНЬСпекторський ?. Я., Стусь О. В., Статкевич В. М. Дискретна математика. Зб?рник задач: навч. пос?б. Ки?в: НТУУ ?КП??, 2015. 105 с.Трохимчук Р. М. Теор?я граф?в. Навчальний пос?бник для студент?в факультету к?бернетики. Ки?в: редакц?йно-видавничий центр ?Ки?вський ун?верситет?, 1998. 43 с.Листопад Н. И., Карук И. А., Хайдер А. А. Алгоритмы поиска кратчайшего пути и их модификация. URL: (дата звернення 13.04.2019).Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория применения/ ред. Королюка В.С.; пер. с англ. Строка В.В. Киев: Наукова думка, 1984. 384 с.Efficient Algorithms for Path Problems in Weighted Graphs. URL: (дата звернення 16.04.2019).Cvetkovic D. The Generating Function for Variations with Restrictions and Paths of the Graph and Self-Complementary Graphs. URL: (дата звернення 16.04.2019).Cvetkovic D. Die Zahl der Wege eines Grafen. Beograd: Univ. Beograd, 1970. 210 p.Spectra of Simple Graphs. Owen Jones, 2013. URL: (дата звернення 20.04.2019).Abramson M. Enumeration of Combinations with Restricted Differences and Cospan. Journal of Combinatorial Theory. 1968. May 14. No. 7. P.?162-170. Карта полетов бюджетных авиакомпаний. URL: (дата звернення 25.04.2019). Карпов Д.В. Теория графов. URL: (дата звернення 01.05.2019). Chung R. K. Lectures on Spectral Graph Theory. URL: (дата звернення 05.05.2019). The Shortest Path algorithm. URL: (дата звернення 27.04.2019). Берцун В. Н. Математическое моделирование на графах. Томск: Издательство Том. ун-та, 2013. 88 с. Домнин Л. Н. Элементы теории графов: учебное пособие. Пенза: Издательство Пенз.гос. ун-та, 2007. 144 с. Andoni A. Spectral Graph Algorithms. URL: (дата звернення 25.04.2019). Norman B. Algebraic Graph Theory. Cambridge: Cambridge University Press, 1993. 247 p. Chung R. K. Review of Spectral Graph Theory. URL: (дата звернення 28.05.2019). Mathematical Python. Eigenvalues and Eigenvectors. URL: (дата звернення 10.05.2019). Graph Plotting in Python. URL: (дата звернення 12.05.2019).ДОДАТОК А Л?СТИНГ ПРОГРАМНОГО ПРОДУКТУimport numpy as npimport networkx as nximport matplotlib.pyplot as pltdef grafgen(M): U = [ "{}".format(int(i+1)) for i in range(M.shape[0]) ] G = nx.DiGraph() G.add_edges_from([ (U[i], U[j]) for i, j in zip(*M.nonzero()) ]) pos = nx.spring_layout(G) plt.figure() nx.draw(G, pos, edge_color = 'black', width = 1, linewidths =1 ,\ node_size = 900, node_color = 'pink', alpha = 0.9,\ labels = {node:node for node in G.nodes()}) for i, j in zip(*M.nonzero()): #G.add_edge(U[i], U[j], weight=M[i][j], type="green") nx.draw_networkx_edge_labels(G,pos,edge_labels={(U[i], U[j]): str(M[i][j])}) plt.axis('ofsf') plt.show() def paths(eigs, eigenvalues, k): pathsQuantity = 0 for i in range(len(eigs)): pathsQuantity += (sum(eigs[i])) ** 2 * eigenvalues[i] ** k# for j in range(len(eigs)):# pathsQuantity += a(eigs, eigenvalues, i, j, k) return np.real(round(pathsQuantity))def a(eigs, eigenvalues, i, j, k): a = 0 for v in range(len(eigs)): a += eigs[i,v] * eigs[j,v] * eigenvalues[v] ** k return a#Take matrix size from first row inputfirstRow = input().split(" ")n = len(firstRow)#initialise nxn matrix with zeroesmat = np.zeros((n,n))mat[0] = firstRow#input each row at a time,with each element separated by a spacefor i in range(1, n): mat[i] = input().split(" ")print(mat)eigs = np.transpose(np.linalg.eig(mat)[1])eigenvalues = np.linalg.eig(mat)[0]print('\033[1m'+'Given matrix has such eigenvalues and eigenvectors:'+'\033[0m')print()for i in range(len(np.linalg.eig(mat)[0])): print ('\033[1m'+'Eigenvalue:'+'\033[0m') print(eigenvalues[i]) print ('\033[1m'+'Eigenvector:'+'\033[0m') print(eigs[i]) print() grafgen(mat) print('Paths of which length should be found?')k = int(input())print(paths(eigs, eigenvalues, k))print()print('Matrix in power ' + str(k))np.linalg.matrix_power(mat,k)print('Paths of which length should be found?')k = int(input())print()print('i:')i = int(input())print('j:')j = int(input())print()print(f'The numbers of paths from city ({i}) to city ({j}) lengths ' + str(k))print(np.linalg.matrix_power(mat,k)[i,j])print()# print(f'a({i},{j}):')# print(a(eigs, eigenvalues, i, j, k))ДОДАТОК Б ПРЕЗЕНТАЦ?Я ДИПЛОМНО? РОБОТИ ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download