В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 16

и. 4.8). Пусть он строит кратчайшее остовное дерево Р с суммарным весом ребер о(Р). Пусть С вЂ” любой гамильтонов цикл. Если выбросить любое ребро из С, то получим дерево Т. При этом о(Р) < о(Т) < о(С). Поэтому о(Р) < Р . Рассмотрим дерево Р и заменим каждое ребро е = (щ,из) в Р двумя ребрами е' = (оьи;) и ев = (иоо1). Тогда получим мультиграф К (граф с кратными ребрами), в котором степень каждой вершины четна. Так как Р— остовное дерево, то мультиграф К связный.

Вылив доказано (см. теорему 4.19), что в любом связном мультиграфе, в котором степени всех вершин четны, существует эйлеров дикл. Применим к К алгоритм с полиномиальной сложностью для построения в К эйлерова цикла С1 (существование такого алгоритма доказано в теореме 4.19). Поскольку пикл С1 прохсвщт по каждому ребру в К ровно 1 рвз, то вес п(С1) = 2о(Р) < 2Рип. Выберем любую вершину о| в С1 в качестве начальной и пусть вершины в Сг встречаются в порядке оп оз, оз,..., щ и иь оььп, оь Пусть выделенное о; встречается в цикле раньше. Тогда заменим последовательность ребер (е; ь ет), (ео ит ы) на ребро (и; и ч+т) в исходном графе.

