Лекции — Комбинаторные алгоритмы

Федеральное агентство по образованию
Государственное образовательное учреждение высшего
профессионального образования
Уфимский государственный авиационный технический университет








Лекции по дисциплине
«КОМБИНАТОРНЫЕ АЛГОРИТМЫ»












Уфа 2010


УДК 519.682.1
ББК 22.18 (я7)
П 30

П 30 Филиппова А.С. Лекции по дисциплине «Комбинаторные алгоритмы»: Учеб. пособие / А.С.Филиппова; Уфимск. гос. авиац. техн. ун-т. – Уфа: УГАТУ, 2010.-85 с. ISBN 0-486-41962-2

Пособие соответствует государственному образовательному стандарту дисциплины «Комбинаторные алгоритмы» направления подготовки бакалавров 010300 – «Математика. Компьютерные науки». Дисциплина посвящена алгоритмам решения типовых задач комбинаторной оптимизации. В лекциях основное внимание уделено комбинаторным алгоритмам и задачам исследования операций: кратчайшие расстояния на графах, остовные деревья, сети, сетевое планирование, потоки в сетях, паросочетания, понятие NP-полных задач.
Учебное пособие предназначены для студентов 2-го и 3-го курса общенаучного факультета, изучающих дисциплину «Комбинаторные алгоритмы».

Ил. 37. Табл. 13. Библиогр.: 5 назв.

Рецензенты: д-р. физ.-мат. наук, проф. С.И. Спивак


ISBN
ББК 22.18 (я7)
ISBN 0-486-41962-2 © Уфимский государственный авиационный
технический университет, 2010
© А.С. Филиппова, 2010
Содержание

Предисловие..4
Введение.4
Лекция 1. Основные определения комбинаторики5
Лекция 2. Сеть. Кратчайшие пути. Алгоритм Дейкстры..9
Лекция 3. Кратчайшие пути между всеми парами узлов. Алгоритм
с тройственными операциями.16
Лекция 4. Поиск остовного дерева в ширину и поиск в глубину. Алгоритмы .
Прима и Краскала (жадный) для поиска минимального остовного дерева.21
ЛЕКЦИЯ 5. Проблема коммивояжера. Алгоритмы «ближайшего соседа», «самой близкой вставки»26
ЛЕКЦИЯ 6. Сетевое планирование. Задача о кратчайшем сроке.
Задача о критическом пути30
ЛЕКЦИЯ 7. Максимальные потоки. Теорема Форда и Фалкерсона..35
Лекция 8. Метод нахождения максимального потока. Теорема о максимальных разрезах40
ЛЕКЦИЯ 9. Алгоритмы для нахождения максимального потока и минимального разреза..46
ЛЕКЦИЯ 10. Потоки с минимальной стоимостью. Метод анализа и оценки проекта REPT-метод.51
Лекция 11. Непересекающиеся цепи и разделяющие множества
Теорема Менгера. ...56
ЛЕКЦИЯ 12. Максимальные и наибольшие паросочетания. Алгоритм выбора наибольшего сочетания в двудольном графе с матрицей двудольного графа.60
ЛЕКЦИЯ 13 Задачи о назначении. Венгерский алгоритм.69
ЛЕКЦИЯ 14. Классы задач в зависимости от их трудности. Полиномиальные, недетерминированные алгоритмы. Стандартные NP-полные задачи. Решение NP-полной задачи.74
Контрольные вопросы ..82
Литература..84






















Предисловие
Учебное пособие содержит в себе курс лекций по дисциплине «Комбинаторные алгоритмы». Оно посвящено некоторым комбинаторным алгоритмам, которые встречаются в информатике, исследовании операций и дискретной математике. Особое внимание уделяется идеям, лежащим в основе алгоритмов, а так же детальному разбору численных примеров для каждого приведенного алгоритма. Каждый пример проиллюстрирован, что упрощает понимание сути изучаемых алгоритмов. Основу для материалов лекций составила книга Ху Т.Ч., Шинга М.Т. «Комбинаторные алгоритмы», перевод и научное редактирование которой выполнены в 2004 году на кафедре математической логики и высшей алгебры Нижегородского государственного университета им. Н.И.Лобачевского. Несмотря на то, что на русском языке имеются разного уровня и объема учебники, отражающие в разной степени рассматриваемую тематику, в основном они изданы в конце прошлого века и поэтому для студентов составляет трудность их изучение. Данное учебное пособие отличает простой стиль изложения с минимумом формализма (но не в ущерб математической строгости), отбор материала, сбалансированный объем.



Введение
Комбинаторика раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций. Это изучение включает в себя вопросы существования комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса. Простейшим примером комбинаторных конфигураций являются перестановки, сочетания и размещения. Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация Комбинаторное искусство), Я. Бернулли (работа Искусство предположений), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и  Г. Лейбница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало  одному из основных методов перечисления комбинаторных конфигураций методу производящих функций.   Возвращение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам.  Классические комбинаторные задачи это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок. Например, в 1859 г. У. Гамильтон придумал игру Кругосветное путешествие, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа. Это одна из самых известных задач комбинаторики - задача коммивояжера.






Лекция 1. Основные определения комбинаторики

Бытует мнение, что комбинаторные задачи элементарны. Конечно, это не так. Число комбинаторных задач и их разнообразие быстро растет. К их решению прямо или косвенно приводят многие практические задачи. При этом оказывается, что несмотря на заманчивую простоту постановки, комбинаторные задачи в большинстве очень трудны; многие из них не поддаются решению до сих пор. К числу современных задач, решаемых комбинаторными методами, относятся:
1) задачи на размещения. Это задачи о расположении, например, на плоскости предметов, обладающих свойствами дальнодействия;
2) задачи о покрытиях и заполнениях. Это задачи, например, о заполнении заданных пространственных фигур меньшими телами заданных форм и размеров;
3) задачи о маршрутах. К ним относятся задачи на отыскание кратчайшего пути и тому подобное. Это задачи оптимального плана;
4) комбинаторные задачи теории графов. Это задачи сетевого планирования, например, задачи транспортных и электрических сетей, задачи об окрашивании графов, задачи о перечислении вершин и тому подобные задачи;
5) перечислительные задачи. В таких задачах речь идет о числе предметов, составляемых из данного набора элементов при соблюдении определенных правил.
В задачах комбинаторного анализа исследуются дискретные множества, то есть множества, составленные из отдельных обособленных элементов. В большинстве случаев эти множества конечные, но не исключается и рассмотрение множеств, состоящих из бесконечного числа элементов. Особенностью комбинаторных задач является то, что в них преимущественное внимание уделяется двум видам операций: отбору подмножеств и упорядочению элементов. Эти две операции и являются основными комбинаторными.
В некотором смысле слово «комбинаторика» можно понимать как синоним термина «дискретная математика», то есть исследование дискретных конечных математических структур. Вычисления на дискретных конечных математических структурах, которые часто называют комбинаторными вычислениями, требуют комбинаторного анализа для установления свойств и выявления оценки применимости используемых алгоритмов. Рассмотрим элементарный жизненный пример.
Пример 1.1. Пусть некоторое агентство недвижимости располагает базой данных из n записей, причём каждая запись содержит одно предложение (что имеется) и один запрос (что требуется) относительно объектов недвижимости. Требуется найти все такие пары записей, в которых предложение первой записи совпадает с запросом второй и одновременно предложение второй записи совпадает с запросом первой. (На бытовом языке это называется подбором вариантов обмена.) Допустим, что используемая СУБД позволяет проверить вариант за одну миллисекунду. Нетрудно сообразить, что при «лобовом» алгоритме поиска вариантов (каждая запись сравнивается с каждой) потребуется п(п 1)/2 сравнений. Если n = 100, то все в порядке ответ будет получен за 4,95 секунды. Но если n = 100 000 (более реальный случай), то ответ будет получен за 4 999 950 секунд, что составляет без малого 1389 часов и вряд ли может считаться приемлемым. Обратите внимание на то, что мы оценили только трудоёмкость подбора прямых вариантов, а существуют ещё варианты, когда число участников сделки больше двух.
Этот пример показывает, что практические задачи и алгоритмы требуют предварительного анализа и количественной оценки. Задачи обычно оцениваются с точки зрения размера, то есть общего количества различных вариантов, среди которых нужно найти решение, а алгоритмы оцениваются с точки зрения сложности. При этом различают
- сложность по времени (или временную сложность), то есть количество необходимых шагов алгоритма,
- сложность по памяти (или емкостную сложность), то есть объём памяти, необходимый для работы алгоритма.
Во всех случаях основным инструментом такого анализа оказываются формулы и методы.
Во многих практических случаях возникает необходимость подсчитать количество возможных комбинаций объектов, удовлетворяющих определённым условиям. Такие задачи называются комбинаторными. Разнообразие комбинаторных задач не поддаётся исчерпывающему описанию, но среди них есть целый ряд особенно часто встречающихся, для которых известны способы подсчёта.
Для формулировки и решения комбинаторных задач используются различные модели комбинаторных конфигураций. Рассмотрим следующие две наиболее популярные (изложение на “языке ящиков» и «языке функций»):
а) Дано n предметов. Их нужно разместить по m ящикам так, чтобы выполнялись заданные ограничения. Сколькими способами это можно сделать?
б) Рассмотрим множество функций 13EMBED Equation.31415, где 13EMBED Equation.31415, 13EMBED Equation.31415. Не ограничивая общности, можно считать, что Х = {1,...,п}, Y = {1,...,т}, F= (F(1),...,F(n)), 13EMBED Equation.31415. Сколько существует функций F, удовлетворяющих заданным ограничениям?
1) Размещения. Число всех функций (при отсутствии ограничений), или число всех возможных способов разместить п предметов по m ящикам, называется числом размещений и обозначается U(m,n).
Перестановка с повторениями – выборка упорядоченная, в которой элементы могут повторяться.
Теорема. U (m,n) = 13EMBED Equation.31415.
Доказательство. Поскольку ограничений нет, предметы размещаются независимо друг от друга и каждый из га предметов можно разместить m способами.
Замечание. В комбинаторных задачах часто используются два правила, которые называются правилом суммы и правилом произведения. Неформально эти правила можно сформулировать следующим образом. Пусть существуют некоторые возможности построения комбинаторной конфигурации. Если эти возможности взаимно исключают друг друга, то их количества следует складывать, а если возможности независимы, то их количества следует перемножать.
Пример 1.1. При игре в кости бросаются две кости и выпавшие на верхних гранях очки складываются. Какова вероятность выбросить 12 очков? Каждый возможный исход соответствует функции F: {1,2} > {1,2,3,4,5,6} (аргумент номер кости, результат очки на верхней грани). Таким образом, всего возможно U(6,2) = 62 = 36 различных исходов. Из них только один (6 + 6) даёт двенадцать очков. Вероятность 1/36.
2) Размещения без повторений. Число инъективных функций, или число способов разместить n предметов по m ящикам, не более чем по одному в ящик, называется числом размещений без повторений и обозначается А(m,n), или 13EMBED Equation.31415.
Теорема. 13EMBED Equation.31415.
Доказательство. Ящик для первого предмета можно выбрать m способами, для второго m- 1 способами и т. д. Таким образом
13EMBED Equation.31415. (1.1)
По определению считают, что A(m,n) =0 при n > m и А(т, 0) = 1.
Замечание. Формула (1.1) слева выглядит сложной и незавершённой, формула справа изящной и «математичной». Но формула это частный случай алгоритма. При практическом вычислении левая формула оказывается намного предпочтительнее правой. Во-первых, для вычисления по левой формуле потребуется (т- 1) умножение, а по правой (2т- п - 2) умножений и одно деление. Поскольку п < т, левая формула вычисляется существенно быстрее. Во- вторых, число А(m,n) растёт довольно быстро и при больших m и n может не поместиться в разрядную сетку. Левая формула работает правильно, если результат помещается в разрядную сетку. При вычислении же по правой формуле переполнение может наступить «раньше времени» (то есть промежуточные результаты не помещаются в разрядную сетку, в то время как окончательный результат мог бы поместиться), поскольку факториал очень быстро растущая функция.
Пример 1.2. В некоторых видах спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. Сколько возможно различных исходов, если в соревновании участвуют п участников? Каждый возможный исход соответствует функции F: {1,2,3} 13EMBED Equation.31415{1 ..п} (аргумент номер призового места, результат номер участника). Таким образом, всего возможно А(п, 3) = п(п - 1)(n- 2) различных исходов.
3) Перестановки. Если |Х| = |Y| = n, то существуют взаимно-однозначные функции 13EMBED Equation.31415. Число взаимно-однозначных функций, или число перестановок п предметов, обозначается Р(п).
Теорема Р(п) = п!.
Доказательство: 13EMBED Equation.31415
Пример 1.3. Последовательность 13EMBED Equation.31415 непустых подмножеств множества 13EMBED Equation.31415 называется цепочкой в Е, если
13EMBED Equation.31415&13EMBED Equation.31415.
Цепочка 13EMBED Equation.31415 называется полной цепочкой в Е, если |13EMBED Equation.31415| =|E|. Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующее подмножество Ei+1 получено из предыдущего подмножества Ei добавлением ровно одного элемента из Е и таким образом, |E1|=1, |E2|= 2, ..., |Ет|= т. Следовательно, полная цепочка определяется порядком, в котором элементы Е добавляются для образования очередного элемента полной цепочки. Отсюда количество полных цепочек это количество перестановок элементов множества Е, равное т!.
4) Сочетания. Число строго монотонно возрастающих функций, или число размещений n неразличимых предметов по m ящикам не более чем по одному в ящик, то есть число способов выбрать из т ящиков n ящиков с предметами, называется числом сочетаний и обозначается С(т,п), или 13EMBED Equation.31415, или 13EMBED Equation.31415.
Теорема. 13EMBED Equation.31415
Доказательство. (Обоснование формулы) Сочетание является размещением без повторений неразличимых предметов. Следовательно, число сочетаний определяется тем, какие ящики заняты предметами, поскольку перестановка предметов при тех же занятых ящиках считается одним сочетанием. Таким образом,
13EMBED Equation.31415.
(Сведение моделей) Число сочетаний является числом строго монотонно возрастающих функций, потому что любая строго монотонно возрастающая функция 13EMBED Equation.31415 определяется набором своих значений, причём 13EMBED Equation.31415. Другими словами, каждая строго монотонно возрастающая функция определяется выбором п чисел из диапазона 1..т. Таким образом, число строго монотонно возрастающих функций равно числу n-элементных подмножеств m-элементного множества, которое, в свою очередь, равно числу способов выбрать n ящиков с предметами из m ящиков.
·
По определению 13EMBED Equation.31415 при п> т.
Пример 1.4. В начале игры в домино каждому играющему выдаётся 7 костей из имеющихся 28 различных костей. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элементпого множества. Имеем:
13EMBED Equation.31415.
5) Сочетания с повторениями. Число монотонно возрастающих функций, или число размещений n неразличимых предметов по т ящикам, называется числом сочетаний с повторениями и обозначается V(m, п).
Теорема. V(m,n) = C(n + m - 1, n).
Доказательство. Монотонно возрастающей функции 13EMBED Equation.31415 однозначно соответствует строго монотонно возрастающая функция 13EMBED Equation.31415. Это соответствие устанавливается следующей формулой: 13EMBED Equation.31415.
Пример 1.5. Сколькими способами можно рассадить n вновь прибывших гостей среди m гостей, уже сидящих за круглым столом? Очевидно, что между m сидящими за круглым столом гостями имеется m промежутков, в которые можно рассаживать вновь прибывших. Таким образом, число способов равно
13EMBED Equation.31415.



























