Пути, цепи, циклы.

маршрут

путь (цепь) – рёбра не могут повторяться

простой путь – рёбра и вершины не могут повторяться

Элементарная дуга – это цепь, в которой каждая вершина встречается только один раз

В простом графе можно описывать путь только вершинами

Замкнутый маршрут – в котором начальные и конечные вершины совпадают

Замкнутый путь – ребра не повторяются

Цикл – маршрут у которого начальные и конечные вершины совпадают и рёбра, и вершины не повторяются.

Обхват – длина минимального цикла, если в графе циклов нет – обхват = бесконечности

Обхват графа больше 3 – граф свободный от треугольников

Изолированная вершина циклом не является

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

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