1)Читання графу з файлу(Вус Стас): Приймає csv файл, де в рядку є пара зв’язаних вершин, також приймає прапорець oriented, коли вона False функція сплітує кожну лінійку і робить з неї список з двох елементів, а потім створює відповідні вершини в словники і вкладає пов’язані вершини до значення вершини у словнику.

2)Гамільтоновий цикл(Слаблюк Назар): Приймає словник, ключами якого є вершини графа, а значеннями - списки вершин, з якими зʼєднана вершина, до якої стосується це значення. Створено допоміжну функцію для пошуку гамільтонових шляхів, адже якщо гамільтоновий шлях є для всіх вершин, то існує і гамільтоновий цикл. Допоміжна функція приймає граф, його величину(для контролювання довжини шляху), початкову точку, та шлях(опціонально), який був до цього. Допоміжна функція додає всі гамільтонові шляхи до списку, потім перевіряє чи є шляхи зі всіх вершин графа, якщо так- то повертає список, з порядком вершин, як вони йдуть в циклі, починаючи з 1 вершини в графі. Якщо ж немає гамільтонового циклу, але є шляхи, то функція поверне 'no hamilton cycle but this graph has hamilton path or pathes: і гамільтонові шляхи. Якщо на того ні того немає- то поверне текст 'miss input, try again but with the new graph'.

3)Ейлеровий цикл(Пясковська Анна) Ця функція знаходить ейлерів цикл в графі, який працює як для неорієнтованих, так і для орієнтованих графів. Функція eiler_cycle спочатку перевіряє звязаність графу за допомогою пошуку в глибину (DFS), парність степенів кожної вершини і, якщо граф не з'єднаний, повідомляє про відсутність ейлерового циклу. Для неорієнтованих графів функція перевіряє парність степенів вершин та використовує модифікований DFS для знаходження циклу. Для орієнтованих графів визначає початкову вершину та використовує DFS для знаходження циклу. Після знаходження базового циклу, функція відновлює його, додаючи необхідні підцикли.

4)Перевірка на двочастковість(Мокра Ангеліна) Функція bipartite_check перевіряє чи граф є дводольним. Алгоритм базується на ідеї BFS обходу графу та призначення двох кольорів вершинам, переконуючись, що жодні дві сусідні вершини не мають однакового кольору. Для призначення кольорів кожній вершині використовується масив color, кожній вершині надаються значення: 0 початкове для нерозфарбованої вершини, -1 та 1 для позначення двох кольорів. Спершу переконуємося, що всі вершини присутні в графі, включаючи ті, що можуть мати порожні списки суміжних вершин, далі сортуємо ключі(всі вершини графа) словника по кількості суміжних вершин від більшого до меншого. Далі за алгоритмом BFS проходимось по графу та перевіряємо на дводольність: Призначаємо початковий колір вершини, а потім перевіряємо колір сусідніх вершин. Якщо вершина та її суміжна мають однаковий колір, граф вважається не дводольним, і функція повертає False. Якщо суміжна вершина не розфарбована, надаємо їй протилежного кольору. Якщо всі вершини успішно пройдено, і граф виявився дводольним, функція повертає.

5)(Артем Крутько) Функція izomorf_check передбачає, що вона буде викликана для 2-ох графів. Перевіряє, чи є ці графи ізоморфними. Загалом не існує конкретного підходу, який би точно перевіряв, чи є графи ізоморфними, але я використав основні алгоритми перевірки:

1 перевірка: Це є перевірка, чи у двох графах є одинакова кількість вершин

if len(graph1) != len(graph2):
    flag = False

2 перевірка: Це є перевірка, чи у двох графах є одинакові степені вершин

Створюємо нові словники, у яких ключ - це вершина графа, а значення - кількість ребер, які виходять з неї.

dct_len_1 = [len(value) for value in graph1.values()]
dct_len_2 = [len(value) for value in graph2.values()]

if sorted(dct_len_1) != sorted(dct_len_2):
    flag = False

3 перевірка: Це є перевірка, чи у двох графах є однакова кількість ребер

Створюємо нові списки, у які добавляємо кортежі з вершиною і суміжною вершиною.

edg_lst_1 = []
edg_lst_2 = []

for key, value in graph1.items():
    for i in value:
        edg_lst_1.append((key, i))

for key, value in graph2.items():
    for i in value:
        edg_lst_2.append((key, i))

if len(edg_lst_1) != len(edg_lst_2):
    flag = False

4 перевірка: Це є перевірка, чи у двох графах є або немає ейлерового цикла

Створюємо нові списки, у які добавляємо True, якщо степінь вершини парна, False, якщо непарна. Потім змінній присвоюємо True, якщо у цих списках всі елементи True, але якщо хоча би 1 False, тоді False

lst_el_1 = all([i % 2 == 0 for i in dct_len_1])
lst_el_2 = all([i % 2 == 0 for i in dct_len_2])

if lst_el_1 != lst_el_2:
    flag = False

5 перевірка: Це є перевірка, чи у двох графах є або немає ейлерового цикла (якщо граф орієнтований)

Створюємо нові змінні зі значенням 0, і якщо степінь вершини виходить непарне число, тоді добавляємо до цієї змінної +1. Потім, якщо ця змінна дорівнює 2, тоді перевіряємо, чи друга змінна також дорівнює 2.

count1 = 0

for item in dct_len_1:
    if item % 2 != 0:
        count1 += 1

count2 = 0

for item in dct_len_2:
    if item % 2 != 0:
        count2 += 1

if count1 == 2 and count2 != 2:
    flag = False

if count1 != 2 and count2 == 2:
    flag = False

6)Розмальовування графів(Вус Стас): Функція приймає словник, де ключем є вершина, а значенням масив зі всіма пов’язаними з даною вершиною вершинами. У функції є масив visited, куди вносяться всі відвідуванні вершини, connect, де знаходяться пов’язані вершини. Існує цикл while, де умовою виходу є рівність довжини visited і кількості вершин Цикл проходиться по вершинах і перевіряє чи є якісь елементи пов’язані з даною вершиною. Якщо нема, то додає, і так доки не обійде всі вершини.