ЗВІТ
Теорія графів – один з найважливіших розділів як дискретної математики, так і сфери комп’ютерних технологій загалом. Якщо на мить замислитися, то графи застосовуються у всьому, що нас оточує: від комп’ютерних мереж і аж до уявлення будинків і комунікацій між ними, як вершин і ребер. Саме через їхнє широке застосування командою було вирішено обрати цю тему з-поміж інших.
СТРУКТУРА ПРОЄКТУ
Проєкт складається з 18-ти функцій, зокрема:
• read_graph_from_file для читання csv-файлу та повернення графу у вигляді списку кортежів. • get_adjancy_matrix для отримання графу та повернення матриці суміжності для нього. • get_vertices для отримання графу та повернення списку його вершин.
• find_hamiltonian_cycle для приймання графу та повернення Гамільтонового циклу (чи повідомлення про його відсутність) у формі списку вершин. Гамільтонів цикл – простий цикл, що містить всі вершини графа в точності по одному разу. Для реалізації визначення наявності Гамільтонового циклу використовується алгоритм пошуку з поверненням (backtracking), що полягає в у побудові дерева можливих кроків алгоритму та проходженні по ньому, допоки не буде знайдено відповідний шлях. При невдалих проходженнях дерева непотрібні гілки просто «відрізаються». Для реалізації цього алгоритму написана допоміжна рекурснивна функція hamiltonian_util, яка повертає або цей цикл, або Fasle в разі його відсутності. Функція is_vertex_valid є допоміжною для hamiltonian_util. Вона перевіряє чи може вершина бути наступною в Гамільтоновому циклі. У найгіршому випадку складність такого алгоритму O(n!), де n – кількість вершин графа.
• bipartite_check для отримання графу та перевірки, чи є він дводольним (двочастковим). За теоремою Кьоніга, умовою двочастковості є відсутність у графі циклу непарної довжини. Проте реалізація за таким принципом у контексті комп'ютерного виконання доволі непроста й потребує врахування багатьох нюансів. Тому в модулі використано альтернативний алгоритм – визначення двочастковості методом пошуку ушир та розфарбуванням. Відомо, якщо граф можна розфарбувати в 2 кольори – він двочастковий. Саме це й виконує функція: перевіряє відсутність петель у графі та розфарбовує його двома кольорами. Якщо це можливо – функція поверне True, в іншому випадку – False. Цікаво, що граф з 0 ребрами теж двочастковий, тому така перевірка теж проводиться. Слід зазначити, що такий алгоритм працює тільки для зв’язного графа. Єдиний мінус цієї реалізації – складність О(n^2), де n – кількість вершин графа. Існують й інші ефективніші алгоритми визначення двочастковості, проте, шляхом перевірки на практиці ми виявили, що вони не для всіх прикладів працюють коректно (наприклад, граф цикл з трьома вершинами (трикутник) визначало як двочастковий, а це суперечить умові відсутності циклів непарної довжини тощо).
• print_euler_circuit для приймання графу та виводу Ейлерового циклу, чи інформацію про його відсутність. За теоремою зв’язний мультиграф має Ейлеровий цикл тоді й лише тоді, коли степені всіх його вершин парні. Ця теорема застосовується у функції, де перевіряються степені вершин, тобто спочатку здійснюється перевірка, чи граф має Ейлеровий цикл, а наступним кроком є виведення даного циклу, і він реалізується з використанням пошуку вглиб для обходу графа. Для реалізації даного алгоритму використовуються дві допоміжні функції, перша з яких – convert_to_dict, що конвертує граф як список кортежів, отриманого через функцію read_graph_from_file, у словник, для подальшої роботи із ним, де key – це вершина графа, а value – це вершини, суміжні із нею. Друга допоміжна функція – це deep_first_search, яка працює рекурсивно та безпосередньо повертає шлях Ейлерового циклу у графі, використовуючи пошук вглиб для обходу графа. Спершу основна функція print_euler_circuit перевіряє степені вершин, і у тому випадку, коли у графі нуль вершин непарного степеня, вона викликає функцію deep_first_search та виводить на екран Ейлеровий цикл графа; якщо ж непарні степені у графі є, тоді вона виводить на екран повідомлення «graph doesn’t have an Eulerian circuit».
• check_for_isomorphism для отримання двох графів, перевірки, чи є вони ізоморфними, й повернення булевого значення: True у випадку, якщо графи можна вважати ізоморфними і False – якщо ні. Графи ізоморфні, якщо шляхом перестановки рядків і стовпців матриці суміжності одного графа можна отримати матрицю суміжності іншого графа. Іншими словами, якщо у плоскому вигляді графи однакові, то вони ізоморфні. Цікаво, що проблема ізоморфності графів досі не розв’язана й не існує конкретного алгоритму. Проте на основі знань з курсу Дискретної математики, можемо максимально перевірити на ізоморфність графи, шляхом перевірки трьох інваріантів: кількості вершин, кількості ребер і степені вершин. Відомо, що не існує набору інваріантів для виявлення ізоморфізму, тому вважатимемо порушення інваріанта достатньою умовою неізоморфності. Для перевірки трьох вищезазначених інваріантів реалізовано три допоміжні функції num_vertices, num_edges та vertices_degree, алгоритм роботи яких інтуїтивно зрозумілий. У випадку, якщо всі інваріанти справджуються, що не дає гарантії ізоморфності, викликається четверта допоміжна функція permutations, яка перевіряє чи може бути побудована бієкція між графами. Для цього виконується перевірка виконання умови, що обидві вершини мають суміжні вершини з такими самими степенями. Складність такого алгоритму O(4*n^2).
• colour_graph для приймання зв’язного графа, та повернення його розфарбування у три кольори чи повідомлення про неможливість такого розфарбування. За означенням розфарбування графа G називають таке приписування кольорів (або натуральних чисел) його вершинам, що ніякі дві суміжні вершини не набувають однакового кольору. Для реалізації цього завдання створено дві допоміжні функції, перша check_colour_of_vertex приймає вершину графа та перевіряє за допомогою циклу, чи дана вершина може бути розфарбована у даний колір. Якщо суміжна вершина має даний колір, функція повертає False, а у всіх інших випадках (всі суміжні вершини мають колір, відмінний від даного) – True. Друга допоміжна функція – colour_vertex, що записує у список номери кольорів вершин графа (що не перевищують задане користувачем число), та повертає булеве значення, чи можна розфарбувати граф у дану кількість кольорів. Основна функція colour_graph обробляє дані допоміжних функцій, приймає граф, повернутий функцією get_adjancy_matrix у вигляді булевої матриці, та повертає список кортежів, першим елементом кожного є вершина, а другим – колір розфарбування, якщо розфарбування у три кольори можливе, та повідомлення «Colouring in 3 colours is imposibble» у іншому випадку. Складність даного алгоритму є О(3^n).
РОЗПОДІЛ ОБОВ’ЯЗКІВ У КОМАНДІ:
- Богдан Рубан – підтримка проєкту на GitHub: забезпечення сталості роботи репозиторію, об’єднання фрагментів коду інших учасників команди та внесення синтаксичних правок до коду. Розробка функцій find_hamiltonian_cycle, hamiltonian_util, is_vertex_valid, read_graph_from_file, get_adjancy_matrix та get_vertices.
- Карина Волохатюк – розробка функцій colour_graph та допоміжних до неї check_colour_of_vertex та colour_vertex.
- Роман Кулик – розробка функції bipartite_check та написання звіту.
- Олександра Стасюк – написання звіту й розробка функцій print_euler_circuit та допоміжних deep_first_search та convert_to_dict.
- Владислав Василевич – розробка функції check_for_isomorphism та допоміжних до неї.
ПРОЦЕС ВИКОНАННЯ І ВИКОРИСТАННЯ ПРОЕКТУ
Проєкт було виконано упродовж п’яти днів. Робота була організована засобами онлайн-комунікації. Під час першої зустрічі члени команди ближче познайомилися та обговорювали всі можливі теми проєкту. Результатом першої зустрічі є обрана тема та визначений шлях виконання проєкту з розподілом завдань та встановленими дедлайнами для кожного учасника команди. Одним з проміжних етапів було тестування виконаних модулів на великих об’ємах даних для перевірки коректності роботи тих чи інших фрагментів коду. Відверто кажучи, було виявлено ряд недоліків, які доводилося виправляти в критично короткі проміжки часу. Ще одним етапом реалізації проєкту було написання своїх відгуків і стислого пояснення принципу роботи модулю у відповідному документі – це дало змогу полегшити написання звіту та давало можливість висловити свої думки з приводу виконаної роботи «на папері». Друга зустріч була значно довшою, ніж перша, оскільки мета – пояснити алгоритм роботи завдання, що виконував, усім членам команди. На цьому етапі, були зібрані фінальні версії модулів кожного розробника у репозиторії проєкту на GitHub. Результат – багато запитань, майже дві години обговорення та внесення десятка дрібних правок. В останній день здачі був написаний звіт. З результатом роботи команди можете ознайомитися за посиланням https://github.com/iamthewalrus67/GraphsProject. Проєкт може бути використаний як інтерактивний прототип для створення більш глобального застосунку з вивчення дискретної математики, при підготовці до лекцій/контрольних/іспиту з цього предмету або як інструмент для самоперевірки виконаних завдань.
ВИСНОВКИ
Отже, після виконання роботи над проєктом, можемо вважати, що кожен учасник команди з графами тепер на «ти», а такі поняття, як «ізоморфізм», «дводольність» чи «Ейлерів цикл» не створять труднощів під час складання іспиту. На нашу думку, мети виконання комп’ютерного проєкту досягнуто: члени команди розібралися з вибраною темою й на основі знань з дискретної математики та основ програмування розробили функціональний застосунок, що ще обов’язково стане в нагоді. Усі учасники погоджуються, що виконання проєкту, попри нецілковиту дослідженість заданої тематики, було цікавим досвідом, зазначають, що відсутність будь-яких обмежень стала позитивною несподіванкою, і чекають на схожі форми роботи в наступному семестрі.