Лекция 2. Сеть. Кратчайшие пути. Алгоритм Дейкстры

Подграф, являющийся деревом и содержащий все вершины графа, называется остовным (покрывающим) деревом графа.
Эти определения иллюстрируются рис. 1.


Рис. 1. Граф G

В графе G имеется три пути между вершинами 13EMBED Equation.31415 и 13EMBED Equation.31415: (13EMBED Equation.31415), (13EMBED Equation.31415), (13EMBED Equation.31415). Ребра 13EMBED Equation.31415 и 13EMBED Equation.31415 образуют остовное дерево, то же верно для ребер 13EMBED Equation.31415 и 13EMBED Equation.31415. Еще одно остовное дерево можно составить из ребер 13EMBED Equation.31415 и 13EMBED Equation.31415. Вершина 13EMBED Equation.31415 имеет степень 3 в графе G и степень 2 в последнем остовном дереве. Если ребро 13EMBED Equation.31415 ориентировано от 13EMBED Equation.31415 к 13EMBED Equation.31415, то по-прежнему есть три пути из 13EMBED Equation.31415 в 13EMBED Equation.31415, но ни одного пути из 13EMBED Equation.31415 в 13EMBED Equation.31415.
В большинстве приложений с ребрами или вершинами ассоциируются некоторые числа. В этом случае граф называется сетью. Все определения теории графов применимы и к сетям. В теории сетей мы обычно используем термины «узлы» и «дуги» вместо «вершины» и «ребра».

