Глава 19. Орграфы и ориентированные ациклические графы. Транзитивноесокращение. Пусть задан орграф, требуется найти орграф, который име­ет то же транзитивное замыкание и минимальное число ребер среди орграфов этого

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

Ориентированный эвклидов путь. Существует ли на орграфе путь, соединяющий две заданных вершины, который использует каждое ребро орграфа в точности один раз? Эта задача решается довольно просто в силу тех же причин, что и соответствующая задача для неориентированных графов, которую мы рассматривали в разделе 17.7 (см. упражнение 17.92).

Ориентированный маршрут почтальона. Пусть задан граф, существует ли ориентиро­ванный цикл с минимальным числом ребер, который использует каждое ребро графа, по меньшей мере, один раз (при этом он имеет возможность воспользоваться каждым кон­кретным ребром многократно). Как мы увидим в разделе 22.7, эта задача сводится к за­даче выявления потоков с минимальной стоимостью, и в силу этого обстоятельства она поддается решению.

Ориентированный гамильтонов путь. Найти в орграфе простой ориентированный путь максимальной длины. Эта задача относится к числу NP-трудных, однако она легко реша­ется, если граф представляет собой DAG (см. упражнение 19.114).

Односвязный подграф. Говорят, что граф односвязный (uniconnected), если существует самое большее один ориентированный путь между любой парой вершин. Если задан орг­раф и целое число k, определить, существует ли односвязный подграф, имеющий, по мень­шей мере, к ребер. Известно, что для произвольного к эта задача принадлежит к катего­рии NP-трудных.

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

Четные циклы. Определите, содержит ли заданный орграф цикл четной длины. Как было показано в разделе 17.8, это проблема не принадлежит к числу трудно разрешимых, тем не менее, никому не удалось получить алгоритм, который можно было бы исполь­зовать на практике.

Так же как и в случае неориентированных графов, было исследовано великое мно­жество задач, при этом часто определение того, является ли рассматриваемая задача лег­ко или трудно решаемой, сама по себе является сложной проблемой (см. раздел 17.8). Как подчеркивалось на протяжении всей этой главы, некоторые обнаруженные нами факты, касающиеся орграфов, суть выражения более общих математических закономер­ностей, а многие из используемых нами алгоритмов имеют применение на уровнях абст­ракций, отличающихся от тех, на которых мы работаем. С другой стороны, понятие труд­но решаемой задачи говорит нам о том, что в своем стремлении получить эффективные алгоритмы, обеспечивающие эффективное решение тех или иных задач, мы можем столк­нуться с фундаментальными препятствиями. С другой стороны, классические алгоритмы, опи­санные в настоящей главе, имеют фундаментальное значение и находят широкое примене­ние на практике, поскольку они предлагают эффективные решения задач, которые часто возникают в реальной жизни и не могут быть решены каким-либо другим способом.

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