worked on the project:
1.Розподілили функції
2.Під час роботи над проектом збиралися і обговорювали алгоритми, після чого реалізовували функції.
У цьому проекті ми виконали наші знання з дискретної математики про графи, зокрема ізоморфність графів, ейлерів та гамільтонів цикли, дводольність графа, а також розфарбування графів. Також, при перевірці на зв’язність, використали пошук вширину.
read_data:
csv file:
| 1 | 3 |
|---|---|
| 1 | 2 |
| 2 | 3 |
| 3 | 1 |
Перша функція read_data читає файл з графом і повертає 2 tupples з словниками, де ключем є вершина, а значенням список вершин, з якими зв'язана вершина-ключ. Один словник- для неорієнтовфного графа, а інший- для орієнтованого. Спочатку ми перевіряємо, чи існує такий шлях до файлу. Якщо шлях існує- читаємо рядки файлу і розділяємо їх за пробілом (file.columns[0].split(' ')), тепер проходимось по кожному рядку. Row перетворюємо в список і беремо перший елемент. Перевіряємо, чи в ключах є перша вершина, якщо немає, то створюємо новий ключ.
ifconnected:
Друга функція ifconnected перевіряє граф на зв’язність і повертає True/False. Ми використовуємо пошук вширину, проходимось по вершинах першого графа і додаємо їх в список, а потім перевіряємо, чи є якісь вершини, яких немає в списку. Спочатку створюємо 2 списки: відвідані вершини і не відвідані вершини. Беремо першу вершину і проходимось пошуком вширину, поки існує черга(поки список не буде пустим). Після закінчення перевіряємо, чи всі елементи відвідані.
Поверне False, бо в списку будудь лише [а,b,c,d], a e,f,g не буде
Третя функція bipartite перевіряє граф на дводольність і повертає True/False. Тут знову використовуємо пошук вширину. Першу вершину записуємо в перший список, другу в другий список і так по порядку, поки не пройдемося по всіх вершинах. На малюнку показаний приклад(1- перший список з вершинами, 2- другий).
поверне False
find euler circuit: Anastasia Beheni
Пошук Ейлерового графу містить 4 функції. Фінальний вивід – список вершин по порядку, в якому треба проходитись. Функції euler_circuit_not_directed і euler_circuit_directed повертають цей фінальний вивід, вони викликають в собі функцію, яка перевіряє чи існує ейлерів цикл і, якщо існує, шукає його. В функціях is_euler_possible_not_directed і is_euler_possible_directed ми перевіряємо, чи існує ейлерів цикл для неорієнтованих і орієнтованих графів. В функції для неорієнтованих графів ми проходимось по всіх значеннях словника(списках вершин) і записуємо в новостворений список довжину цього списку(тобто степінь кожної вершини графа). Після цього перевіряємо, чи кожен з елементів нового списку ділиться націло на 2(тобто є парним), якщо ні, то функція повертає False, якщо так, то True. Щодо функції для орієнтованих графів ми робимо подібну процедуру, але ми перевіряємо, чи кількість дуг, які входять в вершину дорівнює кількості дуг, які з неї виходять. В функціях, де ми вже шукаємо цей ейлерів цикл, ми шукаємо його за таким алгоритмом: “останній прийшов - перший вийде”.
стек: [1,2,3,4,5,3,1] відповідь: [1,3,5,4,3,2,1]
Приклад виводу:
find hamiltonian cycle: Anastasia Senyk, Maksym Koliubinskyi
Функції pre_hamilton і hamiltonian_cycle шукають чи існує Гамільтоновий шлях і, якщо існує, повертає список вершин, по яких треба проходитись, щоб отримати цей шлях. Перша функція шукає, чи існує шлях та повертає True/False відповідно, а також в ній ми створюємо елементи для другої функції. Друга функція приймає наш граф, список, змінну для переходу між ключами і довжину шляху. Проходимось пошуком вшир і після отримання списку перевіряємо, чи початкова і кінцева вершини зв’язані і чи вершина є ключем(особливо важливо для орієнтованих графів). Item(вершину) прирівнюємо до якогось індексу в списку ключа і щоразу рекурсивно збільшуємо цей індекс на 1. Остання рекурсія “повертає назад”.
[1,2,3,4,5] 1 не зв'язана з 5, тому вертаємось назад (покроково) до 2 ([1,2,5,4,3])
Приклад виводу:
Функції isomorphism_of_not_directed_graphs та isomorphism_of_directed_graphs перевіряють, чи два графи (не орієнтовані чи орієнтовані відповідно) ізоморфні. Якщо так, то функції повертають True, ні - False.
В обох функціях спершу перевіряються інваріанти:
-
не орієнтовані графи: кількість вершин, кількість ребер, кількість вершин певного степеня вершини, степені суміжних вершин (для цього використовується окрема функція vertices_check_not_directed, яка перевіряє чи дві вершини мають однаковий степінь та чи степені суміжних їм вершин однакові)
-
орієнтовані графи: кількість вершин, кількість вершин з певним напівстепенем входу і виходу (автоматично перевіряється кількість ребер) Далі за допомогою функцій adjacent_matrix (створює матрицю суміжності графа) та matrix_permutations_comparison (здійснює перестановки рядків і стовпців однієї з матриць і перевіряє чи якась із перестановок співпала з матрицею другого графа. Ця функція повертає True, якщо матриці співпали, False - якщо ні) здійснюємо остаточну перевірку, чи графи ізоморфні.
Function5: Olesia Omelchuk, Sofia Yamkova
За допомогою функцій coloring_decision, coloring_rec та color_check ми перевіряємо, чи поданий граф можна розфарубвати в три кольори. Якщо так, то функція coloring decision повертає список з таплів, де нульовий елемент - це вершина, а перший - її колір.
На початку функції coloring_decision ми створюємо словник, де ключі - вершини, значення - їх колір.
Далі передаємо цей список в функцію coloring_rec, яка також приймає список всіх вершин графа, індекс вершини, яку ми хочемо зафарбувати та сам граф. Функція поверне відповідно True або False, а також в процесі буде змінювати словник з вершинами і їх кольорами. Це рекурсивна функція, яка намагається розфарбувати подану вершину, проходячись по списку з трьох кольорів. Якщо розфарбування вдалось, то функція викликає сама себе і намагається розфарбувати наступну вершину і так далі. Якщо ж не вдалось розфарбувати наступну вершину, то ми повертаємось в рекурсії на крок назад і пробуємо розфарбувати вершину в інший колір. Якщо такого кольору немає, повертаємо False.
За допомогою функції color_check, яка приймає колір, у який ми хочемо зафарбувати вершину, словник з вершинами і їх кольорами та список суміжних вершин, проходячись по цьому списку, перевіряємо чи якась із суміжних вершин часом не зафарбована в цей же ж колір. Функція повертає True якщо ні, і False, якщо так.
Приклад виводу:
Під час виконання комп’ютерного проекту ми поглибили наші знання з дискретної математики з теми графів, а саме: 1.Алгоритм пошуку вшир (перевірка зв’язності та дводольність)
2.Алгоритм пошуку вглиб (Ейлерів цикл)
3.Алгоритм backtracking (Гамільтонів цикл)
4.Перевірка інваріантів ізоморфності графа
А також вдосконалили свої навички з основ програмування, застосовуючи їх на практиці, що пригодиться нам на 2-му курсі.