Программа, методические указания и контрольные задания Для студентов-заочников Казань, 2009 г

Вид материала

Содержание

Методические указания к выполнению и оформлению контрольной работы
Пример выполнения контрольной работы
Разрезом сети
Пропускной способностью
Минимальным разрезом

Подобный материал:

1 2 3

Рис. 2

Определим кратчайшее расстояние между вершинами x₁ и x₈.

На нулевой итерации полагаем L^*(x₁)= 0 (знак * у метки означает, что рассматриваемая метка постоянная); L(x_j) = ∞ (j=2, 3, ..., 8) - все вершины, кроме первой, имеют временные метки.

Первая итерация

Шаг 1. Пусть Г(x₁) - множество вершин - последователей вершины x₁ . В нашем случае Г(x₁) = {x₂, x₃, x₄, x₆.} Вычисляем новые временные метки вершин из Г(x₁) в соответствии с (1).

L(x₂) = min {∞, 2+0} = 2,

L(x₃) = min {∞, 1+0} = 1,

L(x₄) = min{∞, 6+0} = 6,

L(x₆) = min{∞, 9+0} = 9.

Шаг 2. Превращаем временные метки в постоянные:

min L(x_j) = min _2≤_j_≤8 {2, 1, 6,∞, 9, ∞, ∞} = 1.

Вершина x₃, как имеющая минимальную временную метку, получает постоянную метку L^* (x₃) = 1.

Результаты вычислений будем оформлять в виде табл. 3. Причем записывать будем только обновленные метки и помечать их в том столбце, в котором они родились. Кроме того, для каждой итерации в строке под номером итерации будем помещать вершину, отмеченную “звездочкой” на предыдущей итерации.

Таблица 3

Вершины	Итерации
	0	1	2	3	4	5	6	7
		x₁	x₃	x₂	x₅	x₄	x₇	x₆
x₁	0^*
x₂	∞	2^*
x₃	∞	1^*
x₄	∞	6		5	4^*
x₅	∞		2^*
x₆	∞	9				6^*
x₇	∞				5^*
x₈	∞						6^*

Вторая итерация

Шаг 1. Рассматриваем Г(x₃) = {x₁, x₅}.

Временную метку имеет только вершина x₅. Обновляем ее (метку).

L (x₅) = min{∞, 1+1} = 2.

Шаг 2. Вычисляем min по всем временным меткам.

min {L(x₂), L(x₄), L(x₅), L(x₆), L(x₇), L(x₈)}= min {2, 6,2, 9, ∞, ∞} =2.

В качестве постоянной можно взять любую из меток L(x₂) и L(x₅), которые совпадают и равны вычисленному минимуму. Пусть постоянную метку получит, например, вершина x₂, т.е.

L^*(x₂)=2.

Третья итерация

Шаг 1. Г(x₂) = {x₁, x₄, x₅}. Вершины x₄ и x₅ имеют временные метки. Обновляем метки.

L(x₄) = min {6, 3+2}= 5,

L(x₅) = min {2, 5+2} = 2.

Шаг 2. min {L(x₄), L(x₅), L(x₆), L(x₇), L(x₈)}= min {5,2, 9, ∞, ∞} =2.

Наименьшую метку имеет вершина x₅. Эта метка становится постоянной, т.е.

L^*(x₅) = 2.

Четвертая итерация

Шаг 1. Г(x₅) = {x₂, x₃, x₄, x₇}. Временные метки имеют вершины x₄ и x₇. Обновляем их.

L(x₄) = min {5, 2+2} = 4,

L(x₇) = min {∞, 3+2} = 5.

Шаг 2. min {L(x₄), L(x₆), L(x₇), L(x₈)} = min {4, 9, 5,∞} = 4.

Величина x₄ получает постоянную метку L^*(x₄) = 4.

Пятая итерация

Шаг 1. Г(x₄) = {x₁, x₂, x₅, x₆}. Временную метку имеет только вершина x₆ .

Ее новая метка

L(x₆) = min {9, 2+4} = 6.

Шаг 2. min {L(x₆), L(x₇), L(x₈)} = min{6, 5,∞} = 5.

Полагаем L^*(x₇) = 5.

Шестая итерация

Шаг 1. Г(x₇) = {x₅, x₆, x₈}. Временные метки - у вершин x₆ и x₈. Имеем

L(x₆) = min {6, 2+5} = 6,

L(x₈) = min {∞, 1+5} = 6.

Шаг 2. min {L(x₆), L(x₈)}= min {6, 6} = 6.

Любую из меток L(x₆), L(x₈) можно сделать постоянной. Пусть L^*(x₆) =6.

Седьмая итерация

Шаг 1. Г(x₆) = {x₁, x₄, x₇, x₈}. Единственная вершина из Г(x₆) с временной меткой - это x₈ .

L(x₈) = min {6, 2+6} = 6.

