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

вершиной? Известно, что эта классическая задача имеет решение, при этом она решает­ся за время, пропорциональное полиномиальной функции от V и Е, однако исследова­телям никак не удается получить быстродействующий алгоритм, пригодный для работы с крупными графами. Эту задачу проще решить при наличии разнообразных ограничений. Например, задача поиска соответствия студентов вакантным должностям в различных об­щественных организациях есть задача двудольного сочетания (bipartite matching): мы имеем два различных типа вершин (студенты и организации), при этом нас интересуют только те ребра, которые соединяют вершину одного типа с вершиной другого типа. Решение этой задачи можно найти в главе 22.

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

Четные циклы в орграфах. Имеются ли в заданном орграфе цикл четной длины? На первый взгляд кажется, что на этот вопрос нетрудно ответить, поскольку нетрудно отве­тить на этот вопрос в случае неориентированных графов (см. раздел 18.4), равно как и на вопрос, имеется ли в орграфе цикл нечетной длины. Тем не менее, в течение многих лет мы никак не можем изучить эту задачу настолько, чтобы хотя бы ответить на вопрос, существует или нет алгоритм ее решения (см. раздел ссылок). Теорема, устанавливающая существование эффективного алгоритма, была доказана в 1999 г., однако метод доказа­тельства настолько сложен, что никакой математик или программист не возьмется за ее реализацию.

Одна из основных тем, рассматриваемых в главе 22, заключается в том, что многие задачи на графах, поддающиеся решению, решаются наилучшим образом за счет приме­нения алгоритмов, которые могут решать весь класс этих задач в общей постановке. Ал­горитмы поиска кратчайшего маршрута (shortest path algorithm), рассматриваемые в главе 21, алгоритмы на транспортных сетях (network flow algorithm), исследуемые в главе 22, а так­же мощный сетевой симплексный алгоритм (network simplex algorithm), рассматриваемый в главе 22, способны решать многие задачи на графах, которые в противном случае пре­вращаются в трудно преодолимые проблемы. В числе таких задач отметим следующие.

Задача распределения. Эта задача, известная еще как задача двудольного взвешенного сочетания (bipartite weighed matching), заключается в том, чтобы найти в двудольном графе совершенное сочетание с минимальным весом. Она легко решается за счет применения алгоритмов, разработанных для транспортных сетей. Известны специальные методы, ко­торые решают данную проблему непосредственно, но при ближайшем рассмотрении было обнаружено их большое сходство с решениями, обеспечиваемыми алгоритмами транспор­тных сетей.

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