При этом получим опять цикл, проходящий по всем вершинам. Посхольку веса удовлетворюот неравенству треугольника, то суммарный вес цикла при этом не возрастет. Если в полученном цикле снова есть повторяющиеся вершину, то опять выбросим одну вершину, осуществив "спрямление" . Этот процесс будем повторять до тех пор, пока не получится пикл Сэ без повторюощихся вершин. Тогда цикл Сз будет гамильтоновым и д(Сэ) ~ (Ы(Ст) < 2Е .

В результате мы получаем алгоритм для ЗКНТ с полиномиальной сложностью, который является 1-приближенным. 5.4. Задача о максимальной клике Выше было доказано, что задача КЛИКА является ФР-полной. Рассмотрим теперь следующую задачу МК. Вход: неориентированный граф С. Требуетпсят найти какую-нибудь максимальную по числу вершин клику. Теорема 5.9. Задана о максимальной клике (МК~ являетпся 3Р-трудно й. Докаэательстпео, Пусть А — алгоритм с полиномиальной сложностью для МК, и пусть пара (С, к) — вход для задачи КЛИКА. Применим к С алгоритм А и.

найдем мощность т полученной максимельной клики в С. Если т > 1т, то для пары (С, й) в задаче КЛИКА ответ "да", иначе ответ "нет". Получаем полиномиальный алгоритм для задачи КЛИКА. Так как КЛИКА гт Р-полна, то из существования полиномиальиого алгоритма для МК следует существование полиномиального алгоритма для всех задач из т т Р, то есть МК ХР-трудна.

Прежде, чем исследовать приближенные алгоритмы для МК, докажем лемму. Определение. Пусть С = (У, Е) — неориентированный граф. Определнм граф Сэ = (Уэ,Еэ) как граф с множеством вершин Уэ = У х 1т = 1(и,о)1и б У,и б У) и множеством ребер Еэ = ((им ит), (иэ, иэЦ, где либо иг = из и (им иэ) Е Е, либо (иь из) б Е. Лемма 5.2. Если в С есть клика размера й, тпо в Сэ естпь к тика размера кэ. Если в Сз естпь к тика размера т, где (й — 1)э < т ~ (й~, то в 6' есть клика размера к и в 6э естпь клика размера кэ.

Доказатпельстпво. Пусть в С есть клика С = (иьин Тогда из определения легко проверить, что Сз = 1(и, и) ~и й С, и б С1 — клика в 6а размера (тэ. Обратно, пусть в Сэ есть клика Р размера т. тз Вершинами в Р являю гся пары (и, и) б У . Пусть У = (сси И,..., ип1 и пусть Рт — множество вершин (и,и) из Р, у которых и = иь По опрелелению графа Сг вершины (и,и') и (и,и") смежны в Сг тогда и только тогда, когда (и', еп) б Е. Поэтому вторые координаты всех вершин из Р; образуют клику в С. Если ~Рс ~ > к хотя бы для одного с, то получаем в С клику размера й. В противном случае Щ < й — 1 дпя всех с и, следовательно, число непустых Р; не менее й, так как тп > (к — 1)г. Выберем в каждом непустом Рт любую вершину (иь ив,).

Тах как все эти вершины принадлежат одной клике Р, то все ови смежны. Так как ит ф сз пРи с ф т, то (иост) б Е дла всех пеРвых координат выбранных вершин по определению графа Сг. Поскольку число выбранных вершин тп > к, то получаем клвку в С размера й. Последнее утверждение леммы следует из первого. Следствие 1. Моисность матссимальной клики в Сз имегтп вид йз для нгкопторого натпура съного тс. Следствие 2.

Суитгстпвустп полиномиальный плевритам, котпорый по заданной клике Р мотцностпи тп в графе Сг, где (й — 1)г < тп < йг, стпроитп клику С мотцностпи к в графе С. Пусть тп и тп — мощность клики, когораг строится некоторым алгоритмом, и мощность максимальной клики для падкого входа С. Тогда тп < тп и (тл — пс ! Теорема.

Если длг задачи МК сутцестпвугтп полиномиальный г-приближенный алгоритм для некотпорого О < г < 1, тпо длз МК сутцестпвуетп полиномиальный г-приближенный алгоритпм для всех О < г < 1. Яоказатпельстпво. Пусть для задачи МК для некоторого О < г < 1 имеется полиномиальный г-приближенный алгоритм А„и пусть О < Б < 1. Выберем натуральное г так, что (1 — д) г < 1 — г. Такое г существует, так как 1 — Б < 1. Рассмотрим следующий алгоритм В. Пусть на вход поступает граф С. Строим последовательно Сг, Сс,..., Сг'.

Применяем к Сг" глгоритм А,. Получаем клику Р, в Сг . По клике Р, строим клику Р„т в Сг так, как в доквзательстве леммы. По Р„т аналогично строим клику Рт г в Сг и т.д. до клики Рг в С. Клику Рв выдаем в ответ. Так как т — фиксировано, то алгоритм В полиномиален (см. следствие 2). Докажем, что он является Б-приближенным. Пусть мощность максимальной клики в С равна й. Тогда мощность максвмгльной клики в Сз равна йг по лемме 5.2 (см.

следствие 1). Так как алгоритм А, является е-приближенным, то ~Р„~ ) И (1 — е) . Поскольку (Р; ~~ ) ДЦ для всех з, то ~Ро~ )~ й 'ъ~~ — е > lс(1 — 6). Следовательно, алгоритм В является б-приближенным. Теорема дока- зана. 6. Классы РБРАСЕ и ЭЙДОС Классы Р и А»Р определялись через используемое алгоритмом время работы. Другие классы мы можем получить, если будем рассматривать используемую память. Определение. Класс РЗРАСЕ определяется как класс всех задач распознавания (языков), для которых существует алгоритм, использующий память (например, число ячеек машины Тьюринга), не превосходящую р(п), где и — длина входа и р — произвольный (фиксированный для данной задачи) полинам, Очевидно, что Р С РБРАСЕ. Теорема 6.1. Гг Р С РБРАСЕ.

Локаэательство. Пусть задача распознавания гь(х) б ИР. По определению класса ХР гь(х) представимо в виде: гь(х) = зуОу! < р»(~х!)Йфх, у)), где )х( и (у( — длина слов х и у, р» — некоторый полинам и предикат ь„»(х, у) 6 Р. Покажем, что для вычисления Е(х) существует алгоритм с полиномиальной памятью.

Пусть дан вход х. Вычисляем длину и слова х. Вычисляем р»(п) и отмечаем в памяти зону р»(п), на которой перебираем по очереди все слова у длины < р»(п). Для каждого у вычисляем фх, у). Если при вычислении Я(х, у) хотя бы один раз ответ фх, у) = "истина", то выдаем ответ "да", иначе выдаем ответ "вет". Так как (х! + )у( < и+ р»(п) и С» б Р, то время вычисления 6,»(х,у) для одного у не превосходит некоторого полинома от и. но тогда и используемая память не превосходит полинома от и. Теорема доказана. Лемма 6.1.

Если зона работы машины Тьюринга на входах длины и содерхсит не более р»(п) ячеек, где р»(п) — некоторый полинам, в ленточном алу»авите машины г символов, у машины Й состояний и машина останавливаегпсв на любом входе, то максимальное время работы 6(п) машины на словах длины и удовлетворяет неравенству: 6(п) < 7»ь(ь)р (7») ьь < ~г(ь) где р(п) — некоторый полинам. Яоказательс»пво. Если зона работы машины содержит не более р»(п) ячеек, то при работе машины может порождаться не более гибур»(7») й различных конфигураций, поскольку на ленте можно записать не более г»ь~"~ различных слов, головка может обозревать любую из не более р»(п) ячеек и машина может находиться в любом из к 76 состояний. Поскольку по условию при любом шаше мапцша останавли- вается, то она не может "зациклиться", то есть ксафигурацвя не может повториться.

Поэтому время работы при любом входе не превосходят числа различных конфигураций. При этом 1обз(гт рт(п) ' >т) = рг(п) ' 1обз т'+ 1обэ рт(п) + 1обэ й ~ (р(п), где р(п) — некоторый полянам. Теорема доказана Следствие. Л~ав лтвбот> задачи из Р$РАСЕ с(п) ~( 2~""1, аде р(п) — нвнотпорыб полинолт. Определение. Задача распознавания (язык) Ь называется РБРАСЕ-полясяь если: 1) Ь б РБРАСЕ, 2) к Ь полиномиальво сводятся все задачи из РБРАСЕ. з тверисдение. Если для некотпороб РБРАСЕ-полива' за- дачи сутаестпвуетп алгоритп.н с полинаииальноб сложностпь, тпо Р$РАСЕ = Р.