Шаг 2. min {L(x₈)} = min {6} = 6. Вершина x₈ получает постоянную метку L^*(x₈) = 6.

Процесс расстановки меток закончен. Значение постоянной метки вершины x₈ дает кратчайшее расстояние между x₁ и x₈, которое равно 6.

2)Для нахождения кратчайшего пути между x₁ и x₈ воспользуемся табл. 1.3. Вершина x₈ получила постоянную метку на шестой итерации. Значит, ей предшествует вершина x₇. Постоянная метка вершины x₇ находится в столбце под номером 4. Значит, ей предшествует вершина x₅. И так далее.

Таким образом, кратчайший путь из x₁ в x₈ S= {x₁, x₃, x₅, x₇, x₈}.

Построим основное дерево кратчайших путей для данного графа. Говоря другими словами, следует найти связный подграф исходного графа, который не содержал бы циклов, и в котором длина пути от вершины x₁ (корня дерева) до каждой из вершин графа была бы наименьшей по сравнению с любым другим путем из x₁ до рассматриваемой вершины. Для этого используем строку табл. 3, содержащую последовательность вершин {x₁ x₃ x₂ x₅ x₄ x₇ x₆}. Каждую вершину из этой последовательности, начиная с первой, нужно соединить ребром с вершинами, отмеченными в соответствующем столбце символом “*”. Так, в столбце под x₁ помеченными являются вершины x₃ и x₅. Значит, соединяем ребрами x₁ с этими вершинами. Следующая ветвь дерева строится уже от вершины x₃ до вершины x₅. Согласно последовательности, строить дерево продолжаем от вершины x₅. От нее должны идти ребра к вершинам x₄ и x₇ (см. столбец, соответствующий 4-й итерации). На 5-й итерации соединяем ребром вершины x₄ и x₆. На 6-й итерации проводим ребро от вершины x₇ до x₈. Последнюю вершину x₆ не с чем соединять, так как в последнем столбце нет помеченных вершин. Таким образом, процесс построения дерева завершен.

Соответствующий построенному дереву кратчайших путей граф представлен на рис. 3

Рис. 3

Заметим, что сравнение рис. 2 и 3 подтверждает известную теорему о графах: наименьшее число ребер p, которое нужно удалить из связного графа, чтобы получить дерево, удовлетворяет соотношению

p= N - n + 1,

где N - число ребер исходного графа,

n - число вершин графа.

В нашем случае p = 13 - 8 + 1 = 6, т.е. количество удаляемых ребер графа для получения дерева не может быть меньше шести. Непосредственный подсчет показывает, что в рассматриваемой задаче оно равно шести.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ И ОФОРМЛЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

При выполнении контрольной работы необходимо строго придерживаться указанных ниже правил. Работы, выполненные без соблюдения этих правил не засчитываются и возвращаются студенту для переработки.

Контрольная работа должна быть выполнена в отдельной тетради в клетку чернилами любого цвета, кроме красного. Необходимо оставлять поля шириной 4-5 см для замечаний рецензента.
В заголовке работы на обложке тетради должны быть ясно написаны фамилия студента, его инициалы, учебный номер (шифр), название дисциплины. Здесь же следует указать название учебного заведения, дату отсылки в университет и адрес. В конце работы следует выставить дату её выполения и подпись.
Контрольная работа должна содержать все пункты предлагаемого расчета строго по положенному варианту. Контрольная работа не своего варианта не засчитывается.
Перед самим расчетом надо полностью выписать свои данные и условия к выполняемой работе.
Весь расчет следует излагать подробно и аккуратно, объясняя и мотивируя свои действия по ходу решения, делая необходимые рисунки.
После получения прорецензированной незачтенной работы, студент должен исправить все отмеченные рецензентом ошибки и недочеты и выполнить все рекомендации рецензента.
Если рецензент предлагает внести в решение те или иные исправления или дополнения и прислать их для повторной проверки, то это следует сделать в короткий срок.
В случае незачета работы и отсутствия прямого указания рецензента на то, что студент может ограничиться представлением исправленных решений, вся работа должна быть заново исполнена.
При высылаемых исправлениях должна обязательно находиться прорецензированная работа и рецензия на неё. Поэтому рекомендуется при выполнении контрольной работы оставлять в конце тетради несколько чистых листов для всех дополнений и исправлений в соответствии с указанием рецензента. Вносить исправления в сам текст после её рецензирования запрещается.

ПРИМЕР ВЫПОЛНЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ

Транспортные сети. Построение максимального потока

Основные определения

Двухполюсной транспортной сетью S называется произвольный орграф без петель с множеством вершин X и с множеством дуг U, для которых выполняются следующие условия:

1.Существует одна и только одна вершина s ∈ X, в которую не заходит ни одной дуги. Эта вершина называется источником или входом сети.

