В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114530), страница 14
Текст из файла (страница 14)
По лемме 4.28 гамильтонов цикл ИР не проходит по крайней мере по одному из основных ребер подграфа Н . Пусть этому ребру соспоставлен литерал б с переменной хь Если 1 = хо то это ребро соединено а-графом с еР, если б = хи то с еб. Так как по данному ребру бз цикл И' не проходит, он должен проходить по е;, если й = хн и по ео, если 1 = йо Из выбора 1~ получаем, что в любом случае 1(у) = 1 и, следовательно, РЗЯ = 1. Поскольку это верно для всех у, то К(у) = 1, то есть КНФ К выполнима.
Обратно, пусть КНФ К выполнима и К(у) = 1, где у ('Гь, Ъ) . Проведем пикл И по полграфу Сз так, чтобы для каждого 1 = 1, 2,..., и он проходил по ео, если у, = О, и по е~, если у; = 1. Тогда по свойствам а-графов цикл И' не может проходить по основному ребру подграфа Сы которому приписан литерал 1, такой, что $( у) = 1, и обязан проходить по основному ребру, если ему приписан литерал г, такой, что 1(7) = О. так как Рв( г) = 1 для всех 1', то в каждом подграфе Н существует хотя бы одно ребро, такое, что для соответствующего ему литерала 1, выполняется гЯ) = 1. Следовательно в хаждом подграфе Н, существует одно, два или три основных ребра, таких, что цикл И' не должен по ним проходить, и должен проходить по остальным основным ребрам.
По лемме 4.28 в каждом Н, можно построить гамильтонову цель, удовлетворяющую этим требованиям, и в целом в графе Сь можно построить гамильтонов цикл. Лемма доказана. Проверить, является ли слово и б А' З-КНФ, и построить граф Св, если а = К вЂ” зто З-КНФ, можно за полиномиальное (от длины а) время. Поэтому мы получаем полиномиальное сведение задачи 3-ВЫП к задаче ГЦ. Так как задача 3-ВЫП ХР-полна и ГЦ й МР, то и задача ГЦ "гУР-полна.
Теорема 4.18 доказана. Интересно, что следующая близкая задача оказывается полиномигльной. Определение. Мультиграфом называется граф, в котором разрешены кратные ребра (то есть ребра, соединяющие олпу и ту же пару вершин). Определение. Эйлеровым цшслом в мультиграфе называется дилл, проходящий по каждому ребру ровно один раз и проходящий по всем вершинам. Теорема 4.19. Эйлеров цикл в мультиграфе сушествует тогда и только тогда, когда мультиграф связный и степени всех вершин в мультиграфе четны, причем суи4ествует полиномиальный алгоритм, который, в случае, когда мультиграф связный и степени всех вершин в мультиграфе четны, строит эйлеров цикл. Яокаэательство. Необходимость следует из того, что если эйлеров цикл проходит через вершину Й раз, то степень этой вершины должна равняться 2х. Пусть теперь все степени четны. Выберем любую вершину о1 н будем строить путь по ребрам, используя любые еше не пройденные ребра, до тех пор, пока не окажемся в тупеке.
Так как степень любой вершины четна, то тупик не может образоваться ни в одной вершине, отличной от оь В результате получим некоторый цикл. Если этот цикл не содержит всех ребер мультиграфа, то, в силу связности мультиграфа, существует на построенном цикле хотя бы одна вершина оз, которая инцидентна не пройденному ребру. Тогда рассмотрим уже построенный цикл, как начинающийся и кончающийся в вершине оь После чего опять продолжим построение цикла иэ вершины оз.
Этот процесс будем продолжать рекурсивно, пока в цикл не войдут все ребра. Описанный алгоритм, очевидно, полиномиэлен относительно числа ребер. 5. Задачи оптимизации В практических приложениях часто возникают задачи оптимизапии, которые имеют следующую структуру. Каждому входу х сопоставляется некоторое множество уу допустимых решений. Задан функционал Р: У, — у Н, где Н вЂ” множество действительных чисел. Требуется найти шш Р(у) или шах Р(у) уеУ уеУ, или то допустимое решение ув, на котором достигается оптимальное значение функционала. Если функционал Р вычисляется быстро, то найдя оптимальное допустимое решение, мы можем легко получить и оптимальное значение фувкпионвла Р„.
Обратное, вообще говоря, не ясно: может суп|ествояать быстрый алгоритм, который находит Р не находя оптимальною решения, С каждой задачей оптимизации можно связать задачу распознавания. При этом на вход кроме х подается число я и спрашивается, верно ли, что Р„< я (или Р > Й). На практике для решения задач оптимизации часто используются алгоритмы, называемые жадными или градиентными. В таких алгоритмах допустимое решение строится постепенно по шагам, причем на каждом шаге делается выбор, оптимальный для данного шага. Как мы увидим ниже, такой поиход не всегда приводит к оптимальному решению в целом. Однако для следующей задачи он всегда дает оптимальное решение. Напомним, что деревом называется любой неориентированный связный граф без циклов.
Подграф Су графа 0 называется остовным, если Су содержит все вершины графа С. Через К„обозначается полный граф на и вершинах, то есть граф, в котором каждая пара вершин соединена ребром. 5.1. Задача о кратчайшем остовном дереве Вход: неориентированный полный граф К„, в котором для любого ребра е задан вес уо(е) > О.
Требуетася: выделить в К„остовное дерево с минимальной суммой весов ребер. Замечание. На практике это означает требование построить сеть минимальной стоимости, связывающую и данных объектов. . Напомним некоторые факты из теории графов ]3]. Утверждение 1.
Если в графе с и вершинами число ребер а < и — 1, куо граф ке связный. Утверждение 2. Если е графе С нети циклов и а = и — 1 (д, и — число ребер и вершин), тпо С вЂ” дерево. Утверждение 3. В любом дереве с п еершинами числа ребер д = и — 1. Утверждение 4.
Если к дереву добавить новое ребро на тпех все аертлиная, тпо абраэуетпся ровно 1 цикл. Рассмотрим следующий алгоритм для задачи о кратчайшем остовном дереве. 1. Взять любое ребро ет минимального веса. 2. Рекурсивный шаг: пусть уже выбраны ребра ем ез,..., е . Если тп = и — 1, то остановиться. Иначе, среди всех ребер, не образующих циклов с ем ез,..., е, взять ребро е ьт минимального веса, и повторить рекурсивный шаг. Алгоритм делает меньше, чем п итерапий и на каждой просматривает менее, чем из ребер. 11ри этом, если из ребер емез,...,еть сформировать связные компоненты, то 'тот факт, что е .ьт не образует с ними диклов, эквивалентен тому, что концы ребра е„,ьт не лежат в одной связной компоненте.
Это свойство легко проверяется. Таким образом, алгоритм может быть реализован с лоливомиальным от и числом операций, включающих поиск информации и сравнение весов. Теорема 5.1. Описанный алгаритпм корректпно строит минимальное остпоеное дерево. Нокаэатпельстпво. 1) Докажем, что если тп ( п-1, то существуют ребра, не образующие циклов с емез,...,ен.
Если тп < п — 1, то подграф, состоящий из всех вершин и ребер ем ез,..., е,„, не связный 1по утв. 1). Если взять любое ребро, соединкюшее две вершины из разных компонент этого псэтграфа, то циклы не образуются. Такам образом, алгоритм проработает до тп = и — 1. 2) Прн остановке тп = и — 1 и ребра емез,...,е не образуют циклов. Тогда (по утв. 2) они образуют остовное дерево. 3) Пусть алгоритм строит остовное дерево О. Докажем, что Ю вЂ” минимальное остовное дерево. Рассмотрим все минимальные остовные деревья, н пусть Т вЂ” минимальное остовное дерево, имеющее с Ю наибольшее число общих ребер. Докажем 1от противного), что Х) = Т.
Допустим, что Т ~ .О. Так как и в Т и в О и — 1 ребро (утв. 3), то в О есть ребра, не входящие в Т. Пусть в алгоритме ребра дерева Р появлялись в порядке: ем ез,...,е„т и пусть ребра енез,.,,,еь принадлежат дереву Т, а еььт ф Т. Рассмотрим граф Н = Тст (еьы). В Н имеется единственный дикл С (утв. 4), содержащий еьть Так как Р 66 не содержит цикпов, то в С есть хотя бы одно ребро е такое, что е у Р. При атом е б Т.
Рассмотрим Нь = Н 1 (е1. Граф Нь — связный и без циююв, то есть Нь — остовное дерево. Пусть ш(Нь) и ш(Т) — суммы весов ребер в Нь и Т. Так как Т вЂ” минимапьное остовное дерево, то ш(Нь) ) ш(Т) и ш(Нь) = ш(Т) + ш(еы.ь) — ш(е) ) ш(Т). Отсюда ьо(е) < ш(еьвь). Поскопьку е й Т и еь,еа,еь принадлежат дереву Т, то е не образует циклов с еь, ез,..., еь Если бы было ш(е) < ш(еьвь), то на й + 1-м шаге алгоритма не могло бы выбираться ребро еьвь Значит ьо(е) = ш(еь+ь) и ш(Нь) = ш(Т). Получаем, что Нь — также минимальное остовное дерево, но имеющее с Р на 1 общее ребро больше, чем Т с Р.
Это противоречит выбору дерева Т. Из полученного противоречия следует, что должно быть Р = Т, то есть Р— минимальное остовное дерево. Теорема доказана. 5.2. Приближенные алгоритмы Задача о минимальном вершинном пскрытии (МВП). Будем говорить, что вершина и покрывает ребро е, если она явпяется одним из концов ребра е. Подмножество А С Ъ' вершин графа С = (У,Е) называется вершинным покрытием, если вершины из А покрывают все ребра из Е. ' Вход: неориентировапвый граф С = (Ъ', Е). Требуегася: найти вершинное покрытие (ВП) минимальной мощности.
ььлКадныйв алгоритм для МВП. На каждом шаге выбирается любая вершина, покрывающая наибольшее число еще ве покрытых ребер. Апгоритм останавливается, когда все ребра покрыты. Легко показать, что "жадный" алгоритм для МВП имеет попиномиапьную сложность. Теорема 5.2. Яля "жадного" а ьгоритма длл задачи ь1ьВН для любого натурального и существует граф Св такой, что при входе С„выпо ьняется неравенствоь Еалг > Еотн(1п ьь — 1п 2 — 1), где г' — число вершин в покрытии, которое строит алгоритм. 67 Докаэагпеяьспзео. Включим в граф С„сначала вершины ип им..., и„, между которыми не будет ребер.
Палее выделим из вершин ип из,..., и„["-] непересекаюп1ихся пар [одна вершина может не участвовать в парах) и каждую пару соединим с новой вершиной, при этом получим новые вершины оп оз,..., о~31 степени 2. Затем выделим нз вершин ип ии..., и„[з) непересекающихся троек и каждую тройку соединим с новой вершиной [степени 3). Палее аналогично выделим непересекающиеся четверки, пятерки вершин и т.д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
