Изменения
Нет описания правки
=== Постановка задачи ===
{{Определение
|definition='''Эйлеров цикл в графе''' — это путь, проходящий по всем рёбрам графа ровно по одному разу. Задача — для заданного графа найти такой путь.
}}
Задача — для заданного графа найти такой путь. Заметим, что это возможно тогда и только тогда, когда граф связный и степень каждой его вершины четна.
=== Предыдущие результаты ===
Основная мысль — изменить структуру хранения графа. Ниже будет показан алгоритм, работающий за <tex>O(m*log(m))</tex> (ранее лучшим считался результат <tex>O(m^2*log(m))</tex> )
==== Представление графа ====
Пусть <tex>G</tex> — неориентированный связный граф, <tex>V</tex> — множество его вершин, <tex>E</tex> — ребер. Будем хранить ребра в виде списков связности. Пусть <tex>L_v</tex> — множество вершин, соединенных с <tex>v</tex> ребром, <tex>L</tex> — множество всех <tex>L_v</tex>. Для каждой вершины <tex>v</tex> введем также множество <tex>M_v</tex>, хранящее в себе неупорядоченные пары вершин из <tex>L_v</tex>. Обозначим через <tex>M</tex> множество всех <tex>M_v</tex>
==== Фитнес функция ====
==== Операция мутации ====