2.Существует одна и только одна вершина t ∈ X, из которой не исходит ни одной дуги. Эта вершина называется стоком или выходом сети.

3.На множестве дуг сети U определена неотрицательная функция

С:U→R⁺ 0, ставящая в соответствие каждой дуге u  U неотрицательное число c(u), называемое пропускной способностью сети.

Потоком в сети S=(X,U) от входа к выходу (или от источника в сток) называется произвольная неотрицательная вещественная функция, определенная на множестве дуг сети :U → R⁺ 0, для которой выполняются следующие условия:

1. 0 ≤(u)≤c(u) для любой дуги;

2. ля любой вершины xX,x≠s,x≠t,

где

-множество дуг, заходящих в вершину x,

-множество дуг, выходящих из вершины x.

Это условие означает, что количество потока, входящего в каждую вершину сети (кроме вxода и выxода) равно количеству потока, выходящего из этой вершины. Следовательно, количество потока, выходящего из вxода s равно количеству потока, входящего в выxод t . Эта величина называется величиной потока и обозначается _s.

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

Поток не может исчезать и накапливаться в промежуточных вершинах сети, поэтому модель будет соответствовать ситуации с отсутствием брака и незавершенного производства. Пропускная способность дуг сети в этом случае должна учитывать способность транспортной системы и производительность станков.

Интересна задача нахождения максимального потока в сети (например, максимальное число деталей, которое может обработать в единицу времени производственная система).

Разрезом сети S=(X,U), заданным на множестве вершин AX, A≠0, A≠X, sA, tX\A называется множество дуг (x_i,x_j)  U таких, что x_i A, x_jX\A. Разрез обозначается P(A).

Иными словами, разрезом сети является множество дуг сети, обладающих следующим свойством: любой путь от входа к выходу сети пройдет хотя бы по одной дуге разреза. При удалении разреза вход сети отделяется от выхода, т.е. сеть как бы разрезается.

Пропускной способностью разреза или величиной разреза C(A) называется сумма пропускных способностей входящих в него дуг: C(A) =

Минимальным разрезом, разделяющим вход s и выход t сети, называется произвольный разрез P(A), sA, tX\A с минимальной пропускной способностью.

Теорема Форда-Фалкерсона

Величина каждого потока от вxода к выxоду не превосходит пропускной способности минимального разреза, разделяющего вxод и выxод сети, причем существует максимальный поток, чья величина равна пропускной способности минимального разреза.

Дуга uU, соединяющая вершины x_iX, x_jX сети S, является допустимой, если для нее выполняется одно из следующих условий:

Направление дуги совпадает с направлением потока и значение потока по этой дуге меньше ее пропускной способности: u = (x_i,x_j), (u) < c (u).
Направление дуги противоположно направлению потока и по ней проходит ненулевой поток: u = (x_i,x_j), (u) > 0.

Дуги, для которых выполняется условие 1), называются увеличивающими или согласованными. Дуги, для которых выполняется условие 2), называются уменьшающими или несогласованными.

Увеличивающей цепью, соединяющей вход и выход сети, называется
простая цепь, все дуги которой являются допустимыми. Знание увеличивающей цепи позволяет увеличить поток по ней на величину  = min _u{(u)}, где  (u) = с(u)-(u), если u -увеличивающая.  (u) = (u),если u - уменьшающая.

Алгоритм построения максимального потока

Шаг1. Задать начальное значение потока, если оно не задано. Удобно задавать начальное значение потока равным 0. Перейти к шагу 2.

Шаг2. Построить увеличивающую цепь от входа к выходу сети. Если увеличивающей цепи не существует, то максимальный поток построен. В противном случае перейти к шагу 3.

Шаг3. Вдоль построенной цепи увеличить значение потока на величину 8. Перейти к шагу 2.

Замечание. Для того, чтобы алгоритм Форда-Фалкерсона сходился за конечное число шагов для произвольных значений пропускных способностей, нужно в качестве увеличивающей цепи выбирать цепь, содержащую минимально возможное число дуг.

Пример. Пусть дана матрица пропускных способностей некоторой транспортной сети (табл. 4). Построим сеть, соответствующую этой матрице (рис.4). Учтем, что веса, равные нулю, означают отсутствие ребра между соответствующими вершинами, а ненулевое значение, стоящее на пересечении k-й строки и l-го столбца означает, что из вершины x_k идет дуга в вершину x₁. Буквами s и t обозначены вершины, соответствующие истоку и стоку. Над каждой дугой проставлена ее пропускная способность и начальное значение потока (в скобках).

Таблица 4

	x₁	х₂	х₃	х₄	t
s	7	0	4	0	0
x₁	0	3	0	5	0
х₂	0	0	2	0	5
х₃	0	0	0	4	0
х₄	0	0	0	0	6

Blog

Программа, методические указания и контрольные задания Для студентов-заочников Казань, 2009 г

Содержание