Задача 5. Алгоритм Дейкстры
Вариант №70
Задачи по комбинаторике
Задача 1
На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений на английском языке. Сколькими способами читатель может выбрать 3 книги, если:
а) словарь ему не нужен;
б) словарь нужен ему обязательно?
Решение
а) 
б) 
Ответ:165 способами; 55 способами.
Задача 2
Сколько может быть случаев выбора 2 карандашей и 3 ручек из пяти различных карандашей и шести различных ручек?
Решение
Количество выборов карандашей равно 
, а ручек – 
. Используя правило умножения, получаем
Ответ:200 случаев.
Задача 3
Предприятие может предоставить работу по одной специальности 4 женщинами, по другой - 6 мужчинам, по третьей - 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?
Решение
Имеем 14 претендентов и 13 рабочих мест. Сначала выберем работников на первую специальность, то есть 4 женщин из 6:
Далее независимо аналогичным образом выберем мужчин на вторую специальность:
Осталось 2 женщины, 2 мужчин и 3 вакантных места, которые, по условию, могут занять любые из четырех оставшихся человек. Это может быть сделано 2 вариантами:
1. 1 женщина и 2 мужчин (выбираем женщину 
способами)
2. 1 мужчина и 2 женщины (выбираем мужчину 
способами).
В итоге получаем 
1 680 способов.
Ответ: 1 680 способов.
Задача 4
Пусть есть 10 шариков: 2 красных, 3 синих и 5 жёлтых. Сколькими способами можно выложить узор, размещая шарики на дощечку с 10-ю местами?
Решение
2 520.
Ответ:2 520 способами.
Задача 5
Сколько перестановок можно сделать из букв слова «МИССИСИПИ»?
Решение
Всего букв 9. Из них одинаковы «и» = 4, «с»=3, «м»=1, «п»=1. Следовательно, число различных перестановок равно
2 520.
Ответ:2 520 перестановок.
Задачи по теории графов
Задача 1.Максимальные полные подграфы (клики)
Максимальный полный подграф (клика) графа G есть порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершинH, содержащих S, не является полным. Следовательно, в клике все вершины попарно смежны. Возможно также определить кликовое число графа(известное также как густота или плотность) - это максимальное число вершин в кликах данного графа.
В неориентированном графе заданном матрицей смежностей выделить клики.
Пусть задан неориентированный граф G1 матрицей смежностей M1
Берем первую строку, находим первую единичку по адресу (1,2).
На основе наблюдений приходим к выводу, что для отыскания клик в неориентированном графе нужно выделить в исходной матрице смежностей подматрицы указанного выше вида, множества вершин образующие эти матрицы и будут вершинами клики. Но по определению клики нам подойдут не все такие множества, а лишь оригинальные не содержащих в себе других множеств вершин. Так что вторая задача будет сводится к выделению из полученных множеств оригинальных, не содержащих в себе других подмножестве. То что исходная матрица смежностей симметрична относительно главной диагонали позволят нам осуществлять поиск подматриц только в ее верхнем или нижнем треугольнике.
Шаг 1.
Идем по матрице как показано на рисунке 3.2 а и ищем первую попавшуюся единичку (рис 3.2 б) запоминаем ее координаты (R,C) .
Шаг 2.
Ищем следующую 1 по адресу (R,C1)
Шаг 3.
Начинаем спускаться по столбцу (С1) в поисках 1 , причем ищем ее по адресу (С,С1), так как в исходной матрице столбцы попарно смежных вершин не обязательно соседствуют. Запоминаем строку каждой найденной таким образом 1 для поиска в следующих столбцах. Увеличиваем длину множества вершин на 1.
Количество повторений шага 3 равно текущему размеру множества вершин.
Если по указанному адресу мы не встречаем 1 то значит данный столбец не образует подматрицу смежностей клики - пропускаем его. Начинаем Шаг 2.
Если размер множества вершин образующих клику больше 2 то запоминаем это множество.
Так до конца строки.
Повторяем Шаг 1 для всех 1 в строке.
Таким образом, проходим всю матрицу. На выходе получаем несколько множеств вершин, отбираем среди них только оригинальные, не содержащие в себе других подмножеств.
Отобранные подмножества и есть клики заданного графа.
Работа алгоритма. Запоминаем адрес первой 1 (1,2). Ищем следующую 1 в первой строке. Она находится по адресу (1,5). Проверяем адрес (2,5) на 1. Там ее нет. Пропускаем 5-й столбец. Находим следующую 1 в 6 столбце. Проверяем адрес (2,6) на 1. Там ее нет. так до конца строки. Убеждаемся что в данном цикле сравнений матрица смежностей получаемой клики имеет размерность два. Что означает наличие в клике двух вершин - простейшее сочетание - оно не рассматривается в моей программе. Мы записываем в файл клик клики не меньше третьего порядка.
Выбираем в первой строке следующую 1. Она находится по адресу (1,5) запоминаем этот адрес в массиве строк. Ищем следующую 1 в первой строке. Она находится по адресу (1,6). Спускаемся по 6 столбцу, проверяем адрес (5,6) на 1. Она там есть. Количество найденных 1 в 6 столбце =размеру массива содержащего множества. Тогда увеличиваем длину этого массива на 1 и записываем туда 6. Получаем в массиве [1,5,6]. И т.д.
В итоге получим клики с номерами вершин: 1 5 6 8; 6 4 8; 1 7 8.
Матрица смежностей клики 1568.
1 5 6 8
10 1 1 1
51 0 1 1
61 1 0 1
81 1 1 0
Задача 2. Поиск в ширину
Рассмотрим метод поиска в графе, называемый поиском в ширину (англ: breadth first search). Прежде чем описать его, отметим, что при поиске в глубину чем позднее будет посещена вершина, тем раньше она будет использована — точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не использованные вершины скапливаются в стеке. Поиск в ширину, грубо говоря, основывается на замене стека очередью. После такой модификации, чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще не просмотренных соседей этой вершины. Вся процедура поиска представлена ниже (данная процедура используется также и для просмотра графа, и в псевдокоде, описанном ниже, отсутствуют операторы, которые не используются для поиска).
1 procedure WS (v);
(*поиск в ширину в графе с началом в вершине v;
переменные НОВЫЙ, ЗАПИСЬ — глобальные *)
2 begin
3 ОЧЕРЕДЬ := Æ; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь
4 while ОЧЕРЕДЬ ¹ Æ do
5 begin р<= ОЧЕРЕДЬ; посетить р;
6 for u Î ЗАПИСЬ [р] do
7 if НОВЫЙ [u] then
8 begin ОЧЕРЕДЬ <= u; НОВЫЙ [u]:=ложь
9 end
10 end
11 end
На рис. 1 представлен граф, вершины которого занумерованы согласно очередности, в которой они посещаются в процессе поиска в глубину.
Как и в случае поиска в глубину, процедуру WS можно использовать без всяких модификаций и тогда, когда списки инцидентности ЗАПИСЬ[v], v = V, определяют некоторый ориентированный граф. Очевидно, что тогда посещаются только те вершины, до которых существует путь от вершины, с которой мы начинаем поиск
 | |||||
