- •Задачи для программирования по темам
- •Направление ″бизнес-информатика″, специальность ″математические методы в экономике″
- •1 . Обходы графа . Вычисление числа компонент связности графа.
- •2. Алгоритмы поиска путей в графе.
- •3. Алгоритмы нахождения минимального остова в графе
- •4. Хроматическое число графа. Алгоритм правильной раскраски вершин графа методом перебора с возвратами.
- •5. Транспортные сети. Теорема форда-фалкерсона о максимальном потоке в транспортной сети
- •6А. Варианты задач для групп по направлению ″бизнес-информатика″ тема ″транспортные сети″
- •6Б. Варианты задач для групп по специальности ″математические методы в экономике″
- •7.Задачи по теме ″рекурсивные функции″.
- •1. Доказать, что следующие функции примитивно рекурсивны:
- •8. Задачи по теме ″машины тьюринга″
- •2. (Гаврилов г. П., Сапоженко а.А. Задачник. С. 220-221, идея из № 1.2.) Построить машину в алфавите , , которая:
- •3. (Гаврилов г. П., Сапоженко а.А. Задачник. С. 221, № 1.3.) По заданной машине Тьюринга и начальной конфигурации найти заключительную конфигурацию:
- •4. (Лавров и.А., Максимова л.Л. С. 138, № 1.) Какую функцию вычисляет машина Тьюринга со следующей программой п:
- •5. (Лавров и.А., Максимова л.Л. С. 139, № 5.) Построить следующие машины Тьюринга в алфавите , , начальную конфигурацию в заключительную конфигурацию :
4. Хроматическое число графа. Алгоритм правильной раскраски вершин графа методом перебора с возвратами.
Определения и постановка задачи.
Даны простой неориентированный граф с множеством вершин и множеством рёбер (граф простой, значит. без петель и кратных дуг).
Вершинная -раскраска графа – это присвоение его вершинам цветов из множества . Раскраска называется правильной, если никакие две смежные вершины не получают одного цвета.
Хроматическим числом графа называется минимальное число , при котором существует правильная раскраска вершин графа в цветов.
Очевидно, что .
Задача: вычислить .
Функция возвращает значение для графа , заданного каким-либо образом (например, матрицей или структурой смежностей). Попутно вычисляется вектор , где – цвет, который получает -ая вершина. При вычислении используется вспомогательная функция , возвращающая значение e (ложь), если правильная -раскраска графа не существует, и возвращает значение e, если существует; в последнем случае вычисляется значение – число использованных красок.
если раскраска существует, то можно считать, что вершина 1 получила цвет 1
for do остальные вершины пока цвета не имеют
i← 2;
Далее поиск правильной -раскраски осуществляется методом перебора с возвратами
while do начинаем раскраску со второй вершины
if then {назад: }
else
if цвет вершин, смежных с -ой вершиной, отличен от
then {вперед: }
od; конец цикла while
if then return (false)
else { ← число различных цветов в ; return (true)}.
Теперь вычисляем хроматическое число графа
;
;
for do ;
while do
{;; ← };
return ().
5. Транспортные сети. Теорема форда-фалкерсона о максимальном потоке в транспортной сети
Определение. Транспортная сеть − это связный ориентированный граф без петель, удовлетворяющий следующим условиям:
1. Существует только одна вершина с нулевой степенью захода; эта вершина называется источником и обозначается через .
2. Существует только одна вершина с нулевой степенью исхода; эта вершина называется стоком и обозначается через .
3. Каждой дуге в сети сопоставляется неотрицательное вещественное число, называемое пропускной способностью дуги ; оно обозначается через или . (Если не существует дуги, ориентированной из в , то полагаем, что .)
Моделью транспортной сети может служить водопроводная система, в которой сечения труб определяют пропускные способности соответствующих труб, т.е. количество жидкости. которое может пропустить труба за единицу времени.
Потоком в транспортной сети является функция, сопоставляющая каждой дуге неотрицательное вещественное число так, что выполняются следующие условия:
1. для любой дуги ;
2. для любого .
(Требование 2 − это условие сохранения баланса. Образно говоря, ″сколько втекает в вершину, столько и вытекает из неё″.)
Величина потока обозначается через и определяется выражением
.
Говорят, что поток максимален, если не существует потока такого, что >.
Постановка задачи. Найти максимальный поток в заданной транспортной сети.
Пусть , . Разрез , определяется как множество дуг, у которых начало и конец лежат в разных подмножествах и . Разрез состоит из прямых дуг, ориентированных из в , и обратных дуг, ориентированных из в . Если , , то соответствующий разрез называется (- ) - разрезом. См. рис. 1.
Далее рассматриваются только - - разрезы.
Пропускная способность , разреза , определяется как сумма пропускных способностей прямых дуг разреза. Разрез, пропускная способность которого не больше, чем у любого другого разреза, называется минимальным. (В транспортной сети может быть несколько минимальных разрезов, конечно, с одинаковыми пропускными способностями.)
Поток из в определяется как
Аналогично определяется поток из в :
1. Лемма. Для любого - - разреза <,> имеет место равенство
.
Доказательство. Для фиксированного имеем
Суммируя по всем , получаем
С другой стороны,
2. Следствие. Для любого потока и любого - - разреза <,>
(,).
Доказательство.. ∎
Для потока и разреза <,> прямую дугу, где , , будем называть -насыщенной (соответственно, -не), если (соответственно, если ). Обратную дугу , где , , будем называть -нулевой (соответственно, -положительной), если (соответственно, если ).
3. Лемма. Если величина потока равна пропускной способности некоторого разреза ,, то − максимальный поток, а − минимальный разрез. Для данного разреза прямые дуги являются насыщенными, а обратные − нулевыми.
Доказательство. Пусть − максимальный поток, а − минимальный разрез. Так как и, по условию, , то . ∎
Рассмотрим в транспортной сети цепочку рёбер
, ,, , ,
соединяющую источник и некоторую вершину . Заметим, что рёбра получаются из дуг путём снятия ориентации. Соответствующие дуги, составляющие цепочку, могут быть как прямыми, т.е. ориентированными из в , так и обратными, т.е. ориентированными из в .
Для ребра полагаем
Цепочка называется -ненасыщенной, если . -ненасыщенная цепочка из в называется -дополняющей.
Наличие в сети -дополняющей цепочки позволяет увеличить величину потока, вводя новый поток
При этом
.
4. Теорема. Поток в транспортной сети максимален тогда и только тогда, когда в сети отсутствуют -дополняющие цепочки.
Доказательство. Необходимость. Если поток максимален, то в сети заведомо нет -дополняющих цепочек. В противном случае можно было бы построить новый поток , величина которого больше, чем у потока .
Достаточность. Предположим, что сеть с потоком не содержит -дополняющих цепочек. Покажем, что в этом случае − максимальный поток.
Разобьём множество вершин сети на два непересекающихся подмножества и : в включим те вершины , до которых существуют -ненасыщенные цепочки из источника , а в включим остальные вершины, т.е. . Очевидно, что .
Пусть − произвольная дуга разреза ,. Если − прямая дуга, т.е. , , то является -насыщенной дугой, поскольку иначе существует -ненасыщенная цепочка из в и . Аналогично, если − обратная дуга, т.е. , , то является -нулевой дугой. Таким образом, для прямых дуг и для обратных дуг разреза <,>. Тогда ,,, , и ,,,. Из леммы 3 вытекает, что <,> − минимальный разрез, а − максимальный поток.∎
5. Следствие (теорема Форда-Фалкерсона). Величина максимального потока в транспортной сети равна пропускной способности минимального разреза.
ПОМЕЧАЮЩИЙ АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПОТОКА В ТРАНСПОРТНОЙ СЕТИ
Алгоритм основан на теореме 4 и состоит из двух фаз.
На первой фазе, используя помечающую процедуру, устанавливаем, существует ли в сети -дополняющая цепочка. Если такой цепочки нет, то согласно теореме 4 поток в сети максимален (конец алгоритма). В противном случае переходим ко второй фазе, в которой, используя метки, полученные на первой фазе, строим новый поток такой, что . Фазы 1 и 2 повторяются до тех пор, пока не будет построен максимальный поток.
Метка, которую может получить вершина на фазе 1, имеет вид (, , ), где символ указывает на вершину, от которой получена метка, указывает направление помечивания − прямое () или обратное (), наконец, = , если существует -ненасыщенная цепочка из в .
Помечивание начинается с пометки источника, который получает метку
, , , где значение несущественно. Помечивание остальных вершин происходит по следующим правилам.
Прямое помечивание. Если , то прямое помечивание из возможно, если вершина уже помечена и . При этом вершина получает метку , , , где .
Обратное помечивание. Если , то обратное помечивание из возможно, если вершина уже помечена и . При этом вершина получает метку , , , где .
Фаза 1 завершается, если либо 1) вершина (сток) помечена, либо 2) вершина не помечена и ни одну из непомеченных вершин не удаётся (нельзя) пометить. В пределах фазы каждая вершина помечается лишь один раз.
Если сток получил метку в первой фазе, то из правил помечивания следует, что в сети существует -дополняющая цепочка и >0. Во второй фазе эта цепочка прослеживается в обратном направлении (начиная с ) с помощью символов , что позволяет построить новый поток с увеличенным значением .
Алгоритм Форда-Фалкерсона.
Вход: транспортная сеть , заданная матрицей (), где =(, ), , , пропускных способностей, или каким-нибудь другим способом.
(Начинаем с нулевого потока.)
for е ∈ E do f(e):= 0;
(Фаза 1.)
Удаляем все метки вершин;
Помечаем источник;
while вершина t не помечена и существует непомеченная вершина v do
помечаем вершину v;
od;
if сток не помечен then конец: максимальный поток построен;
(Фаза 2.)
v:= t; u:= dv;
while v ≠ s do
if bv = ″+″ then f(u,v):= f(u,v)+ ∆t
else f(u,v):= f(u,v)− ∆t;
v:= u
od;
Возврат на фазу 1.
Выход: максимальный поток f.