Добавил:

guap4736_vkclub152685050 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Национальный минерально-сырьевой университет «Горный»

Предмет:

Дискретная математика

Файл:

Дискретная математика

.pdf

Скачиваний:

Добавлен:

11.08.2019

Размер:

1.66 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 1011 / 1111

vk.com/club152685050 | vk.com/id446425943

x1	x2	x4	x3	x6	( min ) 12( 66 )
	2	5	2	3

Замечание.

1) Если требуется найти минимальный путь из xk в xm , то вершины надо перенумеровать так, чтобы x1 := xk , xn xm

2) Если в ненагруженном орграфе надо найти путь, содержащий наименьшее количество дуг, то каждой дуге присваивается длина ( i ) 1.

§ 13. Потоки в транспортных сетях


Пусть дан орграф		G =<M, Г		>, x M –некоторая вершина графа.

Обозначим Г 1 (x) - множество дуг графа G , заходящих в вершину x,
Г(х) – множество дуг, выходящих из вершины х

	x	2
	1
				x
1				x
	3				4
					4
x0		x2

6	x3		9
	x3


			Г 1 (x0 ) {Ø}, Г (х0 ) {				1 ,	4 , 6 } ,
			Г 1
			Г 1	(x4 ) {	2 , 9 }, Г (x4 ) {Ø} ,

				Г Г 1 (х) Г (х)
				х М		x M

Опр.	Пусть с ( ) - целочисленная, неотрицательная функция, заданная на

множестве	Г ;	число	с ( i ) ,	поставленное		в	соответствие дуге		(	i ) Г
называется пропускной способностью этой дуги.
Опр.	Вершина x0 M , в которую не заходит ни одна из дуг, называется
источником, Г		1 ( x )={	Ø }) вершина z M, из			которой не входит ни одна дуга,
		0

называется стоком, Г(z)={ Ø }

101

vk.com/club152685050 | vk.com/id446425943

Опр. Транспортной сетью называется совокупность связного орграфа


G	=<M, Г	> и заданной на множестве		Г	функции пропускной способности дуг с

( ) , при этом в графе			G .

1)отсутствуют петли;

2)существует единственная вершина – источник

3)существует единственная вершина – сток.

Пример.

(6)	(3)	x2
(6)
x0	(4) (3)	(4)
(4)	(10)	z
		z

x3	(5)

Рис.1

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

Опр. Целочисленная неотрицательная функция ( ) , заданная на

множестве дуг транспортной сети G , называется допустимым потоком, если:

1.0 ( ) C( ), Г (величина потока по дуге не превосходит

пропускной способности этой дуги)


2. ( )	( ),	x x0 , x z , т.е. для промежуточных вершин сети	G

Г 1 ( x)	Г ( х)

сумма потоков по заходящим в вершину х дугам равна сумме потоков по выходящим из х дугам; («сколько втекает, столько и вытекает»)

Замечание. На диаграмме сети G пропускная способность обозначается числом в круглых скобках, а поток по дуге - числом перед скобками.

Механическая интерпретация транспортной сети

На практике можно представить, что дуги - трубы, по которым течет в одном направлении несжимаемая жидкость; при этом 1) количество жидкости, протекающей по трубе в единицу времени, не превосходит пропускной

102

( ) c( )

vk.com/club152685050 | vk.com/id446425943

способности трубы; 2) сколько жидкости поступает в сеть, столько из нее и

вытекает.
вытекает.	( )
Г ( x )	Г 1 ( z )
0
Опр. Величиной допустимого потока в сети							называется число
Опр. Величиной допустимого потока в сети						G	называется число

	\| \|=	( )				( )
		Г 1 ( z )		Г ( x0 )
Пример допустимого потока в сети
Пример допустимого потока в сети			G
		x1	1(3)			x2
	2(6)					2(4)
		1(4)		1(3)		2(4)
	x0	1(4)		1(3)			Z
	x0			5(10)			Z
				5(10)
	4(4)			4(5)
		x3
		Рис.2
		( ) 4 1
	\| \|=11,	Г 1 ( x3 )			-для		x3
	\| \|=11,	( ) 4 1			-для		x3

Г ( x3 )