Кратчайший путь
Каждой дуге сети приписано число – длина этой дуги.
В большинстве случаев длины дуг положительны, но в некоторых приложениях они могут быть и отрицательными. Например, узлы могут представлять различные состояния некоторой физической системы, а длина дуги 13EMBED Equation.31415, может означать количество энергии, поглощаемой при переходе из состояния 13EMBED Equation.31415 в состояние 13EMBED Equation.31415. Отрицательная длина дуги тогда означает, что энергия излучается при переходе из 13EMBED Equation.31415 в 13EMBED Equation.31415. Если суммарная длина некоторого контура или цикла в сети отрицательна, будем говорить, что сеть содержит отрицательный контур.
Длина пути есть сумма длин всех его дуг. Обычно имеется много путей между двумя вершинами 13EMBED Equation.31415 и 13EMBED Equation.31415, путь минимальной длины называется кратчайшим путем из 13EMBED Equation.31415 в 13EMBED Equation.31415.
Задача нахождения кратчайшего пути является фундаментальной и часто входит как подзадача в другие оптимизационные задачи. Обычно рассматриваются три типа задач о кратчайшем пути:
кратчайший путь от одного узла до другого;
кратчайшие пути от одного узла до всех других узлов;
кратчайшие пути между всеми парами узлов.
Так как все алгоритмы, решающие задачу (1) и задачу (2), по существу, те же самые, мы будем рассматривать задачу нахождения кратчайших путей от одного узла до всех остальных узлов сети.
Задача нахождения кратчайшего пути корректна, если сеть не содержит отрицательного цикла (или отрицательного контура). Заметим, что сеть может иметь ориентированные дуги отрицательной длины и не иметь отрицательных циклов.
Обозначим длину дуги из 13EMBED Equation.31415 в 13EMBED Equation.31415 через 13EMBED Equation.31415 и предположим, что
13EMBED Equation.31415 для всех i, j, (1.1)
13EMBED Equation.31415 для некоторых i, j, (1.2)
13EMBED Equation.31415 для некоторых i, j, k. (1.3)
Для удобства будем считать, что 13EMBED Equation.31415, если нет дуги из узла 13EMBED Equation.31415 в узел 13EMBED Equation.31415, и 13EMBED Equation.31415 для всех i.
Условие (1.3) делает задачу о кратчайшем пути нетривиальной. Если оно не выполняется, то кратчайший путь из 13EMBED Equation.31415 в 13EMBED Equation.31415 состоит из единственной дуги 13EMBED Equation.31415.
Обычно мы хотим знать как длину кратчайшего пути, так и последовательность его узлов. Сделаем сначала несколько замечаний. Пусть 13EMBED Equation.31415 – путь из 13EMBED Equation.31415 в 13EMBED Equation.31415, 13EMBED Equation.31415 – промежуточный узел этого пути. Тогда подпуть от 13EMBED Equation.31415 до 13EMBED Equation.31415 содержит меньше дуг, чем путь 13EMBED Equation.31415. Так как длины всех дуг положительны, то этот подпуть короче, чем 13EMBED Equation.31415. Сформулируем это как замечание 1.
Замечание 1. Длина пути больше, чем длина любого его подпути. (Заметим, что это верно только если длины всех дуг положительны.)
Пусть 13EMBED Equation.31415 промежуточный узел пути 13EMBED Equation.31415 (от 13EMBED Equation.31415 до 13EMBED Equation.31415). Если 13EMBED Equation.31415 – кратчайший путь, то подпуть от 13EMBED Equation.31415 до 13EMBED Equation.31415 сам должен быть кратчайшим путем. В противном случае более короткий путь до 13EMBED Equation.31415, дополненный отрезком исходного пути от 13EMBED Equation.31415 до 13EMBED Equation.31415, составил бы путь, более короткий, чем 13EMBED Equation.31415. Сформулируем это как замечание 2.
Замечание 2. Любой подпуть кратчайшего пути сам должен быть кратчайшим путем. (Заметим, что это не зависит от того, положительны ли длины дуг).
Замечание 3. Любой кратчайший путь содержит не более чем n-1 дугу. (При условии, что нет отрицательных циклов и что в сети n узлов).
На основании этих замечаний можно построить алгоритм для нахождения кратчайших путей из 13EMBED Equation.31415 во все остальные узлы сети.
Пусть, кратчайшие пути из 13EMBED Equation.31415 во все остальные узлы упорядочены в соответствии с их длинами. Для простоты изложения мы можем переименовать узлы так, чтобы кратчайший путь в 13EMBED Equation.31415 был кратчайшим среди всех кратчайших путей. Пусть пути занумерованы в порядке возрастания их длин:
13EMBED Equation.31415.
Алгоритм найдет сначала 13EMBED Equation.31415, затем 13EMBED Equation.31415, и т.д., пока не будет найден самый длинный из кратчайших путей.
Идея алгоритма:
- Если 13EMBED Equation.31415 содержал бы более одной дуги, то он выключал бы более короткий подпуть (замечание 1). Поэтому 13EMBED Equation.31415 должен содержать только одну дугу.
- Если 13EMBED Equation.31415 содержит более чем k дуг, то он содержит по крайней мере k промежуточных узлов. Каждый из подпутей, ведущих в промежуточный узел, короче, чем 13EMBED Equation.31415, и получается k путей, более коротких, чем 13EMBED Equation.31415, что невозможно. Поэтому кратчайший путь 13EMBED Equation.31415 содержит не более k дуг. Сформулируем это как замечание 4.
Замечание 4. Кратчайший путь 13EMBED Equation.31415 содержит не более k дуг.
Следовательно, чтобы найти 13EMBED Equation.31415, нужно только рассмотреть пути из одной дуги, минимальной среди них будет 13EMBED Equation.31415. Чтобы найти 13EMBED Equation.31415, нужно рассмотреть пути из одной и двух дуг. Минимальный среди них будет 13EMBED Equation.31415. Если 13EMBED Equation.31415 – путь из двух дуг с последней дугой 13EMBED Equation.31415 и при этом 13EMBED Equation.31415, то дуга 13EMBED Equation.31415 образует подпуть 13EMBED Equation.31415, более короткий, чем 13EMBED Equation.31415. Поэтому путь 13EMBED Equation.31415 должен либо состоять из одной дуги, либо из двух дуг, последней из которых является дуга 13EMBED Equation.31415.
Далее мы будем приписывать узлам числа, называемые метками. Каждая метка может быть одного из двух видов: временная или постоянная. Постоянная метка узла – это истинное кратчайшее расстояние от начала 13EMBED Equation.31415 до этого узла. Временная метка – это длина некоторого пути от начала до этого узла. Этот путь может быть, а может и не быть кратчайшим, поэтому временная метка является верхней оценкой истинного кратчайшего расстояния.
Описание процесса поиска кратчайших путей от одного узла до всех остальных.
Начиная поиск 13EMBED Equation.31415, приписываем каждому узлу 13EMBED Equation.31415 длину дуги 13EMBED Equation.31415, т.е. временные метки узлов. Среди всех временных меток выбираем минимальную и превращаем ее в постоянную. Таким образом, 13EMBED Equation.31415 становится помеченной постоянно (постоянная метка.
Чтобы найти 13EMBED Equation.31415, не нужно искать все пути из двух дуг, достаточно рассмотреть те из них, у которых первая дуга есть 13EMBED Equation.31415. В качестве временных меток приписываем узлам длины путей из одной дуги.
Далее сравниваем 13EMBED Equation.31415 (длину одной дуги) с 13EMBED Equation.31415 (длиной пути из двух дуг) и минимальное из этих двух значений приписать как временную метку вершине 13EMBED Equation.31415.
Минимум среди всех временных меток есть 13EMBED Equation.31415.
Постоянная метка указывает истинное кратчайшее расстояние от 13EMBED Equation.31415 до 13EMBED Equation.31415. Временная метка узла 13EMBED Equation.31415 указывает либо длину дуги 13EMBED Equation.31415, либо длину пути из 13EMBED Equation.31415 в постоянный узел 13EMBED Equation.31415, дополненного дугой 13EMBED Equation.31415.
Правило для упрощения поиска.
Как только узел 13EMBED Equation.31415 получает постоянную метку 13EMBED Equation.31415, проверяем для каждого узла 13EMBED Equation.31415, соседнего с узлом 13EMBED Equation.31415 и имеющего временную метку, верно ли, что 13EMBED Equation.31415 меньше, чем текущая временная метка 13EMBED Equation.31415. Если верно, заменим эту временную метку значением 13EMBED Equation.31415. Если нет, оставим временную метку без изменения.
Чтобы найти 13EMBED Equation.31415, достаточно найти минимальную временную метку всех соседей узлов и превратить эту метку в постоянную.
Теперь можно формально описать алгоритм и применить его к численному примеру. Будем применять 13EMBED Equation.31415 для обозначения временного кратчайшего расстояния и 13EMBED Equation.31415 для обозначения истинного кратчайшего расстояния.

Алгоритм Дейкстры
(нахождение кратчайшего пути от одного узла до всех остальных)
Шаг 0. Каждому узлу 13EMBED Equation.31415 (i = 1,2,..., п-1) присвоить временную метку 13EMBED Equation.31415. (если нет дуги, соединяющей 13EMBED Equation.31415 и 13EMBED Equation.31415 полагаем 13EMBED Equation.31415)
Шаг 1. Среди всех временных меток выбрать 13EMBED Equation.31415. Заменить 13EMBED Equation.31415 на 13EMBED Equation.31415. Если нет временных меток, остановиться.
Шаг 2. Пусть 13EMBED Equation.31415 узел, только что получивший постоянную метку на шаге 1. Изменить временные метки соседей 13EMBED Equation.31415 узла 13EMBED Equation.31415 в соответствии со следующим правилом: 13EMBED Equation.31415. Перейти к шагу 1.
Пример 2.1. Рассмотрим сеть, показанную на рис. 2, где числа являются длинами дуг.
Будем изображать временные метки внутри каждого узла, а когда метка превращается в постоянную, будем помечать число звездочкой. Когда дуга применяется в некотором кратчайшем пути, будем изображать ее жирной линией.
Шаг 0. Все узлы получают временные метки, равные 13EMBED Equation.31415, а узел 13EMBED Equation.31415 – постоянную метку 0. Это показано на рис. 3.
Шаг 1. Среди всех временных меток минимальное значение 2 имеет метка узла 13EMBED Equation.31415, поэтому 13EMBED Equation.31415 получает постоянную метку.

13 SHAPE \* MERGEFORMAT 1415
Рис. 2
13 SHAPE \* MERGEFORMAT 1415
Рис. 3.

Шаг 2. Узел 13EMBED Equation.31415 имеет соседей 13EMBED Equation.31415 и 13EMBED Equation.31415.
13EMBED Equation.31415.
13EMBED Equation.31415.
Результат показан на рис. 4.

13 SHAPE \* MERGEFORMAT 1415
Рис. 4.
Шаг 1. Среди всех временных меток наименьшую метку 3 имеет узел 13EMBED Equation.31415. Поэтому 13EMBED Equation.31415 получает постоянную метку.
Шаг 2. Соседями узла 13EMBED Equation.31415 являются 13EMBED Equation.31415, 13EMBED Equation.31415. (Узел 13EMBED Equation.31415 тоже соседний, но он стал постоянным и поэтому исключается.)
13EMBED Equation.31415
13EMBED Equation.31415.
Шаг 1. Узел V1 получает постоянную метку 4.
Шаг 2. 13EMBED Equation.31415. Это показано на рис. 5.
Шаг 1. V4 получает постоянную метку 5.
13 SHAPE \* MERGEFORMAT 1415
Рис. 5.

Шаг 2. 13EMBED Equation.31415.
13EMBED Equation.31415
Шаг 1. V6 получает постоянную метку 11.
Шаг 2. 13EMBED Equation.31415
Шаг 1. V5 получает постоянную метку 13.
Шаг 2. 13EMBED Equation.31415
Шаг 1. V7 получает постоянную метку 14.
Окончательный результат показан на рис. 6.
Мы вычислили кратчайшие расстояния от V0 до всех остальных узлов сети, но не нашли кратчайших путей, на которых достигаются эти расстояния.
Способ проследить промежуточные узлы:
Если узлу Vj приписана постоянная метка, то можно просмотреть все соседние узлы и найти среди них тот, метка которого отличается от метки узла Vj в точности на длину соединяющей их дуги. Таким образом, мы можем для каждого узла проследить в обратном направлении путь из начала в этот узел. На рис. 7 каждому узлу приписаны два числа. Первое число постоянная метка, указывающая истинное кратчайшее расстояние от начала до этого узла, второе число указывает последнюю промежуточную вершину кратчайшего пути.

13 SHAPE \* MERGEFORMAT 1415
Рис. 6.

13 SHAPE \* MERGEFORMAT 1415
Рис. 7.

Сложность алгоритма. Так как алгоритм состоит из сравнений и сложений, подсчитаем количество сравнений и сложений.
Имеется n - 2 сравнений при первом проходе, п - 3 сравнений при втором проходе и т. д., так что всего имеется (n - 2) + (n - 3) + . . . + 1 = (n - 1)(n - 2)/2 сравнений на шаге 1. Аналогично, имеется (n - 1)(n - 2)/2 сложений и столько же сравнений на шаге 2. Поэтому, трудоемкость алгоритма есть О(n2). Так как в сети с n узлами имеется О(n2) дуг и каждая дуга должна быть рассмотрена хотя бы один раз, то не будет рискованным сказать, что не существует алгоритма, требующего в общем случае O(n log n) шагов.


Лекция 3. Кратчайшие пути между всеми парами узлов

Рассмотрим задачу поиска кратчайших путей между всеми парами узлов сети.
Пусть 13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415, ,13EMBED Equation.31415, - кратчайший путь из Vi в Vq. Тогда кратчайший путь из Vi в Vj должен представлять собой единственную дугу еij , кратчайший путь из Vj в Vk дугу ejk, и т. д.
Назовем дугу еij базисной, если она представляет собой кратчайший путь из Vi в Vj. Из данного определения следует, что кратчайший путь состоит только из базисных дуг.
Алгоритм, который мы опишем, заменяет все небазисные дуги базисными. Т.е., алгоритм строит дуги, соединяющие каждую пару узлов, не соединенную базисной дугой. Длина каждой построенной дуги равна кратчайшему расстоянию между двумя узлами. Для данного узла Vj рассмотрим следующую простую операцию:
13EMBED Equation.31415 (3.1)
Операция выполняется для каждого фиксированного j и всевозможных i и k, не равных j. Для трех узлов Vj, Vj и Vk и трех дуг с длинами dik , dij и djk данная операция сравнивает длину дуги еik , с длиной пути, состоящего из двух дуг, с промежуточным узлом Vj. Этот случай показан на рис. 8. Операция (2.1) называется тройственной операцией.

13 SHAPE \* MERGEFORMAT 1415
Рис. 8.

Для всевозможных пар узлов Vi и Vk, смежных с Vj , выполним следующие операции.
- Если dik 13EMBED Equation.31415 dij + djk, то никаких действий не производим.
- Если dik > dij + djk,, то создаем новую дугу, ведущую из Vi в Vk с dik = dij + djk .
Схема алгоритма:
Фиксируем j = 1 и выполняем тройственную операцию (3.1) для всех i, k = 2,3, . . . , n.
Фиксируем j = 2 и выполняем тройственную операцию (3.1) для всех i, k = 1, 3, . . . , n.
Замечание. Все новые дуги, добавленные при j = 1, используются далее при j = 2, и т.д.
Как только все тройственные операции будут выполнены для j = n, сеть будет состоять только из базисных дуг и, числа, приписанные каждой ориентированной дуге, ведущей из Vp в Vq, являются кратчайшими расстояниями из Vp в Vq. Докажем это утверждение на примере.
В исходной сети рассмотрим любой кратчайший путь из Vp в Vq. Кратчайший путь должен состоять из базисных дуг этой сети. Если в результате тройственной операции создается дуга с длиной, равной сумме длин всех базисных дуг кратчайшего пути, то это докажет корректность алгоритма.
Рассмотрим кратчайший путь, изображенный на рис. 9.
13 SHAPE \* MERGEFORMAT 1415
Рис. 9.

При j = 1 тройственная операция создает новую дугу с d63 = d61 + d13.
При j = 2 тройственная операция никак не скажется на данном отдельном кратчайшем пути.
При j = 3 дуга с d63 = d61 + d13 уже построена, следовательно, тройственная операция построит дугу с d63 = d63 + d39 = (d61 + d13) + d39.
При j = 4 будет построена дуга с d26 = d24 + d46.
При j = 6 будет построена дуга длины d29= d26 + d69=(d24 + d46) + (d63 + d39)= d24 + d46 + d61 + d13 + d39.
На рис. 9 построенные дуги изображены пунктирной линией. Числа рядом указывают порядок, в котором эти дуги появлялись. Таким образом, базисная дуга е63 построена первой, а базисная дуга е69 построена второй. Некоторые базисные дуги, которые также будут построены в результате тройственной операции, например, e41 , не изображены на рисунке, так как они не влияют на рассматриваемый кратчайший путь.
Замечание 1. Любая из дуг, построенная в результате тройственной операции, не может быть заменена другой дугой или путем меньшей длины. Противное противоречило бы тому, что исходный путь кратчайший.
Замечание 2. Если в сети отсутствуют отрицательные циклы, то любой кратчайший путь должен быть простым и должен состоять не более чем из n - 1 дуг и не более чем из n - 2 различных промежуточных узлов.
Приведенный алгоритм легко может быть запрограммирован на компьютере. Длины дуг сети с n узлами могут быть заданы массивом n х n.
Пример 3.1. Для сети, изображенной на рис. 10, матрица расстояний представлена в таблице 1.
13 SHAPE \* MERGEFORMAT 1415
Рис. 10. Сеть, пример 2

При j = 1 мы сравниваем каждый элемент di,k (13EMBED Equation.31415) с dj,1 + d1,k.
Если di,k >dj,1 + d1,k, то элемент di,k заменяется на эту сумму. В противном случае элемент не меняется.


Табл. 1. Матрица расстояний, пример 2
узел
1
2
3
4
5

1
0
1

·

·
4

2
1
0
5
1

·

3

·
5
0
2

·

4

·
1
2
0
1

5
4

·

·
1
0


При j = 2 мы сравниваем каждый элемент di,k (13EMBED Equation.31415) с dj,2 + d2,k. Минимум из чисел di,k и dj,2 + d2,k становится новым значением элемента di,k.
Замечание 3. В описанных вычислениях при j = 2 мы использовали результаты, полученные при j = 1.
Для фиксированного значения j мы должны просмотреть элементы в (n 1) х (n 1) матрице (диагональные элементы всегда равны 0). Каждый элемент сравнивается с суммой двух других элементов: один из той же строки и один из того же столбца. Алгоритм завершает свою работу, когда мы заканчиваем вычисления для j = n.
Замечание 4. Все длины в неориентированной сети симметричны, поэтому достаточно вычислить только одну из двух длин.
Решение примера 2.1. Выполним тройственную операцию для j = 1,2,3,4,5 и запишем только вычисления, которые приводят к изменению в матрице расстояний.
При j = 1
d25 = min{d25, d21 + d15} = min{
·, 1 + 4} = 5.
Изменения расстояний занесены в табл. 2

Табл. 2.
узел
1
2
3
4
5

1
0
1

·

·
4

2
1
0
5
1
5

3

·
5
0
2

·

4

·
1
2
0
1

5
4
5

·
1
0


При j = 2
d13 = min{d13, d12 + d23} = min{
·, 1 + 5} = 6,
d14 = min{d14, d12 + d24} = min{
·, 1 + 1} = 2,
d35 = min{d35, d32 + d25} = min{
·, 5 + 5} = 10.
Изменения расстояний занесены в табл. 3.
При j = 3
изменений нет.
При j = 4
d13 = min{d13, d14 + d43} = min{6, 2 + 2} = 4,
d15 = min{d15, d14 + d45}= min{4, 2 + 1} = 3,
d23 = min{d23, d24 + d43} = min{5, 1 + 2} = 3,
d25 = min{d25, d24-+ d45} = min{5, 1 + 1} = 2,
d35 = min{d35, d34 + d45} = min{10, 2 + 1} = 3.
Изменения расстояний занесены в табл. 4


Табл. 3.
узел
1
2
3
4
5

1
0
1
6
2
4

2
1
0
5
1
5

3
6
5
0
2
10

4
2
1
2
0
1

5
4
5
10
1
0



Табл. 4.
узел
1
2
3
4
5

1
0
1
4
2
3

2
1
0
3
1
2

3
4
3
0
2
3

4
2
1
2
0
1

5
3
2
3
1
0



При j = 5изменений нет.
Кратчайшие расстояния между каждой парой узлов найдены. Итоговая таблица кратчайших расстояний – это табл. 4. Но необходимо найти промежуточные (внутренние) узлы для кратчайших путей.
Чтобы зафиксировать порядок, в котором появляются эти узлы, мы используем матрицу [pi,k], в которой элемент i-ой строки и k-ro столбца указывает на первый внутренний узел в пути из Vi в Vj,. Если Рik = j, то кратчайший путь имеет вид Vi, Vj,..., Vk. Далее, если pj,k = s, то кратчайший путь имеет вид Vi,Vj, Vs,..., Vk. Изначально мы полагаем Pi,k = k для всех i, k. Например, таблице 1 соответствует таблица 5.

Таблица 5. Начальная таблица промежуточных узлов
узел
1
2
3
4
5

1
1
2
3
4
5

2
1
2
3
4
5

3
1
2
3
4
5

4
1
2
3
4
5

5
1
2
3
4
5


.
Таким образом, предполагается, что каждая дуга базисная (до тех пор, пока не установлено обратное), и первым внутренним узлом на пути из Vi в Vk является сам Vk.
Во время выполнения тройственной операции над таблицей 1 мы также обновляем данные в таблице промежуточных узлов. Элементы таблицы промежуточных узлов изменяются согласно следующему правилу:
pi,k =13EMBED Equation.31415 (3.2)

Например, когда мы присваиваем элементу d25 значение d21 + d15 = 5, мы также полагаем
p25 = p21 = 1.
Когда мы присваиваем элементу d14 значение d12+d24 = 2, мы также полагаем
p14 = p12 = 2.
Когда мы присваиваем элементу d15 значение d14+d45, = 2, мы также полагаем
p15 = p 14 = p 12 = 2.
Когда мы присваиваем элементу d25 значение d24+d45 = 2, мы также полагаем
p25 = p24 = 4.
Итак, по окончании вычислений мы имеем
p15 = 2, p25 = 4.
Так как дуга e45 базисная, то на протяжении всех вычислений р45 = 5.
p15 = 2 означает, что V2 есть первый промежуточный узел на пути из V1 в V5.
p25 = 4 означает, что V4 есть первый промежуточный узел на пути из V2 в V5.
p45 = 5 означает, что V5 есть первый промежуточный узел на пути из V4 в V5.
Таким образом, мы можем выписать все промежуточные узлы на пути из V1 в V5 ими являются V1, V2, V4 и V5.
В общем случае, чтобы найти кратчайший путь из Vg в Vt, мы находим первый промежуточный узел pgt.
Если pst = a, то ищем pat =?
Если pat = b, то ищем рbt =?
Эти действия завершаются, когда pzt=t. Тогда Vs , Va , Vb ,. . . , Vz , Vt узлы кратчайшего пути.
Элементы таблицы 5 изменяются по формулам (3.2) в то же самое время, когда элементы таблицы 1 изменяются по формулам (3.1). В конце вычислений по формулам (3.1), когда мы получаем таблицу 4 кратчайших расстояний, мы также получаем таблицу 6 промежуточных узлов, вычисленную по формулам (3.2).

Табл. 6. Таблица промежуточных узлов. Пример 2.1
узел
1
2
3
4
5

1
1
2
2
2
2

2
1
2
4
4
4

3
4
4
3
4
4

4
2
2
3
4
5

5
4
4
4
4
5


Замечание 5. Несмотря на то, что таблица 1 симметрична, таблица 6 таковой не является. Для того, чтобы получить всю таблицу 6, мы должны провести все вычисления над таблицей 1, а не только половину вычислений, которые мы выполнили в примере.
Например, когда мы полагаем d25 = d51 + d12 = 5, мы также должны выполнить присваивания p52 = p51 = 1.




Лекция 4. Поиск остовного дерева в ширину и поиск в глубину. Алгоритмы Прима и Краскала (жадный) для поиска
минимального остовного дерева

Дана неориентированная сеть N, нужно выбрать подмножество дуг, образующих дерево Т, в котором существует путь между каждой парой узлов сети. Дерево такого типа называется остовным деревом сети.
Поиск остовного дерева в ширину и поиск в глубину
Во многих приложениях нужно в определенном порядке посетить все узлы графа, т. е. построить остовное дерево.
Рассмотрим следующие два общих способа обхода, называемые поиском в ширину (BFS, breadth-first-search) и поиском в глубину (DFS, depth-first-search).
Поиск в ширину, BFS. Выбираем произвольно узел графа G, назовем этот узел V0 и затем посетим всех соседей V0 в произвольном порядке, например, это узлы V1 , V2, , Vi. После посещения всех соседей V0 начать обход заново из V1 (первого посещенного соседа узла V0) и посетить все соседние с V1 узлы, скажем, V11, V12,, V1j, потом все новые узлы, соседние с V2, скажем, V21, V22, , V2k. Систематически получаем:

Порядок
Соседние узлы

V0
V1 , V2, , Vi

V1
V11, V12,, V1j

V2
V21, V22,, V2j




V11
V11 1, V11 2,, V11 j

V12
V12 1, V12 2,, V12 j


На рис. 11 можно взять за V0 узел Va, тогда узлы можно посетить в следующем порядке:
V0, Vb, Vc, Vd, Ve, Vf,
V0, V1, V2, V11, V21 , V11 1.

13 SHAPE \* MERGEFORMAT 1415
Рис. 11.

Если взять в качестве V0 узел Vb, то можно посетить вершины в порядке
Vb , Va , Vc, Vd, Ve, Vf,
V0, V1 , V2, V3, V21, V31.
Замечание 1. После посещения нового узла можно посетить соседей нового узла в произвольном порядке. Здесь используется соглашение о том, что при необходимости выбора узлы посещаются в алфавитном порядке.
Замечание 2. Если пометить дугу, соединяющую посещенный узел с ранее посещенным узлом, то все эти помеченные дуги образуют остовное дерево графа G; если же каждая дуга имеет длину 1, то остовное дерево является деревом кратчайших путей из V0 во все остальные узлы G.
Поиск в глубину, DFS. Выбираем произвольно вершину V0, а затем следуем по ребру е01 в узел Vi , потом следуем по ребру e12 в узел V2, соседний с V1 . Вобщем случае, после посещения узла Vi следуем по ребру eij в узел Vj, если Vj ранее еще не был посещен. Далее применяем рекурсивно этот процесс к Vj и выбираем ребро ejk в узел Vk. Если вершина Vj уже была посещена, то возвращаемся в Vi и выбираем другое ребро. Если все ребра, инцидентные Vi, уже выбраны и нельзя найти ни одной новой вершины, то возвращаемся из Vj в предыдущую вершину, за которой идет Vi, и проверяем ей инцидентные ребра.
Если на рис. 11 начать с вершины Vb, то можно посетить узлы в следующем порядке (упорядочение определяется не единственным образом):
Vb, Vc, Va, Vd, Ve, Vf.
Дуги, следующие в новые вершины, образуют остовное дерево. Это дуги: ebc, eca, ecd, ede, eef.
Можно сравнить два способа посещения узлов. При BFS нужно проверить все ребра, инцидентные узлу, перед переходом к новому узлу. Таким образом, операция последовательно выполняется веером из узлов. При DFS переход к новому узлу осуществляется только после того, как найден новый узел, и происходит проникновение в глубину графа. Только тогда, когда все ребра ведут в старые вершины, идет возврат к предыдущему узлу и из него опять возобновляется DFS.
Алгоритмы BFS и DFS имеют одинаковую сложность для самого неблагоприятого случая. Сложность алгоритма для самого неблагоприятного случая – это приблизительная мера максимального числа действий, требуемых, чтобы выполнить алгоритм. Это функция размера входных данных, которые непосредственно в нашем случае были представлены графом (например, О(n)). Так как алгоритмы имеют одинаковую сложность, то ни один из них не имеет преимуществ перед другим. Тем не менее, для целого ряда специфических графов один алгоритм мог бы производить дерево покрытия эффективнее, чем другой. Например, поиск «по глубине» эффективнее для графа «колеса», а поиск «ширине» для графа «Мальтийский крест».
Минимальное остовное дерево
Если дугам приписаны стоимости dij, то стоимость остовного дерева определяется как сумма dij по всем дугам дерева. Остовное дерево с наименьшей стоимостью среди всех остовных деревьев называется минимальным остовным деревом.
Замечание 3. В общем случае минимальное остовное дерево отличается от дерева кратчайших путей.
Следующие две леммы кажутся очевидными, однако их доказательства требуют внимательного изучения.
Лемма 1. Пусть Va произвольный узел и еах кратчайшая дуга среди всех дуг, смежных с Va. Тогда существует минимальное остовное дерево Т*, содержащее дугу еах.
Доказательство. Пусть Т минимальное остовное дерево, а, А подмножество дуг, смежных с Va, например, А = {eab, eac, ead, eax}. Предположим, что дуга еах является кратчайшей дугой, смежной с Va, но не принадлежит Т. Поскольку Т остовное дерево, то в Т должен быть путь из Vx в Va, содержащий одну из дуг А, например, ead. Обозначим этот путь через (Pxd, eda), где Pxd путь из Vx в Vd . Заменяя ead на еах, получим Т*. Если еах короче, чем ead, то заключаем, что Т* остовное дерево с меньшей стоимостью.
Во-первых, в дереве Т* Va соединяется с Vx дугой еах, а с узлом Vd – путем (eax,Pxd). Оставшиеся узлы Vb, Vc по-прежнему связаны с Va и, следовательно, с остальными узлами сети, значит, Т* является остовным деревом.
Во-вторых, стоимость Т* меньше, чем Т, так как еах короче, чем ead. Это противоречит предположению о том, что Т минимальное остовное дерево. Если дуги ead и еах имеют одинаковые длины, то также можно заменить еаd на еах и получить минимальное остовное дерево Т*, содержащее еах.
Лемма 2. Если известно, что подмножество ребер, образующих поддерево F, является частью минимального остовного дерева, то существует минимальное остовное дерево, содержащее F, и минимальное ребро, соединяющее F u N-F.
Доказательство. Доказательство в точности совпадает с доказательством леммы 1, если заменить Va на F.

По лемме 1 можно начать из произвольной вершины и выбрать наименьшую смежную дугу. Так как известно, что только что выбранная дуга является частью минимального остовного дерева, то можно в лемме 2 взять ее в качестве F и выбрать наименьшую дугу, инцидентную F.
Можно продолжить выбор наименьшего ребра, инцидентного уже выбранной компоненте. Это алгоритм Прима для нахождения минимального остовного дерева.
Идея алгоритма следующая. Алгоритм создает последовательные связные поддеревья, путем присоединения на каждом шаге одной смежной дуги так, чтобы на каждой стадии была выбрана инциндентная дуга с самой маленькой стоимостью. Пример реализации идеи алгоритма Прима представлен на рис. 12. Если начальный узел V0, то последовательность присоединяемых дуг следующая: дуга со стоимостью 1, смежная (вертикальная) дуга со стоимостью 2, дуга (горизонтальная) со стоимостью 2, дуга со стоимостью 4, дуга со стоимостью 3. Стоимость минимального остовного дерева 12.
13 SHAPE \* MERGEFORMAT 1415
Рис. 12. Пример минимального остовного дерева

Замечание 4. Алгоритм Прима для минимального остовного дерева сходен с алгоритмом Дейкстры для нахождения кратчайших путей.
Алгоритм Прима
Пометим узлы, соединенные дугами в остовном дереве, постоянными метками, а еще не соединенные узлы временными метками.
Шаг 0. Выберем произвольный узел, назовем его V1 и пометим его постоянным значением ноль (т.е. Р1=0). Пометим все остальные узлы временно значениями Tj, равными d1j для Vj.
Шаг 1. Среди всех временных меток выберем одну (например, Tj) с наименьшим значением и сделаем ее постоянной. Включим дугу со значением dij = Tij в минимальное остовное дерево, в котором Vi постоянный узел и Tj = dij.
Шаг 2. Пусть Vj последний узел, только что ставший постоянным. Для каждого временного узла Vk пусть Tk mim{Tk, djk}. Если нет временных меток, то конец, иначе вернуться на шаг 1.

Анализ алгоритма Прима. На шаге 1 производится (n - 1) + (n - 2) + + 1 =О(n2) сравнений. На шаге 2 осуществляется (n - 2) + + 1 = О(n2) сравнений. Таким образом, этот алгоритм снова является алгоритмом трудоемкости О(n2).
Замечание. Алгоритм Прима можно использовать и для максимальных остовных деревьев, просто заменяя минимум на максимум (здесь dij = -
·, если нет дуги).
Пример 3.1. Проиллюстрируем алгоритм Прима для сети со значениями величин dij, указанными в таблице 7.
Если данные сети представлены в матричной форме, алгоритм Прима можно описать следующим образом:

Табл. 7. Матрица расстояний dij, пример 3
узел
1
2
3
4
5
6

1
0

·
1

·
3

·

2

·
0

·
6

·
8

3
1

·
0
4
2

·

4

·
6
4
0
6
7

5
3

·
2
6
0

·

6

·
8

·
7

·
0



Шаг 0. Вычеркнуть все элементы в первом столбце и пометить первую строку.
Шаг 1. Выбрать минимальный элемент среди всех элементов в помеченных строках, пусть, например, минимальный элемент есть dij (вычеркнутые элементы выбирать нельзя). Если все элементы в помеченных строках вычеркнуты, то конец.
Шаг 2. Вычеркнуть j-й столбец и пометить i-ю строку. Вернуться на шаг 1.
Если применить алгоритм Прима к таблице 7, то после выбора двух элементов вычисления будут выглядеть так, как показано в таблице 8 (выбранные элементы заключены в рамку).
Табл. 8.
узел
1
2
3
4
5
6

1
0

·
1

·
3

·

2

·
0

·
6

·
8

3
1

·
0
4
2

·

4

·
6
4
0
6
7

5
3

·
2
6
0

·

6

·
8

·
7

·
0

Порядок постоянных меток
0
4
1
3
2
5


Дуги в порядке получения: e13 – e35 – e34 – e42 – e46.





Алгоритм Краскала или жадный для поиска минимального остовного дерева
Начинают с пустого подргафа. Формируют последовательность из (не обязательно связных) подграфов, добавляя на каждой стадии дугу с самой маленькой стоимостью, не допуская при этом образования петель у существующего подграфа. Когда возникает ситуация, при которой дальнейшее добавление ребер оказывается невозможным, получают результирующий подграф, представляющий собой минимальное остовное дерево. Для примера сети изображенной на рис. 12. Последовательность дуг, присоединяемых к минимальному остовному дереву по алгоритму Краскала следующая: первой присоединяется дуга с наименьшей стоимостью 1, далее две дуги со стоимостью 2, затем дуга со стоимостью 3 и последней дуга стоимости 4. Стоимость минимального остовного дерева 12.








































ЛЕКЦИЯ 5. Проблема коммивояжера. Алгоритмы «ближайшего соседа», «самой близкой вставки»

Коммивояжер должен посетить каждый из заданных городов и возвратиться к своему первоначальному положению. Учитывая сеть дорог, соединяющих различные города на его маршруте, проблема путешествующего коммивояжера состоит в том, чтобы найти маршрут, который минимизирует полное расстояние его путешествия. При этом такой маршрут допускает посещение некоторых городов более одного раза.
Сеть дорог может быть представлена взвешенным графом (сетью). Каждый город представляется вершиной, а каждая дорога, соединяющая два города представляется ребром, соединяющим соответствующие два вершины, причем вес ребра равен длине данной дороги. Путешествие, при котором посещается каждый город и которое заканчивается в исходном стартовом положении, представляется замкнутой последовательностью ребер графа, у которого последовательность связанных вершин содержит все вершины. В терминологии теории графов проблема коммивояжера состоит в том, чтобы найти такую замкнутую последовательность ребер, полный вес которой является минимальным. Мы предположим, что граф связан так, что для коммивояжера действительно оказывается возможным посетить каждый город, используя дороги данной сети.
Как правило, оказывается целесообразным несколько видоизменить исходную проблему следующим образом. Граф, описанный выше, заменяется полным графом с одной вершиной для каждого города. (Напомним, что полный граф это такой граф, у которого имеется единственное ребро, соединяющее каждую пару отличных вершин.) Каждому ребру такого графа приписывается вес, равный наикротчайшему расстоянию между соответствующими городами, в соответствии с используемой сетью дорог. Эти самые короткие расстояния могут быть найдены, на основании применения алгоритма Дейкстры к первоначальному графу. Вес ребра в полном графе может быть меньше, чем вес ребра, соединяющего те же самые вершины в первоначальном графе. Это связано с тем, что может найтись маршрут между двумя вершинами итоговая длина которого будет меньшей, чем длина единственного ребра соединяющего эти две вершины. Чтобы мы могли позже возвращать информацию относительно исходного графа (который может и не являться полным графом), мы должны будем хранить записи связанные с информацией о том, какие пути исходного графа формировали ребра полного графа.
Замкнутая последовательность ребер, позволяющая посетить все вершины графа представляющего дорожную сеть соответствует цепи Гамильтона в полном графе Таким образом, проблема коммивояжера может быть сформулирована следующим образом.
ПРОБЛЕМА КОММИВОЯЖЕРА. Для заданного связанного, взвешенного, полного графа требуется построить цепь Гамильтона минимального веса; то есть минимальную цепь Гамильтона.
Напомним, что не каждый граф имеет цепь Гамильтона; однако, каждый полный граф, имеющий, по крайней мере, три вершины, имеет цепь Гамильтона, что непосредствен. Так как наши графы конечны, то может иметься только конечное число цепей Гамильтона, и следовательно, среди них должна быть и минимальная.
Так как веса ребер в полном графе - это самые короткие расстояния между вершинами первоначального графа сети дорог, то для полного графа должно выполняться следующее неравенство треугольника.
Для каждого триплета отличных вершин (V1; V2, V3) справедливо:
d12 + d23
· d13,
где dij - - вес единственного ребра, соединяющего Vi и Vj.
Проблема коммивояжера в виду своего большого практического значения получила значительное внимание со стороны теоретиков, и было разработано много различных алгоритмов для строительства минимальной цепи Гамильтона. Одна из причина большого интереса к данной проблеме связана с тем фактом, что все известные алгоритмы, которые решают данную проблему являются в вычислительном отношении неэффективными относительно числа вершин, то есть все известные алгоритмы являются алгоритмами показательного времени. Тем не менее, с практической точки зрения известны различные эффективные алгоритмы, которые дают приблизительное решение. Другими словами, они обеспечивают цепи Гамильтона, чей вес оказывается близким к минимально возможному, однако при этом нельзя быть уверенным в том, что данный вес является самым минимальным из возможных.
Имеется достаточно очевидный и простой "приблизительный" алгоритм, так называемый известный «алгоритм ближайшего соседа». Это своего рода модификация алгоритма поиска по глубине.
Идея алгоритма «ближайшего соседа». Алгоритм начинается в любой вершине и «идет» по ребрам с самым маленьким весом, которые (ребра) оказываются инцидентными вершине. На каждом шаге алгоритма, мы начинаем развитие событий с последней из числа посещенных вершин и двигаемся вдоль ребер с наименьшим из возможных значений веса по направлению к новым вершинам. (Могут иметься несколько возможностей выбора «минимального ребра» на каждой стадии.) Когда все вершины окажутся посещенными, мы возвращаемся к стартовому положению по единственному ребру полного графа от последней вершины, назад к первой.
Наиболее похожим алгоритмом является жадный алгоритм (в том смысле, что именно ближайшие вершины посещаются на каждой стадии). Оказывается, что этот алгоритм чрезвычайно беден в следующем смысле. Хотя этот алгоритм в некоторых случаях и будет производить минимальный цикл Гамильтона, как правило, цикл, произведенный таким алгоритмом может иметь вес значительно превышающий возможный минимум. Фактически работа данного алгоритма примерно настолько плоха, как только это можно себе представить. Взяв любое положительное целое число k (сколь угодно большое) всегда найдутся графы, для которых вес цикла Гамильтона, полученного на основании алгоритма ближайшего соседа, окажется в k раз больше веса минимального цикла.
Рассмотрим другой "приблизительный" алгоритм «алгоритм самой близкой вставки». Он гарантирует нахождение цикла Гамильтона с полным весом, который не более, чем в два раза превышает минимальный цикл. Причем, как правило, алгоритм самой близкой вставки порождает цикл Гамильтона с весом, значение которого оказывается значительно меньше двойного минимума
Идея алгоритма самой близкой вставки. Основной шаг в алгоритме самой близкой вставки заключается в том, чтобы взять в графе цикл и увеличить его, включая в него самые близкие к нему вершины. Этот шаг повторяется до тех пор, пока все вершины не окажутся включенными в цикл.
Алгоритм может применяться к любому полному взвешенному графу, для которого выполняется неравенство треугольника.
Алгоритм самой близкой вставки
Выбрать любую вершину. Выбрать инцидентное вершине ребро е с самым маленьким весом, и пусть С является последовательностью ребер: е, е. С - стартовый "цикл", (хотя строго говоря это не цикл, так как данная последовательность содержит повторяющееся ребро).
Выбрать ребро с самым маленьким весом, которое присоединяет инцидентную ему вершину, находящуюся вне цикла С к вершине входящей в цикл С (может иметься несколько возможностей выбора таких ребер).
Увеличении цикла в результате включения выбранной вершины V0. Чтобы решить, как вставить V0, следует рассмотреть все пары V1 , V2 смежных вершин цикла С и выбрать такую пару, для которой выражение:
I = d10 + d02 - d12
является минимальным, где dij - обозначает вес ребра, соединяющего Vi и Vj. Это выражение I представляет увеличение полного веса цикла С, после включения в него вершины V0. Мы увеличиваем цикл С, включая вершину V0 путем присоединения ребра соединяющего вершины V1 и V0, и ребра, соединяющего вершины V0 и V2, и удаляя затем ребро соединяющее вершины V1 и V2.
4. Повторяем шаги 2 и 3, пока цикл не будет включать в себя все вершины графа.
Пример 5.1. Проиллюстрируем алгоритм ближайшего включения для сети, представленной на рис. 13 (которая удовлетворяет неравенству треугольника). Веса ребер представлены в матрице расстояний, см. табл.9.

Табл. 9. Матрица расстояний dij, пример 4
узел
А
B
C
D
E
F

A
0
4
9
12
10
3

B
4
0
6
8
10
6

C
9
6
0
5
9
12

D
12
8
5
0
4
11

E
10
10
9
4
0
7

F
3
6
12
11
7
0


Чтобы выполнить шаг I, мы сначала выберем вершину маркированную на рисунке буквой А (мы могли бы, конечно, выбрать любую другую из вершин). Ребро eAF является ребром, инцидентным вершине А, и имеет самый маленький вес из числа ребер, инцидентных вершине А. Поэтому первый цикл будет: eAF, eFA (от вершины А до вершины F и назад к вершине А).
13 SHAPE \* MERGEFORMAT 1415
Рис. 13
Ребро с самым маленьким весом, инцидентное вершине А или вершине F это ребро еАВ, поэтому вершина В это первая вершина, которую следует вставить. Самый короткий путь, которым вершина В может быть вставлена в цепь будет: от вершины А до вершины В и назад через вершину F. Это порождает цепь еАВ, eBF, eFA, показанную на рис. 14.
13 SHAPE \* MERGEFORMAT 1415
Рис. 14

Вершина, которая является самой близкой к вершине этой цепи это вершина С, поэтому мы должны найти лучший способ вставить ее. Цены I для трех ребер текущей цепи будут:
I (еAB) = dAC + dCB - dAB = 9 + 6 - 4 = 11,
I (eBF) = dBC + dCF - dBF = 6 + 12 - 6 = 12 ,
I (eFA) = dFC + dCA - dFA = 12 + 9 - 3 = 18.
Мы таким образом увеличиваем цепь путем удаления ребра еAB и вставляя на его место ребра еАС, еCB. Это дает цепь, показанную на рис. 15.
13 SHAPE \* MERGEFORMAT 1415
Рис. 15

Повторяя этот процесс дважды, мы увеличиваем цепь, включая сначала вершину D и затем вершину Е. Заключительная цепь, eAC, eCD, eDE, eEB, eBF, eFA, является требуемой цепью Гамильтона с полным весом 9 + 5 + 4+ 10+ 6 + 3 = 37.
Этот пример иллюстрирует тот факт, что алгоритм самой близкой вставки может не производить минимальную цепь Гамильтона. Граф действительно имеет единственную минимальную цепь Гамильтона - еАВ, еBC, eCD, eDE, eEF, eFA с полным весом 29.




ЛЕКЦИЯ 6. Сетевое планирование. Задача о кратчайшем сроке.
Задача о критическом пути

Выполнение комплексных научных исследований, а также проектирование и строительство крупных промышленных, сельскохозяйственных и транспортных объектов требуют календарной увязки большого числа взаимосвязанных работ, выполняемых различными организациями. Составление и анализ соответствующих календарных планов представляют из себя весьма сложную задачу, при решении которой применяются так называемые методы сетевого планирования.
При использовании указанных методов зависимость между отдельными работами задается с помощью некоторого орграфа Г, в котором каждая дуга 13EMBED Equation.31415 отвечает определенной работе. Если в этом графе дуги 13EMBED Equation.31415 образуют путь из вершины 13EMBED Equation.31415в вершину 13EMBED Equation.31415, то это означает, что выполнение работ s, для которых 13EMBED Equation.31415= 13EMBED Equation.31415, может начинаться лишь после завершения всех работ 13EMBED Equation.31415. Ввиду этого каждую вершину i орграфа Г интерпретируют как событие, означающее возможность выполнения тех работ s, для которых 13EMBED Equation.31415= i, т. е. завершение всех работ s, для которых 13EMBED Equation.31415 = i. Приведенная интерпретация означает, что для выполнимости рассматриваемого комплекса работ соответствующий орграф Г не должен содержать контуров. Действительно, если бы имелся некоторый контур 13EMBED Equation.31415, то для выполнения каждой работы 13EMBED Equation.31415 потребовалось бы предварительно завершить все остальные работы, что приводит к неразрешимому вопросу, типа известного вопроса о том, кто снес яйцо, из которого вылупилась первая курица.
Следовательно, практически реализуемые комплексы работ описываются орграфами Г, не содержащими контуров. Ясно, что в каждом таком орграфе имеется, по крайней мере, одна начальная вершина 13EMBED Equation.31415, для которой
13EMBED Equation.31415(,
и, по крайней мере, одна конечная вершина 13EMBED Equation.31415, для которой
13EMBED Equation.31415(.
В сетевом планировании обычно ограничиваются рассмотрением случая, когда 13EMBED Equation.31415 = 1 является единственной начальной вершиной, a 13EMBED Equation.31415 = n единственной конечной вершиной. Первая из этих вершин интерпретируется как начальное событие, а вторая как конечное событие, означающее завершение всего комплекса работ. При этом, как нетрудно проверить, для каждой вершины 13EMBED Equation.31415 в орграфе Г имеется путь с концом в этой вершине и началом в вершине 13EMBED Equation.31415 = 1. Точно так же для каждой вершины 13EMBED Equation.31415 имеется путь из этой вершины в конечную вершину 13EMBED Equation.31415 = n.
13EMBED Word.Picture.81415
Рис. 16.

Легко проверить, что в орграфе Г, изображенном на рис. 16, нет контуров и в нем имеются одна начальная вершина 13EMBED Equation.31415 = 1 и одна конечная вершина 13EMBED Equation.31415 = 8. Жирной линией показан путь из начальной вершины 13EMBED Equation.31415= 1 в конечную вершину 13EMBED Equation.31415= 8.
Допустим теперь, что рассматриваемый комплекс работ описывается орграфом Г, обладающим указанными свойствами. Кроме того, известно время 13EMBED Equation.31415, необходимое для выполнения каждой работы 13EMBED Equation.31415. В этом случае, говорят, что имеется сетевой график Г, где 13EMBED Equation.31415.
Календарный план выполнения сетевого графика Г, определяется выбором m-мерного вектора
13EMBED Equation.31415, (6.1)
компоненты которого указывают планируемые сроки выполнения соответствующих событий. Такой план является допустимым (согласован с заданными величинами 13EMBED Equation.31415), если он удовлетворяет условию
13EMBED Equation.31415, 13EMBED Equation.31415. (6.2)
При этом срок выполнения всего комплекса работ определяется величиной
13EMBED Equation.31415. (6.3)
Естественно, что мы заинтересованы в минимизации общего срока выполнения работ. Таким образом, приходим к следующей задаче линейного программирования.
Задача о кратчайшем сроке. При заданном сетевом графике Г определить вектор (6.1), минимизирующий линейную функцию (6.3) при ограничениях (6.2).
Приведенная задача, как нетрудно проверить, является двойственной к следующей задаче, представляющей также самостоятельный интерес.
Задача о критическом пути. При исходных данных задачи о кратчайшем сроке определить п-мерный вектор
x = (x1, х2, ..., хm), 13EMBED Equation.31415, 13EMBED Equation.31415 (6.4)
максимизирующий линейную функцию
13EMBED Equation.31415 (6.5)
при ограничениях
13EMBED Equation.31415 (6.6)
Ясно, что задача о критическом пути является частным случаем сетевой транспортной задачи, в которой 13EMBED Equation.31415= 1, 13EMBED Equation.31415= -1 и 13EMBED Equation.31415= 0, 13EMBED Equation.31415, a 13EMBED Equation.31415, 13EMBED Equation.31415.
Рассмотренные задачи могут решаться простым методом, сводящийся к последовательным просмотрам дуг сетевого графика.
Для каждой вершины 13EMBED Equation.31415, как уже отмечалось, имеется, по крайней мере, один путь р = {13EMBED Equation.31415} с концом в этой вершине и началом в вершине 13EMBED Equation.31415= 1. Множество таких путей обозначим через 13EMBED Equation.31415 и рассмотрим величины
13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415. (6.7)
Нетрудно проверить, что они удовлетворяют соотношениям
13EMBED Equation.31415, 13EMBED Equation.3141513EMBED Equation.31415 (6.8)
где 13EMBED Equation.31415 определяемый формулой (5.3) кратчайший срок для сетевого графика Г. Но тогда в качестве решения задачи о кратчайшем сроке может быть принят вектор (6.1) с компонентами (6.7).
Покажем теперь, что для практического вычисления величин (6.7) нет надобности в предварительном определении соответствующих множеств путей 13EMBED Equation.31415. Для этого заметим, что интересующие нас величины (6.7) связаны между собой соотношениями
13EMBED Equation.31415, 13EMBED Equation.31415, (6.9)
где под 13EMBED Equation.31415, как и выше, понимается множество дуг с концом в вершине i. Используя приведенные формулы, мы можем определить все величины (6.7) за 13EMBED Equation.31415 просмотров списка дуг сетевого графика, где через 13EMBED Equation.31415 обозначена максимальная длина путей 13EMBED Equation.31415. Соответствующий алгоритм для вычисления величин (6.7) поясним более подробно на числовом примере.
Пример 6.1. Рассмотрим сетевой график Г, отвечающий числовым данным, приведенным в табл. 10. Заметим, что соответствующий орграф Г совпадает с изображенным на рис. 16.
Таблица 10
s
1
2
3
4
5
6
7
8
9
10
11
12
13
14

is, js
1, 2
1, 3
1, 4
2, 5
3, 2
3, 5
3, 6
3, 7
4, 3
4, 7
5, 8
6, 8
7, 6
7, 8

13EMBED Equation.31415
10
3
2
5
7
20
12
4
10
5
10
5
2
12


Предположим, что уже имеются некоторые неотрицательные величины 13EMBED Equation.31415, 13EMBED Equation.31415. Тогда при просмотре очередной дуги s новое значение 13EMBED Equation.31415 определяется по формуле
13EMBED Equation.31415.
Получаемые при этом величины 13EMBED Equation.31415, очевидно также не превосходят 13EMBED Equation.31415. Далее, если при очередном просмотре всех дуг 13EMBED Equation.31415 не происходит ни одного изменения величин 13EMBED Equation.31415, то это означает, что имеющиеся 13EMBED Equation.31415 совпадают с искомыми величинами (6.9).
В качестве исходных принимаем 13EMBED Equation.31415=0, 13EMBED Equation.31415. Затем, просматривая дуги 13EMBED Equation.31415, последовательно находим новые значения
13EMBED Equation.31415 = 10, 13EMBED Equation.31415 = 3, 13EMBED Equation.31415 = 2, 13EMBED Equatio
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
которые приведены во второй строке табл. 11.
На втором просмотре дуг 13EMBED Equation.31415 определяем новые значения величин 13EMBED Equation.31415, приведенные в третьей строке табл. 11. На третьем просмотре дуг 13EMBED Equation.31415 ни одна из найденных величин 13EMBED Equation.31415 не изменяется. Следовательно, полученные при втором просмотре величины ti совпадают с искомыми величинами 13EMBED Equation.31415.

Таблица 11
1
2
3
4
5
6
7
8

0
10
12
2
23
15
7
33

0
19
12
2
32
24
16
42


Рассмотренные величины (6.7) определяют минимально возможные сроки выполнения всех событий. При анализе сетевых графиков представляет интерес выявление имеющихся резервов в сроках выполнения отдельных событий. С этой целью через 13EMBED Equation.31415 для каждой вершины 13EMBED Equation.31415 обозначим множество путей из этой вершины в конечную вершину i= n. Затем рассмотрим величины
13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415. (6.10)
Так как множество путей 13EMBED Equation.31415очевидно, совпадает с множеством путей 13EMBED Equation.31415, то
13EMBED Equation.31415.
Что касается остальных вершин 13EMBED Equation.31415, то для них, очевидно, имеют место неравенства
13EMBED Equation.31415, 13EMBED Equation.31415. (6.11)
При этом неотрицательные величины
13EMBED Equation.31415, 13EMBED Equation.31415 (6.12)
можно интерпретировать как имеющиеся резервы времени для выполнения соответствующих событий. Событие i сетевого графика Г называется критическим, если в соответствующем неравенстве (6.11) достигается равенство, т. е. резерв времени (6.12) для выполнения этого события равен нулю.
Для практического вычисления величин (6.10), как и в предыдущем случае, нет надобности в предварительном определении соответствующих множеств путей 13EMBED Equation.31415. Достаточно заметить, что интересующие нас величины (6.10) связаны между собой следующими соотношениями:
13EMBED Equation.31415, 13EMBED Equation.31415 (6.13)
где под 13EMBED Equation.31415 понимается множество дуг с началом в вершине i.
Работу s сетевого графика Г называют напряженной если события 13EMBED Equation.31415 и 13EMBED Equation.31415, являются критическими и при этом 13EMBED Equation.31415, или, что то же, 13EMBED Equation.31415. Ясно, что для определения всех критических событий и всех напряженных дуг достаточно вычислить величины (6.7) и (6.10).
Пример 5.2. Для сетевого графика Г, который уже рассматривался в связи с определением величин 13EMBED Equation.31415 (см. пример 6.1), найдем величины 13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415, а также все критические события и напряженные работы. Исходные данные примера повторены в табл. 10 с тем, чтобы читатель мог проводить соответствующие выкладки, не отрываясь от текста. Кроме того, во второй строке табл. 11 приведены величины 13EMBED Equation.31415, 13EMBED Equation.31415, найденные при решении примера 6.1. Интересующие нас величины 13EMBED Equation.31415, 13EMBED Equation.31415, также определяются за 13EMBED Equation.31415 просмотров дуг 13EMBED Equation.31415. Предположим, что уже имеются некоторые величины 13EMBED Equation.31415, 13EMBED Equation.31415, причем 13EMBED Equation.31415= 13EMBED Equation.31415 = 42. Тогда при просмотре очередной дуги s новое значение 13EMBED Equation.31415 определяется по формуле
13EMBED Equation.31415.
Получаемые при этом величины 13EMBED Equation.31415, очевидно, также не меньше 13EMBED Equation.31415. Далее, если при очередном просмотре всех дуг 13EMBED Equation.31415 не происходит ни одного изменения величин ti, то это означает, что имеющиеся ti совпадают с искомыми величинами (6.10). В качестве исходных принимаем 13EMBED Equation.31415, 13EMBED Equation.31415. Затем за несколько просмотров дуг 13EMBED Equation.31415 находим величины 13EMBED Equation.31415 которые приведены в третьей строке табл. 12. В последнюю строку таблицы заносим величины 13EMBED Equation.31415, подсчитанные по формулам (6.12). Так как 13EMBED Equation.31415=13EMBED Equation.31415=13EMBED Equation.31415=13EMBED Equation.31415=13EMBED Equation.31415 = 0, то соответствующие события являются критическими. Что касается напряженных работ, то таковыми являются работы s13EMBED Equation.31415 {3, 6, 9, 11). На рис. 16 соответствующие дуги отмечены жирными линиями.

Таблица 12
i
1
2
3
4
5
6
7
8

13EMBED Equation.31415
0
19
12
2
32
24
16
42

13EMBED Equation.31415
0
27
12

2
32
37
30
42

13EMBED Equation.31415
0
8
0
0
0
13
14
0


Лемма. Путь р = {s1, s2, .. ., sl} из 13EMBED Equation.31415= 1 в 13EMBED Equation.31415 = n в том и только том случае является критическим, когда соответствующим вершинам отвечают критические события, а дугам напряженные работы.













ЛЕКЦИЯ 7. Максимальные потоки. Теорема Форда и Фалкерсона.

Дана сеть, дуги которой ориентированы. В сети должны быть два специальных узла, называемых источник (исток) V0 и слив (сток) Vn. V0 – узел, у которого инвалентность равна нулю, а Vn – узел у которого аутвалентность равна нулю. Каждой дуге сети приписывается некоторое число. Это число является не длиной дуги, а скорее ее шириной.
Рассмотрим сети, которые представляют собой поток «товара» через серию каналов ("трубопроводов"). 'Товар' может фактически (но не только) представлять собой жидкость, текущую через сеть труб. Дуги просто представляют собой части сети транспортирования для специфического товара, и их веса представляют собой их максимальные пропускные мощности (возможности). Это могут быть, например, рельсы, дорожные или воздушные линии связи, или даже электрические или волокнисто-оптические кабели, если транспортируемый "товар" представляет собой цифровые сигналы. Т.е., если сеть это модель железной дороги, а узлы представляют железнодорожные станции, то число, приписанное дуге, может быть равно количеству путей между двумя станциями. Другой пример, если сеть моделирует трубопровод, а узлы являются сочленениями, то это число может представлять площадь сечения трубы между двумя сочленениями. Оно определяет наибольшее количество жидкости, которое может пройти через дугу. Это число будем называют пропускной способностью дуги. Пропускную способность дуги eij обозначим через bij. Предполагается, что bij >0 при всех i, j.
Задача о максимальном потоке в сети состоит в том, чтобы определить наибольшую величину потока, который может пройти из источника в слив.
Если D сеть, которая имеет несколько источников и/или сливов, рис. 22, а. Мы можем определить сеть N, добавляя два узла V0 и Vn. к D, соединяя V0 с помощью направленной дуги с каждым из источников и соединяя каждый слив с помощью направленных дуг с узлом Vn, рис. 22, б; N имеет единственный источник и единственный слив. Веса, которые должны соответствовать этим дополнительным ребрам зависят от того, что собой представляет данная сеть. В случае планирования проблем, дополнительным ребрам был бы присвоен вес 0, так, чтобы время на завершение всего проекта не было бы искусственно увеличено. Если D сеть для определения максимального потока, то ребрам, исходящим из источника присваивают значения пропускных способностей не менее чем, суммарная пропускная способность выходящих дуг из следующего звена, а дополнительным дугам, входящим в слив – сумму пропускных способностей входящих дуг в предыдущий узел, см. рис. 17 .

13 SHAPE \* MERGEFORMAT 1415
а) б)
Рис. 17. а - Сеть D; б – сеть N c одним источником и одним сливом

Поток в сети ведет себя не совсем так, как вода или другая жидкость. Обозначим через xij поток из Vi в Vj через дугу еij. Для потока имеется ограничение
13EMBED Equation.31415. (7.1)
Кроме ограничения (7.1), потребуем, чтобы приток в каждый узел был равен оттоку из него; т. е. поток сохраняется в каждом узле (за исключением источника и слива):
13EMBED Equation.31415 при всех 13EMBED Equation.31415. (7.2)
Т.к. поток сохраняется в каждом узле, то отток в источнике должен быть равен притоку в сливе:
13EMBED Equation.31415, (7.3)
где v – величина (цена) потока, т.е. полный поток приходящий на слив.
Набор значений xij, определенных для всех дуг сети и удовлетворяющих (7.1)-(7.3), называется потоком в сети. Поток наибольшей возможной величины называется максимальным потоком.
Легко видеть, что может существовать более одного максимального потока. Например, максимальная цена любого потока через сеть, представленную на рис. 18, a равна 3. В квадратных скобках дано значение пропускной способности каждой дуги, рядом поток по этой дуге. Имеются различные пути, которыми этот результат может быть достигнут. Максимальная цена всех возможных потоков равна 3, но имеется несколько различных максимальных потоков, которые достигают этого максимума. Два различных максимальных потока показаны на рис. 18, а и б.
13 SHAPE \* MERGEFORMAT 1415
а) б)
Рис. 18. Сеть с разными потоками и одинаковой ценой

