Основы дискретной математики В.А. Осипова (552659), страница 22
Текст из файла (страница 22)
Действительно, пусть (4.2) (з = (п1 = пп; ~ п12~ п11 = оз) путь, полученный в соответствии с алгоритмом 4.3, и его вес (длина) равна 1()т). Тогда, так как для этих вершин Л, = Л, , (и-1) Л,з = С1211,' ~ (и-1) з = С1212; Л(и 1) 11 $2 (4.3) (и-1) (и-1) Лы 1 Лп = сч — 1п ° Так как последовательность Лп, Л,,... строго убываю- (и-1) (и-1) (и-1) щая, то некоторое Ли равно О и, значит, соответствующая вершина ьн совг1адает с ги т. е, (4.2) — действительно путь из (и — 1) и1 в пь При этом длина его равна Л,, так как складывая почленно левые и правые части равенств (4.3), получим, что Л. = с12п + ссиз + ' ' ' + с11 — и1 = ((/л) ° (и-Ц Л' 1 О ~ (сзур (и-1) (и-1) Лзр 2 — Лзр 1 < сзР-1УР-2; (и — 1) (и-1) Л 1 — Л22 < С4211. Складывая почленно эти неравенства, получаем, что для произвольно выбранного пути (()1') выполняется соотношение Пусть'теперь д' = (п1 = и р, ..., п12, п11 = и;) — произвольный путь из вершины п1 в вершину и; и длина его равна ((д').
Тогда в силу п. 2 алгоритма 4.5 имеем 4.3. Поиск путей в графе 124 чим Л()= ш1п 1Я(5 агтг — э шах; Е 1=1 Лэ = ппп 1Я(5 о ,'1 Ь1т,<А, Таблица 4.1. где Л( ) = птах (Л( ) + сг1) 1Я(и Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Л( ) < 1(д'). Так как для пути )т имеем Л( ) = 1(и), то путь )т — минимальный. Пример 4.11. С помощью алгоритма 4.5 найдем минимальный путь из вершины и1 в вершину гэ в графе, изображенном на рис. 4.10. Минимальный путь — (и1, ий, иы и4, из), его вес (длина) равен 7.
Таблица индексов приведена в табл. 4.1. НапРимеР, использУЯ соотношение Л, = гшп (Л + сгч), полУ- (й-;-1) . (й) 1 Я(а 0 оо 2 со 9 + оо 7 1 0 7 2 3 9 + со 7 оо Для нахождения максимального пути (пути с наибольшей суммой весов (длин) в графе без контуров алгоритм модифици(й+1) руется: в п. 2 Л,. вычисляются по формулам для всех вершин, кроме и1, Л1 — — О, Л ф со, с; ф со.
(й4-1) (й) Последовательность вершин, составляющая максимальный путь, определяется по тому же правилу, что и для минимального пути. Алгоритмы решения задач о минимальных (максимальных) путях позволяют решать широкий класс задач дискретной оптимизации. В качестве примера приведем известную задачу о ранце (рюкзаке). К ней сводятся многие практические задачи, в которых при ограничении на общий объем, вес, размер финансирования требуется определить оптимальную комбинацию определяющих их факторов.
Задача о ранце. Пусть имеется и предметов, которые могут быть помещены в ранец. Полезность гтго предмета оценивается числом аь вес (или объем) — числом 6ь Суммарный вес (или объем) ранца ограничен числом А. Требуется найти набор предметов, обладающих максимальной суммарной полезностью и удовлетворяющий ограничению по весу (объему). Мы сформулировали простейший вариант задачи о ранце, постановка этой задачи имеет вид: 1, если 4-й предмет кладется в ранец; О, если 4-й предмет не кладется в ранец. 1 4.3.2. Специальные цепи в графе. Задача о коммивояжере Одной из наиболее старых задач, относящихся к теории графов, является задача Эйлера о Кенигсбергских мостах.
В Кенигсберге было два острова соединенных семью мостами с берегами реки так, как показано на рис. 4.11. Можно ли обойти все мосты, проходя по каждому из них только один раз? Все попытки эмпирически указать такой маршрут оканчиваются неудачей. Эйлер доказал неразрешимость этой задачи. Определим некоторый специальный вид цепей в графе. Эйлероеой цепью (циклом) называется цепь (цикл), содержащая все ребра графа и притом только по одному разу. Ответ на вопрос, обладает ли данный граф эйлеровой цепью или эйлеровым циклом, дает следующая теорема, которую приведем без доказательства. 127 4.4, Поиск путей в графе 126 а) Рис.
4.13. Рис. 4,11. Рис. 4.12. 3 1 оо 00 4 1 1 оо со оо 1 5 2 оо 2 со Оо 4 оо со 3 со 2 1 1 1 00. 00 00 3 1 00 со оо 2 Оо 00 3 оо 2 оо со 2 оо 4 2 2 9 1 оо 1 1 1 1 со 3 1 2 оо 1 6 1 1 со сс 00 1 2 00 оо 00 5 со со 1 2 оо оо оо 2 1 00 00 2 1 5 со 2 00 1 б) а) Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Теорема 4.1. Неориентпированный граф С =< 1т, сг > обладает эйлеровой цепью тпогда и тполько тогда, когда он свяэен и число вершин нечетной степени равно нулю или двум.
Неориентпированный граф С =< 1т, 0 > обладает эйлеровым циклом тогда и только тпогда, когда он свяэен и степени всех его вершин четны. Обозначим каждую часть суши в задаче о Кенигсбергских мостах вершиной, а каждый мост — ребром, соединяющим соответствующие вершины.
Получим граф, изображенный на рис. 4.11. Этот граф является квазиграфом, т. е. таким графом, у которого вершины могут быть соединены несколькими ребрами. Утверждение теоремы 4.1 выполняется также и для квазиграфов. Степени всех четырех вершин графа на рис. 4.12 нечетны и, следовательно, он не обладает эйлеровой цепью, что доказывает неразрешимость задачи о Кенигсбергских мостах.
Другой известной задачей теории графов является задача о коммивояэссере. Одна из возможных ее формулировок состоит в следующем. Коммивояжер (бродячий торговец) должен посетить по одному разу каждый из городов, связанных дорогами и вернуться в исходный город. Решение задачи о коммивояжере связано с нахождением еще одной специальной цепи в графе.
Гамилътоновой цепью (циклом) называется цепь (цикл), проходящая через каждую вершину графа и притом только один раз. Вопрос о необходимых и достаточных условиях существования гамильтоновых цепей и циклов является весьма сложным и имеет удовлетворительное решение только для некоторых специальных типов графов. Граф, изображенный на рис. 4.13, а) обладает гамильтоновой цепью, но не обладает эйлеровой так как число вершин нечетной степени равно 4; граф, изображенный на рис.
4.13, б) обладает эйлеровой цепью так как степени всех вершин четны, но не гамильтоновой. Задача о коммивояжере сводится к нахождению гамильтонова цикла в графе. Если интерпретировать расстояние между городами или стоимость проезда как веса ребер графа, то требуется найти гамильтонов цикл минимальной длины. Заметим, что в графе из п вершин существует и! гамильтоновых циклов. Поиск минимальных гамильтоновых циклов сложная с алгоритмической точки зрения задача.
Задачи и упражнения 1. Доказать, что любой путь наименьшей длины от вершины и к вершине у в ориентированном графе является простым путем. 2. Определить минимальный путь из вершины и1 в вершину ит в нагруженных графах, заданных матрицами весов: 3. Доказать, что связный граф, у которого все вершины имеют четную степень, содержит эйлерову цепь. 4. Существует ли эйлерова цепь и эйлеров цикл в графах? 128 129 /с Ь ы й 1сг; Ч Ъ", У 1',) 2=14=1 14.4) о йГ1Я) = 9, ТпГи; ф 9, 5 — 2952 Осипова Глава 4. ЭЛЕМЕНТЕ4 ТЕОРИИ ГРАФОВ 4.4. 'Устойчивые подмножества графа.
Ядра 4.4.1. Внутренне и внешне устойчивые множества В ориентированном графе С =< г', Г > подмножество о' С и называется внутренне устойчивым, если т. е. никакие две вершины из Я не смежны. Если У С о, то о' — также внутренне устойчивое подмножество. Внутренне устойчивое подмножество называется максимальным, если оно не является собственным подмножеством никакого другого внутренне устойчивого подмножества.
Пример 4.12. В группе лиц, в которой интересы некоторых из них попарно несовместимы, требуется сформировать комиссию с наибольшим возможным количеством участников с непротиворечивыми интересами. Рассмотрим граф, вершины которого соответствуют различным лицам, а ребра соединяют вершины, соответствующие несовместимым лицам. Тогда максимальные внутренне устойчивые подмножества этого графа соответствуют искомым комиссиям. Совокупность максимальных внутренне устойчивых подмножеств можно отыскать методом, предложенным К. Магу. Рассмотрим граф без петель с вершинами иы ий, ..., иь. Пусть о— некоторое внутренне устойчивое подмножество. Определим предикат г1 условием Ъ; = И тогда и только тогда, когда вершина и; Е 5, и переменную сан, где еа; = И тогда и только тогда, когда и Е Гин у ~ 4 1при переходе к булевым обозначениям, оя совпадает с элементом, стоящим 4.4.
Устойчивые подмножества графа. Ядра на пересечении 4-й строки и 2-го столбца матрицы смежности графа). По определению внутренней устойчивости формула ГУ4ИЧ?) (Яраса;, ) з Ъ'.), г, у' = 1, ..., Й, а также равносильная ей формула принимает значение И. Учитывая, что для данного графа значения ся есть И или Л, выражение 14.4) есть формула логики высказываний от переменных Ъы 'г2, ..., ~4~. Приведем ее к сокращенной дизъюнктивной нормальной форме. Тогда каждому дизъюнктивному члену гадесу;2ос ЙЪП) ЭтОй дИЗЪЮНКтИВНОй НарМаЛЬПОй фОрМЫ СО- ответствует максимальное внутренне устойчивое подмножество вершин 1г'11ио, о;2, ..., оа).
Описанным способом можно получить все максимальные внутренне устойчивые подмножества. В ориентированном графе С =< 1', Г > подмножество Т С С И называется внешне устойчивь м, если для любой вершины и;еТ т. е. из любой вершины и; не принадлежащей Т, исходит по крайней мере одна дуга в вершину, принадлежашую Т. Если Т С Т' С И, то Т' — также внешне устойчивое подмножество; если и; — вершина, для которой Гю; = 9, то Ъ;. принадлежит каждому внешне устойчивому подмножеству. Внешне ускойчивое подмножество называется минимальним, если оно не содержит в качестве собственного подмножества никакого другого внешне устойчивого подмножества. Пример 4.13.
(Задача о часовых. К. Берж). На рис. 4.14 изобРажен план тюРемного каземата с камеРами пы ий, ..., оэ, соединенными коридорами. Каково минимальное количество часовых, которых надо расставить у камер так, чтобы они могли наблюдать за всеми камерами? Задача сводится к нахождению минимального внешне устойчивого подмножества в соответствующем графе. Вершины 1иа, оа) составляют минимальное внешне устойчивое подмножество.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