Опр. Дуга называется насыщенной, если поток по этой дуге равен его пропускной способности:

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

Допустимый поток в примере выше не является полным.

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

1. По всем дугам запускается 0-поток ( ) =0, Г , полученный

граф обозначается G1 .

2.Выбирается некоторый путь из x0 в z:

3.По каждой дуге пути увеличивается поток на 1 до тех пор, пока какая-либо дуга не станет насыщенной.

4. В графе G1 удаляются все насыщенные дуги. Новый граф снова

обозначается G1

103

vk.com/club152685050 | vk.com/id446425943

5.	Если в графе		не существует пути из			x0 в z, то построенный
5.	Если в графе	G1	не существует пути из			x0 в z, то построенный
поток является полным, в противном случае перейти к п.2.
Пример полного потока
			x 3(3)	x	2
			1		2
		1+1+3(6)
				10(10)		Z
		x0
			4(4)		1+4(5)
			x3
			Рис.3

	Путь		Увеличение потока			Насыщенные дуги

	(x0 , z)		10			(x0 , z)

	(x0 , x1 , x2 , z)		3			(x1 , x2 )

	(x0 , x3 , z)		4			(x0 , x3 )

	(x0 , x1 , x3 , z)		1			( x3 , z )

	(x0 , x1 , x3 , x2 , z)		1			( x2 , z )

| | 5 10 4 19

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

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

§ 14. Потоки наибольшей величины Лемма (свойства потока наибольшей величины).

Поток наибольшей величины является полным потоком.

104

vk.com/club152685050 | vk.com/id446425943

Замечание: Обратное неверное так как в транспортных сетях может существовать несколько полных потоков различной величины.

Алгоритм Форда-Фалкерсона (построение потока наибольшей величины).


Пусть дана транспортная сеть	G =<M, Г		>, на множестве дуг	Г	задана

функция пропускной способности дуг.

1.Построим какой либо полный поток ( )

2.Выделим множество вершин M* M и присвоим знаки соединяющим их дугам по следующим правилам:

а) x0 M *
б) Пусть вершина x M * , вершина y cмежна с	x и y M *

- если существует исходящая ненасыщенная дуга (x,y) (имеет начало в х), то вершину y включаем в множество M * , а дуге (x,y) присваиваем знак “+”

- если существуетвходящая дуга (y,x) Г (x- конец дуги) и поток по этой дуге ( ) >0, то у включаем в M * , а дуге (y,x) присваиваем знак “-“ .

Повторяем

до тех пор,

пока не прекратиться выделение новых

вершин в M * .

Если в результате этого

процесса

сток z M * , то построенный

поток является потоком наибольшей величины.

Если z M * , то в M * можно выделить цепь

x0 z (не путь).

Построим новый поток

(

цепи

" ( ) ( ) 1,

цепи и обозначена знаком

( ) 1,

3.Обозначим вновь построенный поток ( ), и вернемся на шаг 2)

Замечание.

При построение каждого нового потока ' ( ) его величина увеличивается

на 1.

Последняя дуга цепи всегда имеет знак “+” т.к. z-конец цепи.

Пример: Построить поток наибольшей величины

105

vk.com/club152685050 | vk.com/id446425943

	x1		3(6)+1	x4
	7(7)			1+5(9)
			2(2)	1+5(9)
			2(2)
x0	1(2)-1			Z
				Z
			3(3)	5(7)
	3(8)+1			5(7)
	3(8)+1		2(2)
		x	2(2)	x3
		x	2	x3
			2

I.Убедимся, что данный поток является полным.

II.Построим поток наибольшей величины.

1) x0 M *

	(x	0	, x ) насыщенная x , не включается в М *
2)				1					1
							) ; x		M *
	(x	0	, x		2			2

	(x2 , x4 )
3)	(x2 , x3 )								насыщенная.
	(x , x			2		)" ", x M *
	1							1

4)(x1, x4 )" " x4 M *

5)(x4 , z) , z M *

Существует цепь {x0 x2 x1 x4 z}, к потокам идущим по дугам, обозначенным знаком “+” добавляем 1, от обозначенных знаком “-” отнимаем 1

III.Получили новый поток на 1 больше предыдущего; вернемся на шаг II

1)x0 M *