Потоки в сетях широко используются во многих приложениях. Например, каково наименьшее число дуг, которые нужно удалить для разъединения двух заданных узлов графа? Этот вопрос является задачей теории графов, однако его можно решить, используя понятие потока.
Если сеть представляет собой цепочку V0, V1, V2, , Vk ,Vn, то наибольшая величина потока, который может пройти из V0 в Vn при выполнении (7.1)-(7.3), равна
13EMBED Equation.31415. (7.4)
Дуга с наименьшим значением пропускной способности является «узким местом» сети. Теперь определим понятие «узкого места» для произвольной сети. Узкое место сети называется разрезом.
Максимальная цена потока в сети тесно связана с идеей «разреза» сети, к описанию которой мы теперь переходим. Интуитивно ясно, что разрез можно рассматривать как множество ребер, которые, в случае их блокировки, полностью останавливают поток от источника к стоку. Однако, если какое-либо из ребер не заблокировано, то поток может и проходить. Сеть на рис. 18 имеет три различных разреза: {e1}, {е2, е3} и {е4}.
Разрезом сети N называется множество ребер, которое после удаления из N, порождают орграф с двумя компонентами, одна из которых содержит источник, а другая содержит слив.
И теперь более формальное определение разреза:
Разрез - это совокупность всех дуг, идущих из некоторого подмножества узлов в его дополнение. 0н обозначается через (13EMBED Equation.31415), где X заданное подмножество узлов, а 13EMBED Equation.31415- его дополнение. Таким образом, разрез (X, 13EMBED Equation.31415) - это множество всех таких дуг eij, что либо 13EMBED Equation.31415 и 13EMBED Equation.31415, либо 13EMBED Equation.31415 и 13EMBED Equation.31415. Удаление всех дуг из разреза разобьет сеть на две или более компоненты. Разрез, разделяющий узлы V0 и Vn - это такой разрез (13EMBED Equation.31415), что 13EMBED Equation.31415 и 13EMBED Equation.31415.
На рис. 19 сеть изображена условно.

