Эйлеров цикл. Определение, условие существования, алгоритм нахождения.

Эйлеров цикл – цикл который содержит в себе все рёбра графа

Для того чтобы эйлеров цикл существовал, граф должен быть связным и степень всех вершин в графе должны быть чётные (при входе в одну вершину, ты должен из неё выйти по другому ребру)

Алгоритм:

Из любой вершины выйти и обойти граф вернувшись в эту же вершину, если остались непрядёные ребра, нужно найти вершину, принадлежащую уже пройдённому циклу, но у которой существуют ребра, которые ещё не пройдены и так до тех пор, пока все рёбра графа не будут исчерпаны.

6. Содержание

   • Графы. Основные определения. Соотношения между количеством ребер и количеством вершин.
   • Изоморфизм графов. Примеры.
   • Пути, цепи, циклы.
   • Связность графов.
   • Эйлеров цикл. Определение, условие существования, алгоритм нахождения.
   • Гамильтонов цикл. Определение. Задача о коммивояжере.
   • Деревья.
   • ОстОвное дерево. Алгоритм Крускала.
   • Алгоритм поиска кратчайшего пути в графе.
   • Клики. Алгоритм поиска клик.
   • Раскраска графов. Алгоритмы раскраски.
   • Генерация случайных графов.