| | |||||
|
Рис. 1 Нумерация вершин графа (в скобках), соответствующая очередности, в которой они просматриваются в процессе поиска в ширину.
Задача 3. Раскраска графа
Граф называется вершинно-К-раскрашенным, если его вершины можно раскрасить К-красками так, чтобы никакие две вершины не имели бы одинаковый цвет. Минимальное число К, при котором граф G является вершинно-К-раскрашенным называется хроматическим числом графа.
Раскрасить граф можно используя следующий алгоритм:
1. Найти число связей всех вершин графа.
2. Рассматривать вершины в порядке не возрастания числа связей.
3. Начинаем раскрашивание в цвет №1. Рассматриваем вершины последовательно и если рассматриваемая вершина не раскрашена, а также не имеет связей с вершинами раскрашеными в этот цвет, то раскрашиваем её в этот цвет.
4. Если все вершины просмотрены, но не раскрашены, то повторяем пункт 3, с цветом на единицу больше, пока все вершины не раскрашены. Число цветов это и есть хроматическое число.
Пример:
Раскрасить граф
Вычислим степени
Рассматриваем вершины в порядке не возрастания числа связей. Те которые не связаны с вершинами раскрашеными в цвет №1 раскрашиваем в цвет №1
Рассматриваем вершины в порядке не возрастания числа связей. Те которые не связаны с вершинами раскрашеными в цвет №2 раскрашиваем в цвет №2
Рассматриваем вершины в порядке не возрастания числа связей. Те которые не связаны с вершинами раскрашеными в цвет №3 раскрашиваем в цвет №3
Все вершины графа раскрашены, число цветов 3 ==> хроматическое число равно трем.
Задача 4. Алгоритм Диница
Этот алгоритм, опубликованный в 1970 г., имел огромное значение. На протяжении 10 лет все достижения в решении задачи о максимальном потоке базировались на методе Диница.
Основная идея метода – алгоритм состоит из фаз, на которых поток увеличивается сразу вдоль всех кратчайших цепей определенной длины. Для этого на i-той фазе строится вспомогательная бесконтурная сеть (layered network). Эта сеть содержит все увеличивающие цепи, длина которых не превышает ki, где ki – длина кратчайшего пути из s в t. Величину ki называют длиной вспомогательной сети.
Рассмотрим работу алгоритма на i-той фазе:
Шаг 1. Построение вспомогательной сети.
С помощью поиска в ширину мы движемся из источника сети в сток по допустимым дугам, добавляя их в Sk и увеличивая k. Дуга u добавляется с ck(u) = c(u) – f(u). Как только достигнут сток сети, он помечается величиной k и k становится “фиксированной”. Мы продолжаем поиск в ширину, но он уже не ведется из вершин v, для которых q(s, v) k. Таким образом, вспомогательная сеть будет содержать подсеть исходной. Если поиск в ширину не достиг стока, то работа алгоритма прекращается. Если k больше (k может только увеличиваться) ki, то мы находимся на i+1 фазе с ki+1 = k.
Шаг 2. Поиск псевдомаксимального потока.
В построенной нами бесконтурной сети длины k ищется псевдомаксимальный поток. Под псевдомаксимальным потоком понимается такой поток f, для которого не существует увеличивающих цепей длины k. Найденный поток переносится в исходную сеть. Затем мы вновь переходим к первому шагу.
Для построения псевдомаксимального потока используется поиск в ширину (с ограничением на длину пути). Пусть на j-той итерации был найден путь из s в t. Пустим по этому пути поток fj. Это значит, что как минимум одна дуга вспомогательной сети является насыщенной. Удалим все насыщенные дуги. В результате могут образоваться “тупики”: вершины, из которых не выходит ни одна дуга (кроме стока), вершины, в которые не входит ни одна дуга (кроме источника) и изолированные вершины. Их также следует удалить со всеми инцидентными им дугами. Это в свою очередь может привести к образованию новых тупиков. Корректировка производится, пока во вспомогательной сети не останется ни одного тупика. Изменим пропускные способности оставшихся дуг по формуле ck(u) = ck(u) – fj(u).
рис. 1
На рисунке вершины 2 и 5 являются тупиками. После их удаления будут последовательно удалены все вершины сети.
Поиск fj следует продолжать до тех пор, пока вспомогательная сеть Ø. Очевидно, что псевдомаксимальный поток f = fj. Псевдомаксимальный поток можно хранить в какой-либо структуре, но на практике найденные потоки fj обычно сразу переносятся в исходную сеть S.
Заметим, что после нахождения fi и корректировки сети, поиск в ширину можно продолжать с ближайшей к s не подвергшейся изменениям дуги найденного пути.
После завершения работы Алгоритма исходная сеть будет содержать максимальный поток. Пример:
рис. 2.
Сеть с уже найденным с помощью алгоритма Диница максимальным потоком.
рис. 3.
Вспомогательная сеть на 1 фазе. k1 = 2.
рис.4.
Вспомогательная сеть на 2 фазе. k2 = 3. На этой сети хорошо видно, что псевдомаксимальный поток обычно не является максимальным.
рис.5.
Вспомогательная сеть на 3 фазе. k3 = 5.
Задача 5. Алгоритм Дейкстры.
Рассмотрим задачу в общем виде. Пусть дан граф G=(X,Г), дугам которого приписаны веса (стоимости), задаваемые матрицей С=||с 
||. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной вершины s 
X до заданной конечной вершины t X., при условии, что такой путь существует, т.е. при условии t R(s). Здесь R(s)- множество вершин, достижимых из вершины s.
Элементы с могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с суммарным отрицательным весом.
Из общей задачи о кратчайшем пути вытекают две подзадачи:
а) для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами x 
X;
б) найти кратчайшее расстояние между всеми парами вершин.
Рассмотрим задачу определения кратчайшего пути между заданными вершинами s и t для случая c >0, 
i , j . Наиболее эффективный алгоритм решения задачи о кротчайшем (s-t) пути первоначально дал Дейкстра. В общем случае этот метод основан на приписывании вершинам временных пометок, причём пометка вершины даёт верхнюю границу длины пути от s к этой вершине. Эти пометки (их величины) постепенно уменьшаются с помощью итерационной процедуры, и на каждом шаге итерации только одна из временных пометок становиться постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а даёт точную длину кратчайшего пути от s к рассматриваемой вершине.
Рассмотрим действие алгоритма на примере. Пусть дан граф G, показанный на рисунке 1, где каждое неориентированное ребро рассматривается как пара противоположно ориентированных дуг равного веса. Матрица смежности весов С приведена ниже. Требуется найти все кратчайшие пути от вершины x, ко всем остальным вершинам. Для решения задачи воспользуемся алгоритмом Дейкстры, который является одним из самых быстрых для поиска кратчайшего расстояния от некоторой вершины до всех остальных.
Рисунок 1. Смешанный граф
Решение.
Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.
Шаг 1.
l(x 
) = 0 
, l(x 
) = , x 
x ,p = x .
Первая итерация
Шаг 2.
Г( p) = Г(x ) = { x 
} – все пометки временные.
Применяя (2) , получим
l(x ) = min { 
; 0+4}= 4,
Так как на первой итерации вершина только одна , то шаг 3 по выбору минимума опускается.
Шаг 4.
l(x )=4 ; p= x .
Шаг 5.
Не все вершины имеют постоянные пометки.
Переход к следующей итерации.
| i / j | x
| x
| x 
| x 
| x 
| x 
|
x 
| --------- | |||||
| x
| --------- | |||||
| x
| --------- | |||||
| x
| --------- | |||||
| x
| --------- | |||||
| x
| --------- |
Таблица 1- Матрица смежности весов .
Вторая итерация.
Шаг 2.
Г( p) = Г(x ) = { x , x 
, x , x }.
l(x ) = min { ; 4+3}= 7,
l(x ) = min { ; 4+2}= 6,
l(x ) = min { ; 4+3}= 7.
Шаг 3.
min{l(x ); l(x ); l(x )} = min{7,6,7} = 6.
Шаг 4.
l(x ) = 6 ; p = x .
Шаг 5. Переход к следующей итерации.
Третья итерация.
Шаг 2.
Г( p) = Г(x 
) = { x , x , x }.
l(x ) = min {7; 7+4} = 7,
l(x ) = min {7; 6+2} = 7.
Шаг 3.
min{l(x ); l(x 
)} = min{7,7} = 7.
Выбираем любую вершину.
Шаг 4.
l(x ) = 7 ; p = x
Шаг 5. Переход к следующей итерации.
Четвёртая итерация.
Шаг 2.
Г( p) = Г(x ) = { x , x , x , x }.
l(x ) = min { ; 7+5} = 12.
l(x ) = min {7; 6+2} = 7.
Шаг 3.
min{ l(x ); l(x ) }= min{7,12} = 7.
Шаг 4.
l(x ) = 7 ; p = x
Шаг 5. Переход к следующей итерации.
Пятая итерация.
Шаг 2.
Г( p) = Г(x ) = { x ,x , x , x }.
l(x ) = min { ; 7+3}=10.
Шаг 3.
min(x ) =10.
Шаг 4.
l(x ) = 10 ; p= x .
Шаг 5. Все вершины имеют постоянные пометки. Остановка. Окончательная расстановка пометок приведена на рис.3
Для нахождения кратчайшего пути между вершиной x (например) и начальной вершиной применяем последовательно соотношение l(x ’) + c(x ’,x ) = l(x ) . Таким образом, полагая x =x , находим вершину x ’ , непосредственно предшествующую x в кратчайшем пути от x к x ; вершина должна удовлетворять соотношению
l(x ’)+ C(x ’, x ’ )= l(x ’ )= 10.
Одной из таких вершиной является х = x ’.
Продолжая аналогичные рассуждения, получим :
l(х 
’) + C(х ’, х ) = l(х ) = 7 
х ’ = x 
.
l(x ’) + C(x ’, x ) = l(x ) = 6 x ’ = x 
.
l(x ’) + C(x ’, x )= l(x ) = 4 x ’ = x
Таким образом, кратчайший путь от вершины x к вершине x проходит через вершины x , x и х . То есть 
( x , x ) = (x , x , x , х , x ). Путь на рисунке выделен черным цветом.
Рисунок 2- Окончательные пометки вершин графа.
Список литературы
1. Н. Кристофидес, Теория графов. М.: «Мир» 1978г. ;
2. Вялых Б. И,, Сукманов С. А. Дискретная математика. ТАИИ 2004г;
3. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965г;
4. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986г.