2)x0 , x2

3)нет ненасыщенных исходящих из x2 дуг и нет входящих в x2 дуг

ненулевого потока завершили построение множества M * { x0 , x2 }, т.е z M * , это означает, что построенный на предыдущем этапе поток , является потоком наибольшей величины | max | 11.

106

vk.com/club152685050 | vk.com/id446425943

§ 15. Поток, насыщающий выходные дуги.
Опр. Выходными дугами называют дуги, инцидентные стоку; величина
потока в транспортной сети:		C( )

	Г 1 ( z )	Г 1 ( z )

Лемма: (свойство потока, насыпающего выходные дуги)

Если в сети существует поток, насыщающий все выходные дуги, то он

является потоком наибольшей величины. Величина этого потока определяется
равенством					с
равенством					с
				Г 1 ( z )	Г 1 ( z )
				Г 1 ( z )	Г 1 ( z )
	Замечание. Поток, насыщающий выходные дуги, не всегда существует в
транспортной сети, например, не существует, если c( )						C( )
					r Г ( x0 )	r Г 1 ( z )
	Опр.	Пусть X – непустое множество вершин, смежных со стоком, в сети

G М , Г ,			Г (х)	- множество всех дуг, выходящих из вершин множества Х,

тогда:

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

ex(X)= c( )

r Г ( х)

2.Если в сети G М , Г , положить пропускную способность дуг,

соединяющих вершины из множества Х со стоком, равную бесконечности и

рассмотреть полученную таким образом новую сеть G , то поглощающей способностью множества Х называется число

ent(X)=max ( ) , где максимум берется по всем допустимым потокам

r Г 1 ( х)

сети G .

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

Теорема (о существовании потока, насыщающего выходные дуги)


Для того чтобы в транспортной сети G	существовал поток, насыщающий

все выходные дуги, необходимо и достаточно, чтобы потребность любого

107

vk.com/club152685050 | vk.com/id446425943

множества Х вершин, смежных со стоком, не превышала поглощающей способности множества Х: ex(Х) ent(x)

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

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

1.Дайте определение графа, орграфа, подграфа, остовного подграфа, однородного графа.

2.Какие графы называются изоморфными?

3.Сформулируйте теорему Эйлера о соотношении вершин и ребер в графе.

4.Дайте определения маршрута в графе, цепи, пути, цикла.

5.Какие графы называются полными, однородными.

6.Приведите примеры планарных графов.

7.Что такое эйлерова характеристика графа.

8.Какой граф называется эйлеровым. Приведите примеры.

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

10.Какие способы машинного представления графов Вы знаете? 11.Что такое дерево, бинарное дерево, корневое дерево.

12.Что называется основным деревом.

13.Приведите алгоритм поиска минимального остовного (опорного) дерева.

14.Сформулируйте теорему Эйлера для орграфа.

15.Приведите алгоритм поиска максимального потока.

16.Дайте механическую интерпретацию транспортной сети.

17.Сформулируйте алгоритм Форда-Фалкерсона – построения потока наибольшей величины.

18.Сформулируйте алгоритм Форда-Белмана – построение минимального пути.

108

vk.com/club152685050 | vk.com/id446425943

СПИСОК ЛИТЕРАТУРЫ

1.Горбатов В.А. Основы дискретной математики. М.: Вильямс, 2009.

2.Новиков Ф.А. Дискретная математика для программистов. – 3-е изд. – СПб.: Питер, 2012.

3.Андерсон Дж. Дискретная математика и комбинаторика. – М.: Вильямс,

2007.

4.Романовский И.В. Дискретный анализ. – СПб.: Невский диалект, 2007.

5.Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергия, 2000.

6.Смирнова Е.Л. Конспект лекций по дискретной математики. – СПб.: ВКА им. А.Ф. Можайского, 2000.

109

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 1011 / 1111

Соседние файлы в предмете Дискретная математика

#
11.08.20191.66 Mб54Дискретная математика.pdf
#
10.08.2019171.64 Кб26тест дискретка 3.pdf
#
10.08.2019158.13 Кб45Тесты по Дискретной математике 2.pdf
#
10.08.2019184.97 Кб78Тесты по Дискретной математике.pdf