Часть 5. Алгоритмы на графах. Неориентированные графы

E T I?

Неориентированные графы

Связность *

Полная связность *

Эвклидов цикл *

Гамильтонов цикл *

Двудольное сочетание *

Максимальное сочетание *

Планарность *

Максимальная клика *

Раскраска в 2 цвета *

Раскраска в 3 цвета *

Кратчайшие пути *

Самые длинные пути *

Вершинное покрытие *

Изоморфизм *

Орграфы

Транзитивное замечание *

Сильная связность *

Цикл нечетной длины *

Цикл четной длины *

Взвешенные графы

Минимальное остовое дерево *

Задача коммивояжера *

Сети

Кратчайшие пути (неотрицательные веса) *

Кратчайшие пути (отрицательные веса) *

Максимальный поток *

Распределение *

Поток минимальной стоимости *

Обозначения:

Е Легкая - известен эффективный классический алгоритм решения (см. справку)

Т Решаемая - решение существует (трудно получить реализацию)

I Нерешаемая - эффективное решение неизвестно (NP-трудная задача)

? Неизвестно, существует ли решение

Что касается класса легких алгоритмов, то мы применяем принцип сравнения алго­ритмов с различными характеристиками для худших случаев и пытаемся дать оценку про­изводительности алгоритма путем анализа и применения эмпирических критериев. В слу-