Вступ
Читання графа з csv_файлу
Зв'язність
Двочастковість
Гамільтонів цикл
Ейлерів цикл
Ізоморфізм
Розфарбування графа
Висновки
Метою нашого проекту була реалізація функцій, що дозволяють максимально ефективно та оптимізовано виконувати такі операції:
пошук Гамільтонового та Ейлерового циклів у графі, перевірка на дводольність, ізоморфізм,
розфарбування графа у три кольори.
Також, присутня функція для перевірки графа на зв’язність, яка була необхідною для подальшої розробки роботи.
Основою проекту став такий розділ математики, як теорія графів. Під час його створення застосовувалися на практиці знання про властивості графів (дводольність (саме критерій дводольності), зв’язність, ізоморфізм та перевірка його інваріантів, знаходження циклів у графах за певними критеріями чи з використанням алгоритмів тощо).
Розподіл роботи:
- Ахинько Катерина: двочастковість
- Батько Дмитро: Ейлерів цикл
- Кузьма Володимир: Гамільтонів цикл, розфарбування графа, зв'язність
- Колодій Квітослава: звіт
- Костюк Ростислав: ізоморфізм, презентація
Функція read_csv для читання файлу з вершинами графа для подальшої з ними роботи.
Одразу відбувається перевірка орієнтованості графа.
детальніше тут -> input.py
Функція connection для перевірки зв’язності графа.
Спочатку створюємо множину, в якій міститься будь-яка вершина. При ітерації по кожній вершині з цієї множини відбувається перевірка,
чи вона є серед ключів. Якщо так, така пара видаляється зі словника.
Це відбувається поки словник не буде порожнім, тобто між усіма вершинами є шлях, який під час роботи циклу був видалений.
Якщо ж результатом виконання циклу є непорожній словник, це означає, що була така вершина, яка не мала шляху з жодною вже перерахованих, а отже граф незв’язний.
детальніше тут -> connection.py
Функція bipartite для перевірки двочастковості графа.
За критерієм двочастковості, якщо можна кожну вершину розмалювати одним з двох кольорів так, щоб жодні дві суміжні вершини не були одного кольору, тот граф є двочастковим.
Саме таким способом працює ця функція.
Створюємо дві множини - кожна для вершин одного з двох кольорів.
Далі додаємо в одну з множин кожну вершину, суміжні їй в іншу, якщо вони ще не зафарбовані. Для випадку, коли є вершина, яка не зафарбовується під час циклу, є змінна, яка коригує роботу циклу.
Поки її кінцевим значенням не буде False, функція шукатиме всі вершини, які ще не зафарбовані.
детальніше тут -> bipartite.py
Для пошуку Гамільтонового циклу у графі наявні дві функції, search та hamiltonian.
hamiltonian: функція повертає список з ключем зі словника.
search: cаме тут відбуваються усі перевірки для того, щоб визначити, чи граф має Гамільтонів цикл та повернути його, якщо він є.
В основі функції лежить рекурсія. Базовий випадок спрацьовує тоді, коли довжина стаку з вершинами буде на 1 більша за довжину графа: це означає, що цикл знайдено, він повернувся у свою початкову вершину, тому функція завершила свою роботу.
В інших випадках функція продовжує шукати можливі варіанти, щоб продовжити цикл. Єдиними можливими є такі, що є в списку суміжних з активною на даний момент вершиною, проте ще не перебувають у стаці.
Якщо множина з такими вершинами відсутня, можливих варіантів немає, Гамільтонового циклу також. Якщо ж ні, для кожної вершини у списку з можливими функція рекурсивно виконує те саме.
Якщо значенням функції буде не False, вона поверне список вершин, що утворюють Гамільтоновий цикл.
детальніше тут -> hamiltonian.py
Для перевірки наявності Ейлерового циклу - from_dict та fleury.
from_dict: Функція приймає словник та перетворює його у список кортежів з ребрами даного графа.
fleury: Далі для пошуку Ейлерового циклу використовується алгоритм Флері.
Спочатку перевірка: чи взагалі існує Ейлерів цикл. Для цього існує необхідний критерій: степінь кожної вершини повинен бути парним. Якщо список суміжних вершин для кожного ключа в словнику не кратний 2, степінь цієї вершини непарний, циклу не існує.
Наступним етапом є сам алгоритм Флері. Обираємо вершину, яка поки є тимчасовою, обираємо довільне ребро, інцидентне даній вершині, причому міст обираємо тільки тоді, коли немає інших можливостей. Поповнюємо порожній список цим ребром, та видаляємо його з графа. Цей процес закінчується тоді, коли всі ребра графа видалено, і вони всі задають певну послідовність в списку. Функція повертає список вершин у такому порядку, в якому вони утворюють Ейлерів цикл.
детальніше тут -> euler.py
izomorph: Функція для визначення ізоморфізму графів.
Створюються два словника для графів, які потрібно перевірити.
Якщо вони не зв’язні, функція припиняє свою роботу - графи не можуть бути ізоморфними.
Далі відбувається перевірка достатнього інваріанту - якщо кількість вершин різна, графи не ізоморфні.
Наступною є перевірка степенів вершин у обох графах: якщо функція знаходить однакові довжини списків з вершинами, видаляє пару ключ-значення зі словника.
У такому випадку, якщо інваріант справджується, словники повинні залишитись порожніми. Якщо ж ні, існують різні степені вершин й графи не ізоморфні, функція повертає False.
Продовжується перевірка графів. Кінцевим етапом є пошук бієкції множини вершин одного графа в множину вершин іншого.
Створюємо кортежі вершин обох графів. З допомогою модуля itertools та його методу permutations можемо створити n! перестановок елементів другого кортежа.
Щоб перевіряти, чи бієкція правильна, створюється словник першого графа, пара ключ-значення, де ключ - вершина з кортежа, значення - список суміжних з нею з початкового графа 1.
Другий словник буде змінюватись при виборі нової перестановки, його ключами будуть вершини з кортежа, а значення - відповідні списки суміжних вершин з початкового графа 2.
Якщо такі словники рівні, тобто бієкція правильна, функція повертає True.
Якщо після перевірки усіх перестановок така бієкція не знайшлася, графи не ізоморфні.
детальніше тут -> izomorph.py
Функції search, find_coloring
Спочатку зафарбовуємо вершину одним кольором та суміжну їй іншим.
Далі, поки довжина списку з зафарбованими вершинами не буде рівна довжині графа, (це означає, що всі вершини зафарбовані кожна своїм кольором) функція продовжує свою роботу й викликає іншу функцію search, яка відповідає за побудову можливих зафарбувань.
Якщо функція видає помилку, граф неможливо зафарбувати.
Якщо одна з можливих варіацій зафарбування не видає помилки при опрацюванні, вона підходить та надалі використовується функціями, інші варіації видаляються зі стеку.
Якщо в кінці стек порожній, тобто немає кольорів, у які ми можемо зафарбувати вершину, зафарбувати граф неможливо. В іншому випадку, функція повертає пару вершина-колір.
детальніше тут -> 3colors.py
Разом наша команда розробила проект для роботи з графами та аналізу їхніх властивостей.
Було цікаво після лекцій на ці ж теми застосовувати свої знання на практиці, шукати додаткову інформацію для кращого усвідомлення, а також працювати в команді й поєднувати це зі своїми навичками програмування.
Незважаючи на труднощі під час реалізації нашого проекту, ми доклали зусиль, щоб виконати усі поставлені перед нами задачі.