Проходимость по графу

В теории графов существует множество проблем, связанных с обходом графов . Различают проблемы при обходе ребер и проблемы при обходе узлов . Ниже кратко представлены наиболее важные проблемы этого типа.

Проблема круга Эйлера

Проблема цикла Эйлера исследует проходимость ребер графа. Вопрос здесь в том, существует ли цикл, который проходит через все ребра графа ровно один раз. Заметим, что это необходимо и достаточно, если граф непрерывен и все узлы имеют прямые степени . Это свойство можно легко проверить в линейном времени, используя поиск в глубину . Также можно найти такой цикл (если он существует) с линейным временем выполнения.

Проблема почтальона

Проблема китайского почтальона требует кратчайшего пути по всем ребрам взвешенного по ребрам графа . Для графов с кругом Эйлера этот маршрут, очевидно, соответствует кругу Эйлера. В других графах ребра обязательно нужно обходить несколько раз. Длина этих краев должна быть минимальной. Для этого достаточно найти наименьшее совершенное спаривание в графе расстояний всех узлов с нечетной степенью. Это возможно за полиномиальное время. Согласно ребрам этой пары, связанные ребра должны дублироваться в исходном графе. Это создает граф с кругом Эйлера. Теперь достаточно найти круг Эйлера.

Проблема цикла Гамильтона

Задача цикла Гамильтона исследует проходимость узлов графа. Вопрос в том, существует ли круг , содержащий каждый узел графа. Проблема NP-полная . Известны некоторые достаточные и необходимые условия существования цикла Гамильтона, так что можно эффективно проверять, есть ли у некоторых графов цикл Гамильтона.

Проблема продавца

Задача коммивояжера требует кратчайшего обхода всех узлов взвешенного по ребрам полного графа. Эта задача также является NP-полной. С помощью некоторых разумных предположений ( неравенства треугольника ) можно подойти к проблеме хотя бы приблизительно .