Комп'ютерний проєкт. Звіт
-
Розподіл Читання графу з файлу - Шергіна Олександра Пошук Гамільтонового і Ейлерового циклів в графі - Котлярчук Оксана Перевірка графа на дводольність - Лисик Лев-Федір Перевірка двох графів на ізоморфність - Пахолок Віктор Розфарбування графа - Сай Божена
-
Хід роботи Для реалізації цього проєкту ми розробили декілька функцій. Ось детальніший опис кожної з них:
- Читання графу з файлу Дана функція читає csv-файл, в якому записаний граф у вигляді списку вершин, і повертає його у вигляді словника. У цьому словнику кожній вершині відповідає список суміжних з нею вершин.
- Пошук Гамільтонового циклу Функція почергово додає вершини графа у список, допоки існує спосіб перейти у наступну, без повторення. Якщо такого способу немає, то функція повертається на крок назад, і йде іншим шляхом. Закінчує роботу,коли у списку є всі вершини і остання з них суміжна з початковою.
- Пошук Ейлерового циклу Перевіряє графік на наявність ейлерового циклу та на орієнтованість. Тоді запускає рекурсивну функцію засновану на алгоритмі Флейрі: перевіряє чи є ребро мостом, або єдиним суміжним; додає його у список ребер і переходить у наступну вершину. У самому графі видаляється зв’язок між вершинами, який уже був пройдений. Після цього алгоритм проходиться по усіх ребрах і додає початкову вершину кожного у фінальний список.
-
Перевірка графу на дводольність Для виконання цієї задачі ми створили дві функції - одну складнішу і другу простішу. Перша функція шукає розбиття множини вершин графа на дві підмножини, вершини яких не з’єднані між собою. Друга функція перевіряє критерій двочастковості:
Для того, щоб граф був двочастковим, необхідно й достатньо, щоб він не мав простих циклів із непарною довжиною.
Для цього ми створили допоміжну функцію, що шукає та повертає всі цикли у графі (вона також знадобилась нам при розробці наступних функцій).
- Перевірка двох графів на ізоморфність Ця функція приймає два графи у вигляді словників та перевіряє їх на ізоморфність. Вона перевіряє всі можливі інваріанти: кількість вершин та ребер, степені всіх вершин та суміжних з ними, довжини циклів (тут ми використали вищезгадану додаткову функцію). Якщо хоч один з цих пунктів у графів різниться, функція видає False, якщо ні - True.
- Розфарбування графа Функція розфарбовує граф у три кольори, так аби дві сусідні вершини не мали однакового кольору. Основна робота полягає у тому що функція приймає вершини і його суміжні вершини і підбирає колір який ще не був використаний.