13 SHAPE \* MERGEFORMAT 1415

Рис. 19. Условное представление сети и разреза

Емкостью разреза называется сумма весов его дуг.
Пропускная способность, или величина (емкость) разреза (13EMBED Equation.31415) определяется как 13EMBED Equation.31415, где 13EMBED Equation.31415 и 13EMBED Equation.31415.
Например, у сети, изображенной на рис. 18 разрез {e1} имеет емкость 4, разрез {е2, е3} – 14, и {е4} - 3.
Разрез является минимальным, если его емкость меньше или равна емкости любого другого разреза.
Замечание. В определении разреза учитываются все дуги между множествами X и 13EMBED Equation.31415, тогда как при вычислении его пропускной способности подсчитываются пропускные способности только дуг из X в 13EMBED Equation.31415, а дуги из 13EMBED Equation.31415 в X игнорируются. Поэтому в общем случае 13EMBED Equation.31415.
Величина максимального потока всегда совпадает с минимальной пропускной способностью разреза, разделяющего V0 и Vn. Разрез с наименьшей пропускной способностью, разделяющий V0 и Vn, называется минимальным разрезом.
Факт совпадения величины максимального потока с пропускной способностью минимального разреза впервые был доказан А.Фордом и Д.Фалкерсоном в 1955г. Это центральная теорема теории потоков в сетях.
Теорема Форда и Фалкерсона (о максимальном потоке и минимальном разрезе). В любой сети с целыми значениями пропускных способностей дуг величина максимального потока из источника в слив равна пропускной способности минимального разреза, разделяющего источник и слив.
Доказательство. Дадим конструктивное доказательство теоремы, которое строит максимальный ноток и находит минимальный разрез. Доказательство показывает, что всегда существует поток, значение которого равно пропускной способности минимального разреза. Поскольку максимальный поток всегда не превосходит пропускной способности произвольного разреза, в частности, минимального разреза, то это и доказывает справедливость теоремы.
Если текущая величина потока равна пропускной способности некоторого разреза, то теорема доказана. Если величина потока не равна пропускной способности разреза, то ищем среди путей из V0 в Vn такой, вдоль которого можно послать дополнительный поток. Это увеличивает величину потока. Продолжаем данную процедуру до тех пор, пока такого пути нельзя будет найти. Докажем, что величина потока равна пропускной способности некоторого разреза. Опишем систематический способ отыскания такого пути.
Начнем с произвольного множества величин Хij, удовлетворяющих (6.1) и (6.2) (например, Xij = 0 при всех i и j). На основе текущего потока в сети рекурсивно определим подмножество узлов X при помощи следующих правил.
0. 13EMBED Equation.31415.
1. Если 13EMBED Equation.31415 и 13EMBED Equation.31415, то 13EMBED Equation.31415.
2. Если 13EMBED Equation.31415 и 13EMBED Equation.31415, то 13EMBED Equation.31415.
Все узлы, не лежащие в X, принадлежат 13EMBED Equation.31415. Используя данные правила определения множества X , рассмотрим два возможных случая.
Случай 1. 13EMBED Equation.31415. Следовательно, для всех дуг из X в 13EMBED Equation.31415 справедливо 13EMBED Equation.31415 (в силу правила 1) и не существует потока 13EMBED Equation.31415 через дугу из 13EMBED Equation.31415 в X (в силу правила 2). Поэтому
13EMBED Equation.31415 и 13EMBED Equation.31415
Следовательно, найден поток со значением, равным с(13EMBED Equation.31415).
Случай 2. 13EMBED Equation.31415. Тогда существует путь из V0 в Vn, образованный дугами, удовлетворяющими правилу 1 или правилу 2. Обозначим этот путь V0,, Vi, eij, Vj ,,Vn. Каждая дуга в данном пути должна удовлетворять либо правилу 1, либо правилу 2. Если дуга удовлетворяет правилу 1, т. е. 13EMBED Equation.31415, то можно отправить дополнительный поток из Vi в Vj. Это увеличивает величину потока вдоль дуги. Такой тип дуги называется прямой дугой. Если же дуга удовлетворяет правилу 2, т. е. 13EMBED Equation.31415, то можно отправить поток из Vj, в Vi, фактически отменяя существующий поток вдоль дуги. Эффект состоит в сокращении величины потока вдоль дуги. Такой тип дуги называется обратной дугой. Данный путь по отношению к текущему потоку называется увеличивающим путем.
Например, возьмем сеть на рис. 20, где числа в квадратных скобках обозначают пропускные способности дуг. Если потоки на дугах равны x01 = х12 = x2n = 1, а все остальные xij = 0, то е03,е32,е21, e4n является увеличивающим путем с обратной дугой e21.

