В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 67

граф С) и граф Т представлены на рис. 77.4. Применение поиска в ширину к графу Т дает путь Р =(х», уь хн уз) из Х в Ун. Заменим (выполнение п. 5) в гРафе Т дуги (хз, у»), (у», х1), (хь у») соответ- ственпо на дуги (у.„, хз), (хп уг), (уы х4). Новый граф Т также изображен на рпс. 77.4. В нем Х„=- (х4, хб), Ти = = (Уз, У4). Снова выполнив поиск в ширину пз Х4о получим Х' = (хм х4, хб), 4"' = (у~). Средя олемептов матрицы И', лежащих на пересече77ин строк с номерами 2, 4, 5 и столбцов с номерами 2, 3, 4, 5, находим минимальный. и 5 5 и а и Иа б б 7 а и' г И 7 б и И б 5 7 Рвс. 77.4 5 5 1 1 5 1 и 5 и И а' г бег а 0 4 5 Рве.

77.5 б 0 И Р И и 5 иа г и 4 и г 1 4 5 5 Рис. 77.6 Получим и = И'44 = 2. Результаты последующего применения к графу 44 операции ((хм х4, хб), (у4), 2) и модифицированный граф Т представлены на рис. 77.5. В этом графе имеется путь Р =(хб, уб, хп у,) из Х44 в гм. «Новый» граф Т, полученный в результате выполнения п. 5, также изображен на рис. 77.5. Поиск в ширину в атом графе из множества Х~ = (х4) дает Х' = (хн х4), Г = (771). Находим а = И144 = (.

Результаты последующего выполнения пп. 8, 9 представлены на рис. 77.6. Поиск в ширину из х4 дает Х' = (хм х4, хб), г' = (у1, уб). 363 Находим и = 1ры = 2. Получаем новые матрицу и граф Т (рпс. 77.7). В графе Т имеется (хь уз)-путь Р = =(хо рь хь уз). Изменив этот граф в соответствия с п. 5, получим новый (рпс. 77.7), в котором Хя =- 1'~ = И. Пять его дуг, ведущих «от Х к 1'з, соответствуют ребрам В и и» а' г в 5 ив и г 7 г и г г г 7 5 и и и1 Ряс. 77.7 совершенного паросочетаппя минимального веса в поход- ном графе 6. Вес этого паросочетания равен О+ О+ 1+ +6+3=10.

5 78. Труднорешаемые задачи Как уже говорилось выше, общепринятой является точка зрения, согласно которой алгоритм считается эффективным, если он имеет полнпомиальпую сложность. Именно таковы все алгоритмы, рассмотренные в предыдущих параграфах. Заметим, однако, что за пределами зтпх рассмотрений осталась ббльшая часть важных задач.

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

Б соответствия с этим всякое целое число ссчь О, 1 займет )1о8 ~а~ [ ячеек машинной памяти ([х[— наименьшее целое, не меньшее чем х). Рациональное 364 число, не являющееся целым, будем рассматривать в виде несократимой дроби и представлять з машине как упорядоченную пару целых чисел — числитель и зпаменатель этой дробя. Время вьшолпепгш кзж и й элс»гентарпон опорацин примем равным сумме „.шв леонсой ее операндов в двоичной системе счисления.

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

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

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

Мы пе бучем пз этом останавливаться, поскольку для дальнейгяего нам «остаточно только знать, что оптимизационная задача «не проще» соответствующей распознавательпой. Итак, далее рассматриваются только распознавательные задачи. Определим Р кат класс распоэпавагельп»лх задач, каждая из которых»гоягет быть регпепа некоторым алгоритмом за полиномиальное время. Мы у»гге знаем, что в этот класс входят задачи о минимальных остовах, кратчайших путях 0 папболыпих паросочетанпях (имеются в виду распозпавательпые постановки этих задач, как было условлено). В то же время было названо не- вем сколько задач, прнпадлежвость которых н классу Р не установлена н считается сомнительной.

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

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

Положение иное, если граф С не является гамильтоновым. В атом случае нельзя утверждать даже, что полиномиальное доказательство этого факта существует. Можно, конечно, перебрать все (!С! — 1)! простых циклов длины !С! полного графа, проверяя наждый раз, содержится лп цикл в графе С. Однако подобное доказательство требует времени по крайней мере О((!С! — 1)!), и, следовательно, не является полнномнальным.

Теперь мы хотим определить еще один класс распознавательных задач, включив в него все задачи, обладающие тем свойством, что если вход задачи имеет ответ «да», то сугцествует полиномнальный алгоритм, проверяющий (доказывающий) этот факт. С этой целью дополним мнон«естес обычных операторов, из которых мы составляли алгоритмы, одним особым. Пусть л~ = А о А», ..., А — последовательность, элементами которой служат обычные операторы и один особый, запись которого имеет вид В((ь»»), (ь !»~И, 2, ..., т).

Пусть, далее, 0= д,, дь ..., о„— такой список, что о, = (~ либо д~=1» (1=1, р). После того как .Ф н 0 заданы, действие особого оператора В((п !»)' определим так: в результате Й-го (Й< р) выполнения этого оператора управление передается оператору А~, если д» = 1„и Л», если д, = Ц, а при Й) р вычисления прекращаются. Итак, последовательности операторов,Ф и списку 0 ста- 388 вится в соответствии обычный (детерминированный) алгоритм.

Этот алгоритм будем обозначать через М«, чтобы подчеркнуть наличие двух компонент ч» и (). Список () будем прп этом называть угадывающей последовательностью, а последовательность 4 — недегерминированным алгори«мои. Подчеркнем особо, что недеторминироьапный алгоритм пе является алгоритмом, а представляет собой чисто абстрактную конструкцию. Будем говорить, что педетерминированпый алгоритм ,Ф решает риспознавательную вида«у за полиномиальное время, если найдется такой полипом р(п), что выполняется следующее условие: каждый вход длины и этой задачи имеет ответ «да» тогда и только тогда, когда для него существует такая угадывающая последовательность Ч, что алгоритм Ф«, будучи примененным к этому входу, останавливается, сообщив ответ «да», и время его работы не превосходит р(п). Заметим, что согласно этому определению каждому входу с ответом «да» должен ставиться в соответствие свой алгоритм э«:«.

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