Глава 17. Свойства и типы графов. иметь дела. В самом деле, для решаемых задач могут быть применены прямые или уни­версальные алгоритмы

иметь дела. В самом деле, для решаемых задач могут быть применены прямые или уни­версальные алгоритмы, подобные программе 17.17, которые, несмотря на то, что время их выполнения в худшем случае экспоненциально, позволяют быстро найти решение (или приемлемое приближение) для многих конкретных примеров соответствующих реальных задач. Мы можем отказаться от использования программы, которая на некоторых вход­ных данных может дать неверные результаты или аварийно завершиться, однако време­нами мы прибегаем к помощи программ, для которых характерно экспоненциальное вре­мя выполнения на некоторых вводах. Мы будем изучать подобного рода ситуации в части 8.

Результаты многих исследований показывают, что многие трудно решаемые задачи так и остаются трудно решаемыми, даже если ослабить некоторые ограничения. Более того, существует множество практических задач, которые мы не можем решить, поскольку ничего не известно о существовании достаточно быстродействующего алгоритма. В этой части книги мы будем относить эти задачи, при столкновении в ними, к категории NP-трудных задач, и будем трактовать этот термин, по меньшей мере, как указание на то, что мы не надеемся отыскать эффективный алгоритм их решения и что не будем предприни­мать попыток найти их решение без применения современных технологий, подобных тем, что рассматриваются в части 8 (за исключением, возможно, применения методов реше­ния " в лоб" для решения небольших задач).

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

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

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

Таблица 17.2. Трудность классификации задач обработки графов_________________

В данной таблице обобщены приведенные в тексте результаты обсуждения относительной трудности решения различных классических задач обработки графов, в процессе которых сравнение задач проводилось с субъективных точек зрения. Эти примеры не только показывают сложность задач, но и то, что сама классификация конкретной задачи может оказаться довольно-таки трудной проблемой.