13 SHAPE \* MERGEFORMAT 1415

Рис. 20.

Пусть
·1 минимум среди всех разностей bij - xij в этом пути,
·2 - минимум среди xji в нем, а
· = min{
·1,
·2} целое положительное число. Тогда можно увеличить дуговые потоки на
· по всем прямым дугам пути и уменьшить дуговые потоки на
· по всем его обратным дугам. Таким образом, величина потока увеличивается на
· и новые значения xij удовлетворяют всем ограничениям (7.1) и (7.2). Теперь на основе нового потока можно переопределить множество X. Если Vn все еще лежит в X, то снова увеличиваем величину потока на некоторое
·. Поскольку пропускная способность минимального разреза конечное число, а величина потока увеличивается по крайней мере на единицу, то после конечного числа шагов будет получен максимальный поток.
Теорема доказана.

Обозначим через F0n набор неотрицательных целых чисел xij, удовлетворяющих (6.1)-(6.3).
Следствие. Поток F0n максимален тогда и только тогда, когда относительно F0n не существует увеличивающего пути.

















Лекция 8. Метод нахождения максимального потока.
Теорема о максимальных разрезах

Величина максимального потока в любой сети определяется единственным образом, и может существовать несколько потоков, дающих наибольшую величину потока. Также в сети может существовать и несколько минимальных разрезов. Например, рассмотрим сеть на рис.21.
Пусть пропускная способность каждой дуги равна единице. Тогда обе дуги е23 и e5n являются минимальными разрезами. Величина максимального потока в точности равна 1, однако максимальным потоком может быть как x01 =x12 = x23 = x34 = x45 = x5n = 1, так и x06 = x62 = x23 = x37 = x75 = x5n = 1.

