Задача пошуку шляхів з використанням спектральної теорії графів
Ескіз недоступний
Дата
2019-06
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Дипломна робота містить: 80 с., 6 табл., 30 рис., 2 дод. та 20 джерел.
Задача пошуку шляхів є дуже важливою у нашому житті. Метою даної роботи є створення програмного продукту, який буде обчислювати кількість шляхів фіксованої довжини. Для розв’язку даної задачі використовується спектральна теорія графів. Об’єктом дослідження є шляхи у графі. Предметом дослідження є спектральна теорія графів.
Для наочного прикладу актуальності даної задачі, було сформульовано та розв’язано задачу пошуку маршруту з мінімальною кількістю пересадок. В якості графа виступає схема low-cost авіаліній, де вершини графа – це міста, а ребра – шляхи сполучень між містами.
Для подальшого дослідження і вдосконалення даної роботи можливо добавити до вхідних даних ціни білетів або час польоту і тривалість перебування у місті пересадки, щоб знайти не тільки шлях з мінімальною кількістю пересадок, а й найдешевший і найшвидший варіанти польоту.
Опис
Ключові слова
орієнтовний, неорієнтовний граф, спектр, матриця суміжності, шлях, довжина шляху, length of a way, oriental, unioned graph, spectrum, matrix of compatibility, ways
Бібліографічний опис
Шульженко, Я. О. Задача пошуку шляхів з використанням спектральної теорії графів : дипломна робота … бакалавра : 6.040303 Системний аналіз / Шульженко Яна Олегівна. – Київ, 2019. – 80 с.