Файл: Лабораторные работы по ДМ.doc

18.

	X1	X2	X3	X4	X5	X6
X1	∞	31	15	19	8	55
X2	19	∞	22	31	7	35
X3	25	43	∞	53	57	16
X4	5	50	49	∞	39	9
X5	24	24	33	5	∞	14
X6	34	26	6	3	36	∞

19.

	X1	X2	X3	X4	X5	X6
X1	∞	39	45	2	51	33
X2	30	∞	20	33	40	35
X3	54	16	∞	55	22	56
X4	19	36	25	∞	18	43
X5	29	8	8	12	∞	25
X6	16	47	31	14	8	∞

20.

	X1	X2	X3	X4	X5	X6
X1	∞	41	27	54	46	5
X2	42	∞	11	32	58	21
X3	36	5	∞	33	22	33
X4	46	24	59	∞	49	59
X5	48	58	11	44	∞	47
X6	26	50	35	19	27	∞

21.

	X1	X2	X3	X4	X5	X6
X1	∞	41	27	54	46	5
X2	42	∞	11	32	58	21
X3	36	5	∞	33	22	33
X4	46	24	59	∞	49	59
X5	48	58	11	44	∞	47
X6	26	50	35	19	27	∞

22.

	X1	X2	X3	X4	X5	X6
X1	∞	21	40	28	60	52
X2	58	∞	11	39	22	56
X3	22	12	∞	23	14	19
X4	25	47	51	∞	20	54
X5	47	43	18	42	∞	52
X6	44	49	50	52	29	∞

23.

	X1	X2	X3	X4	X5	X6
X1	∞	6	56	35	48	29
X2	34	∞	46	46	55	26
X3	29	31	∞	32	13	42
X4	26	34	12	∞	17	7
X5	38	35	40	13	∞	47
X6	60	25	59	36	31	∞

24.

	X1	X2	X3	X4	X5	X6
X1	∞	22	26	56	38	60
X2	34	∞	12	51	37	27
X3	45	33	∞	44	47	37
X4	39	7	16	∞	57	8
X5	35	56	40	58	∞	27
X6	9	20	36	31	18	∞

25.

	X1	X2	X3	X4	X5	X6
X1	∞	4	39	22	10	47
X2	58	∞	56	18	4	35
X3	34	29	∞	17	57	18
X4	52	4	22	∞	15	37
X5	41	44	25	11	∞	32
X6	11	6	19	2	58	∞

26.

	X1	X2	X3	X4	X5	X6
X1	∞	14	40	33	16	51
X2	48	∞	34	4	11	24
X3	57	35	∞	24	38	52
X4	30	50	44	∞	9	31
X5	18	42	24	31	∞	30
X6	1	38	31	19	32	∞

27.

	X1	X2	X3	X4	X5	X6
X1	∞	56	48	39	3	40
X2	47	∞	50	4	10	49
X3	48	50	∞	42	19	16
X4	24	44	47	∞	23	33
X5	38	17	6	51	∞	26
X6	29	59	55	34	18	∞

28.

	X1	X2	X3	X4	X5	X6
X1	∞	41	60	39	46	10
X2	31	∞	59	16	1	51
X3	29	51	∞	14	42	50
X4	35	12	52	∞	16	26
X5	16	39	15	60	∞	57
X6	15	30	38	47	36	∞

Для проверки решения использовать программу Grin

Контрольные вопросы

Лабораторная работа № 9 Определение максимального течение в транспортной сети

Цель работы:

Теоретические сведения

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

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

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

Поток в сети называется стационарным, если существуют две вершины и число такие, что выполнены следующие условия:

В этой ситуации число называется величиной потока , вершина называется источни-

ком, а вершина - стоком потока .

Известна следующая классическая задача о максимальном потоке: в данной сети для данного источника и для данного стока найти стационарный поток максимально возможной величины. Можно доказать, что такая задача всегда имеет решение. Один из способов ее ре- шения называется алгоритмом Форда-Фалкерсона. Сформулируем этот алгоритм по шагам.

Шаг 0. Фиксируем на данной сети с источником и стоком произвольный стационарный поток , например - поток, тождественно равный нулю (т.е. равный нулю на каждом ребре данного орграфа ). Нетрудно проверить, что такой поток действитель-но стационарный и имеет величину 0.

Шаг 1. Около вершины поставим пометку следующего вида:

.

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

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

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

Шаг 2. Пусть - некоторое ребро, начало которого, т.е. вершина , уже имеет некоторую пометку (или, если - это источник , то пометку , где ). Если , т.е. поток равен на ребере пропускной способности , то пометка у вершины не проставляется. Если же , то пометка у вершины выставляется следующим образом.

На первом месте в пометке будет стоять символ , т.е. пометка будет такой: , где число еще нужно найти. Положим

.

Пусть теперь такое ребро, у которого пометку имеет конец, т.е. вершина имеет пометку . Если , то пометку у вершины не выставляют; если же , то вершина получает пометку , где

.

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

Если же вершина оказалась помеченной, то переходим к следующему шагу. Отметим принципиальную подробность: если вершина оказалась помеченной, то число, фигурирующее в пометке, обязательно положительно.

Шаг 3. Пусть вершина имеет пометку . Мы изменим сейчас поток на не-скольких ребрах данного графа, в результате чего получится новый стационарный поток из источника в сток , величина которого будет на (это число указано в пометке стока ) больше величины потока .

Если вершина имеет пометку , то на ребре изменим поток , прибавив к его значению на этом ребре число . Если вершина имеет пометку , то на ребре изменим поток , вычитая из его значения на этом ребре число .

Затем перейдем к вершине и проделаем то же, что только что делалось относительно вершины ; при этом прибавлять или вычитать будем прежнее число . Продолжая так, в соответствии с пометками, отбирать ребра графа и менять на них значение потока (на каждом отбираемом ребре - на одно и то же число !), мы придем к источнику . Это будет означать завершение изменения потока. Можно доказать, что полученный в результате поток является стационарным и его величина на больше величины исходного потока .

Затем нужно повторить все сначала с уже новым базовым стационарным потоком.

Определить максимальный поток в сети для заданного графа.

Задания

Контрольные вопросы