13 SHAPE \* MERGEFORMAT 1415
Рис. 21.

Метод обнаружения максимального потока. Он основан на доказательстве теоремы Форда и Фалкерсона. Основная идея состоит в том, чтобы начать с некоторого потока и, если этот поток уже не является максимальным, улучшить его. Относительно нетрудно найти некоторый поток.
Пример. 8.1. Рассмотрим сеть, показанную на рис. 22,а и предположим, что мы начинаем с потока, показанного на рис. 22, б, который имеет цену 15 и очевидно не является максимальным.
Чтобы улучшить поток, нам следует заменить его новым потоком, имеющим большую цену. Чтобы сделать это, прежде всего, посмотрим на направленный путь, идущий от источника к стоку и обладающий тем свойством, что поток в каждой дуге пути строго меньше его пропускной способности. Пример такого пути приведен на рис. 22,а (хотя имеются и другие возможности выбора пути с такими свойствами). Для данного пути вычислим минимальную цену 13EMBED Equation.31415 для совокупности его дуг. Оказывается возможным увеличить поток в каждом ребре пути на вычисленное значения, задавая новый поток с ценой, превышающей первоначальную. Минимальная цена 13EMBED Equation.31415 для дуг пути, представленного на рис. 22, б, равна 2. Когда поток в каждой дуге этого пути будет увеличен на 2, мы получим поток с ценой 17.






