Основы дискретной математики В.А. Осипова (552659), страница 26
Текст из файла (страница 26)
ЗДЕСЬ сх = тПШ(3, 4, 4, 3, 5). Изменим поток, увеличив его величину на 3 (рис. 4.33, э)). Больше увеличивающих цепей нет. Следовательно, построенный поток является максимальным; его величина равна 11. 4.7.3. Паросочетания в двудольньтх графах Понятие максимального потока можно использовать для решения еще одной задачи для оттределенного вида графов — двудольных. Дв!тдольныл4 графом называется неориентированный граф С =< Ъ; т,т > такой, что множество его вершин можно разбить на два непересекающихся подмножества р = И' ! ! Я (И' Гт 2 = т7)), причем для каждого его ребра (ю, э) Е ю Е Ит, я Е У.
Двудольный граф обозначаем С = (Ит, У, Ц). На рис. 4.34 изображен двудольный граф с множеством вершин (6!) из~ из) т-! (и4~ ю5~ иб). Наросочетанием в неориентированном графе С =< Ъ; Я > называется произвольное множество ребер М С Я такое, что никакие два ребра из М не инцидентны одной вершине. Для каждого ребра (ю, г) Е М, где ю, е е И, говорят, что М сочетает И' с х. Наибольшее паросочетание — это паросочетание с наибольшим числом ребер. Пример 4.20.
(Задача о назначениях). На р должностей У = (дт д2, ", др) можно назначить р работников = (ит, и2, ..., ир). Квалификация каждого работника позволяет ему занимать лишь некоторые из должностей. Возможно ли произвести назначение таким образом, чтобы каждый работник занимал должность в соответствии со своей квалификацией? Если обозначить через Гит множество должностей, которые может занимать работник, то задача сводится к нахождению паросочетания в двудольном графе (Ъ; У, Г). Задачу нахождения наибольшего паросочетания в двудольном графе можно свести к нахождению максимального потока в некоторой транспортной сети. Пусть Н = (И~, Я, Я) — произвольный двудольный граф. Построим сеть С =< Ъ; Г > с множеством вершин Ъ = (ит, иа) т.! И' !! Я (здесь ит — исто шик, ип — сток сети) и множеством дуг Г = (< ит, ю > ~ ю Е Ит) С (< и, и„> ~ л Е Е Я)с4(< ю, я > !(ю Е И")бе(я Е Я)й((ю, е) Е се)).
Пропускную способность С для каждой дуги считаем равной 1. Существует взаимно однозначное соответствие между паросочетаниями в Н и нуль-единичными потоками в транспортной сети С, причем наибольшему паросочетанию соответствует максимальный поток ут, и ребро (ю, и) Е М тогда и только тогда, когда ут(ю, е) = 1. Пример 4.21. На рис.
4.35 представлены транспортная сеть, соответствующая двудольному графу, изображенному на рис. 4.34, а также максимальный поток в этой сети. Соответствующее максимальное паросочетание содержат следуюпттте ребра двудольного графа: < ит, иб ), < и2, иб ), < из, и4 >. п2 Рис. 4.34. з ! пб Рис. 4.35. 155 з 5 Уг 6 з 3 ~~6 ритмов 154 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Задачи и упражнения 1.
Найти максимальные потоки в следующих транспортных сетях. 4.8. 0 вычислительной сложности алго- Методы решения многих задач математики носят алгоритмический характер. Как правило, для задач, имеющих практический интерес, ищут именно разрешающие алгоритмы. Исследуя задачи на дискретных конечных математических структурах можно найти комбинаторные алгоритмы для их решения, например, с помощью некоторого процесса перебора. Однако при этом число шагов алгоритма быстро растет с увеличением размерности задачи, и последняя становится практически неразрешимой.
Поиск эффективных алгоритмов для решения задач дискретной математики привел к одной из важнейших ее проблем — к решению вопроса о возможности исключения перебора вариантов в комбинаторных алгоритмах. В самом широком смысле эффективность алгоритма связана со всеми вычислительными ресурсами, необходимыми для его работы. Однако обычно под наиболее эффективным понимается наиболее «быстрый» алгоритм.
Есть целый ряд задач, представляющих практический интерес, для которых, по-видимому, не существует эффективных алгоритмов, а про имеющиеся разрешающие алгоритмы можно 4.8. О вычислительной сложности алгоритмов сказать, что они неэффективны даже при реализации на значи- тельно более мощных, чем современные, вычислительных ма- шинах. Оценка сложности алгоритмов и создание эффективных алгоритмов — одна из важных задач современной дискретной математики. Мы будем оценивать алгоритмы лишь по временной сложности. Не приводя здесь точных понятий, заметим, что время работы алгоритма можно выразить в виде функции от «размеров» входных данных, требуемых для описания задачи. Входные и выходные данные можно кодировать некоторым «разумным» способом в виде двоичных последовательностей пз нулей и единиц. Тогда алгоритм можно рассматривать как последовательность двоичных операций, работающих с памятью из двоичных же символов.
Временная сложность алгоритма отражает затраты времени (число шагов), требуемые для его работы. Это есть функция, которая каждой входной длине и ставит в соответствие минимальное время, затрачиваемое алгоритмом для решения всех однотипных индивидуальных задач этой длины. Напомним, что функция 1(п) есть 0(д(п)), если существует константа с такая, что ~Дп)~ < с(д(п)) для всех и > О.
Полиномиалы*ьсм алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна О(Р(п)), где Р(п) — некоторая полиномиальная функция от входной длины и. Алгоритмы, для временной„сложности которых не существует такой оценки, называются экспонепциальны ми. Задача считается труднорешаемой, если для нее не сущее снует разрешающего полиномиального алгоритма.
В книге [5) приведены характерные таблицы оценки зависимости времени работы алгоритмов сложности, равной п, пз, 2", от размеров входной информации (табл. 4.2), а также оценки максимальной размерности задачи, решаемой за один час (табл. 4.3). Из последней таблицы видно, что повышение быстродействия машины не дает существенного роста размерности разрешимых задач, если алгоритм имеет экспоненциальную сложность. 156 Таблица 4.2. Глава 4.
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 4.8. О вычислительной сложности алгоритмов 4) задачи, которые могут быть решены лишь с использованием алгоритма экспоненциальной сложности. Разбиение задач на первые три класса зависит от мастерства математика. Однако задачи четвертого класса принципиально нельзя отнести к первым трем классам, поскольку они включают в себя экспоненциальные процедуры, например просмотр всех подграфов исходного графа. К четвертому классу относятся задачи перечисления всех остовных деревьев графа и перечисления всех циклов графа.
Это объясняется тем, что у полного п-вершинного графа число остовных деревьев равно пн 2, число циклов длины г равно Св'(4 — 1)!, т. е. общее число циклов составляет Таблица 4тн Многие прикладные задачи могут быть сформулированы в терминах теории графов. Однако при решении реальных задач характеристики соответствующих графов (например, число вершин п и число ребер т) весьма велики, и их анализ возможен лишь с привлечением вычислительной техники. Задача поиска эффективных алгоритмов в теории графов имеет большое практическое значение. Поэтому в заключение дадим краткий обзор временной сложности рассмотренных нами комбинаторных алгоритмов на графах.
Задачи теории графов можно классифицировать следующим образом: 1) задачи, для которых имеются алгоритмы сложности 0(п+ т); 2) задачи, для которых известны алгоритмы сложности 0(Р(п+ т)), где Р— нелинейный полипом; 3) задачи, для которых известны только алгоритмы экспоненцинльной сложности, но про которые нельзя сказать, что для них нет алгоритмов полиномиальной сложности; а Ес,',($ — 1)! > (и — 1)! К первому классу относятся, в частности, следующие задачи: — отыскание остовного дерева графа; — выделение компоненты связности графа и сильной связности ориентированного графа; — нахождение минимального пути в графе; — нахождение эйлерового цикла.
Для решения этих задач построены алгоритмы, имеющие сложность 0(п+ т). Второй класс в настоящее время включает в себя такие задачи: — нахождение матрицы связности (приведенный в п. 4.2.2 алгоритм Уоршела имеет сложность 0(пз)); — нахождение минимального пути в нагруженном графе (сложность, алгоритма 0(п )); — нахождение минимального остовного дерева в нагруженном графе (сложность алгоритма 0(т~)).
Получение оценок сложности алгоритмов выходит за рамки данной книги. Со способами вычисления этих оценок, а также с алгоритмами, позволяющими улучшить их, можно ознакомиться в специальных монографиях, например [1Ц. Третий класс содержит следующие задачи: — о существовании в графе гамильтонова цикла (задача коммивояжера); — об определении изоморфизма данного графа См какому- либо подграфу графа Сй, Литература ки.
Мл Изд-во МАИ, 1992. 158 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФО — не относящуюся непосредственно к теории графов, но фундаментальную задачу о выполнимости формулы логики высказываний, находящейся в конъюнктивной нормальной форме, и многие другие задачи. Для решения этих задач не существует полиномиальных алгоритмов, хотя не кажется безусловным, что их решение возможно лишь с помощью экспоненцнальных алгоритмов. Для многих задач этого класса справедливо следующее свойство сводимости: существование полиномиального алгоритма для решения одной из них дало бы полиномиальный алгоритм для решения другой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