13 SHAPE \* MERGEFORMAT 1415
а)

13 SHAPE \* MERGEFORMAT 1415
б)
Рис. 22.

Результат нескольких повторений этого процесса производит поток с ценою 24, показанный на рис. 23, в. Для этого потока уже не существует ни одного направленного пути от источника к стоку, обладающего тем свойством, что для каждой дуги пути, поток проходящий через дугу оказывается строго меньшим емкости дуги. В связи с этим может показаться, что найденный поток является максимальным. Однако это не так, но дальнейшее улучшение потока требует некоторых ухищрений.
Рассмотрите путь, показанный на рис.24,а. Это не направленный путь от источника к стоку; строго говоря, мы должны расценить его как путь в основном ненаправленном графе. Поток в каждой из трех ребер, направленных «вперед» строго меньше их емкости, и поток в ребре направленном «назад» положителен. Если мы увеличиваем поток в каждой из дуг с потоком «вперед» на 1 (на минимальную цену 13EMBED Equation.31415 из совокупности цен для дуг, направленных «вперед») и уменьшим на 1 поток в дуге направленном «назад», то в результате поток все еще останется консервативным и при этом его цена будет увеличена на 1. Результирующий поток, с ценой 25, показан на рис.24, б. Других ненаправленных путей рассмотренного типа от источника к стоку в данном примере нет. (То есть, нет больше таких путей, у которых поток через все дуги, направленные вперед может быть увеличен без превышения их емкости, а поток через все дуги направленные назад может быть уменьшен, не становясь отрицательным.) Это означает, что поток, показанный на рис. 23, б является действительно максимальным.



13 SHAPE \* MERGEFORMAT 1415
а)

13 SHAPE \* MERGEFORMAT 1415
б)

13 SHAPE \* MERGEFORMAT 1415
в)

Рис. 23.

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

13 SHAPE \* MERGEFORMAT 1415
а)
13 SHAPE \* MERGEFORMAT 1415
б)
Рис. 24

Если мы можем найти срез со значением емкости равным 25 значению, совпадающему со ценой потока, то мы из этого факта может сделать заключение, что такой поток действительно является максимальным (и конечно, срез является минимальным). Такие разрезы показаны на рис. 24. Таким образом,

Приложенные файлы

  • doc 8931084
    Размер файла: 3 MB Загрузок: 0

Добавить комментарий