Сделай Сам Свою Работу на 5

Два определения связанности вершин графа и их эквивалентность. Разбиение графа на компоненты связанности.





4. На вершинах графаG(V,X) реализуется числовая функция, если каждой вершине vi ставится в соответствие некоторое число xi= φ(vi) из некоторого множества L.

Значением маршрута через вершины vi1, vi2,…,vim.называется число λ(vi1, vi2,…,vim) = xi1*xi2*...*xim.

Минимальным (максимальным) маршрутом через вершины некоторого множества маршрутов Р называется маршрут с минимальным (максимальным) значением λ.

На ребрах графа G(V,X) реализуется числовая функция, если каждому ребру (vi,vj) сопоставлено число ρij = ρ{(vi,vj)} = ρ(vi,vj) из некоторого множества М. Причем ρij = ρji.

Значением маршрута через ребра, соединяющие вершины vi1, vi2,…,vim.называется число λ(vi1, vi2,…,vim) = ρi1i2*ρi2i3*...*ρim-1im.

Минимальным (максимальным) маршрутом через ребра некоторого множества маршрутов Р называется маршрут с минимальным (максимальным) значением λ.

Пример нахождения максимального пути. Пусть в задаче ка­лендарного планирования возникла необходимость определения максимального пути из вершины а1 в вершину а7 для графа, представленного на рис. 4.13а.

 

G(V,X) – связный граф. На множестве V задана числовая функция φ(v), v ? V.



Для каждой вершины задается некоторое число, называемое меткой вершины.

Алгоритм А на графе G(V,X) задается:

1) начальной функцией G(V,X) φ0(v)=(φ0(v1), φ0(v2), …, φ0(vn))

2) правилом А, ставящим в соответствие каждой функции φ из Φ одну и только одну функцию ψ из Φ, т.е. А: Φ→Φ (однозначное отображение множества в себя) и ψ = А(φ). Работа алгоритма: φk = A(φk-1), k=1,2,...

3) иногда задается правило остановки алгоритма, т.е. указывается момент, в который работа алгоритма прекращается.

 

5. Лемма о предшественнице. Если для любой вершины b≠a существует хотя бы одна вершина с: λ(b) = λ(c) + ρ(b,c) или λ(b) - λ(c) = ρ(b,c), то с – предшественница b.

Срезка функции вдоль ребра графа.

Задача о кратчайшем маршруте. Алгоритм Форда для отыскания кратчайшего маршрута.

Каждому ребру (vi,vj) ставится в соответствие некоторое действительное число ρji = ρ{(vj,vi)} = ρ(vj,vi) > 0.

Длиной маршрута {(vi1,vi2), (vi2,vi3), ... , (vim-1,vim)} назовем сумму длин всех ребер Lμ= ρ(vi1,vi2) + ρ(vi2,vi3) + ... + ρ(vim-1,vim).

Для каждой вершины v из V нужно найти кратчайший маршрут из a в v.



Рассмотрим ребро {b,c} из Х: φ(b) ≥ φ(c).

Ребро {b,c} – плохое по отношению к φ, если φ(b) > φ(c) + ρ(b,c), хорошее – в противном случае.

Срезкой функции φ по плохому ребру {b,c} назовем функцию ψ, которая определяется (*):

ψ(v) = φ(c) + ρ(b,c), v=b

ψ(v) = φ(v), v≠b

Для вершины b делаем замену (*). Первую строчку в соотношении (*) можно переписать: ψ(b) = φ(c) + ρ(b,c), φ(b) > ψ(b), φ(v) ≥ ψ(b) – в общем случае для остальных вершин ребро {b,c} стало хорошим по отношению к ψ.

Алгоритм Форда нахождения кратчайшего маршрута:

1) Перенумеруем все ребра в графе G(V,X) в произвольном порядке, а на вершинах графа зададим начальную функцию:

φ0(v)= 0, v=a

φ0(v)= +∞, v≠a

2) Правило А. Пусть на некотором этапе работы алгоритма мы получили функцию: φ(v)=(φ(v1), φ(v2), …, φ(vn)). Находим плохое ребро с минимальным номером относительно функции φ и производим срезку функции φ по этому плохому ребру. Из остальных плохих ребер берем с минимальным номером. По начальной функции φ0(v) и правилу А строим последовательность функций: φk = A(φk-1).

3) Правило остановки: процесс останавливается когда не остается плохих ребер.

Последнюю новую функцию обозначим λ(v).

λ(λ(v1), λ(v2),…, λ(vn)) = λ(v) называются финальными метками вершин.

 

Орграфы

Ориентированный граф (орграф) G — это упорядоченная пара G=(V,A), для которой выполнены следующие условия:

· V — это непустое множество вершин или узлов,

· A — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.



Дуга — это упорядоченная пара вершин , где вершину называют началом, а — концом дуги. Можно сказать, что дуга ведёт от вершины к вершине .

 

G=(V,X) - орграф

V={v1, v2,...,vn}≠ø

Х={(vi,vj): vi, vj ? V} – множество упорядоченных пар

Граф G(V,X), полученный из графа G=(V,X) удалением стрелок на дугах, называется основанием орграфа G.

Согласованность состоит в том, что если вершины a1, b1 ? V1, a2, b2 ? V2 и a2= φ(а1), b2= φ(b1), то образом дуги (a1,b1) является дуга (a2,b2). ψ((a1,b1))= (a2,b2)= (φ(а1), φ(b1)).

Число кратных ребер должно быть одинаково.

Ориентированный маршрут – последовательность дуг {(vi1,vi2), (vi2,vi3), ... , (vim-1,vim)}, vi1→ vi2→…→ vim-1→ vim. Аналогично графам определяется орцепи, простые орцепи, орциклы.

Орграф G связен (слабосвязен), если связным является его основание, т.е. граф G.

Орграф G сильносвязен, если для любых вершин u и v существует простая орцепь из вершины u в вершину v.

Граф G(V,X) называется ориентируемым, если каждое его ребро, рассматриваемое как пара вершин, может быть упорядоченно.

8. Транспортная сеть — ориентированный граф G=(V,X), в котором каждое ребро (u,v)ϵE имеет неотрицательную пропускную способность c(u,v)≥0 и поток f(u,v). Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из в . Транспортная сеть может быть использована для моделирования, например, дорожного трафика.

Целочисленная транспортная сеть — транспортная сеть, все пропускные способности ребер которой — целые числа.

Разрез (s-t cut) — разбиение множества всех вершин V на два подмножества, A и B, таких что , .

Пропускная способность разреза (A,B) (the capacity of an s-t cut (A,B) ) — сумма пропускных способностей всех рёбер из A в B .

Поток через разрез (A,B) — сумма всех потоков из A в B . Он не превышает пропускную способность разреза, поскольку .

Минимальный разрез - разрез с минимальной пропускной способностью.

Остаточная пропускная способность (residual capacity) ребра Она всегда неотрицательна из-за условия на ограничение пропускной способности.

Максимальный поток положителен тогда и только тогда, когда существует путь из источника в сток, проходящий по рёбрам с положительной пропускной способностью.
Доказательство: Пускай такой путь P существует. Пусть c - минимальная из пропускных способностей рёбер, принадлежащих P. Пускай поток равен c на всех рёбрах из P, и нулю на всех остальных рёбрах. Тогда суммарный поток из источника равен c, то есть положителен. Теперь допустим, что такого пути нет, то есть t недостижимо из s по рёбрам с положительной пропускной способностью. Пусть A - множество вершин, достижимых из s по таким рёбрам, B - недостижимых. Тогда, поскольку , , то (A,B) является разрезом. Кроме того, не существует ребра (a,b) с положительной пропускной способностью, такого что , , иначе b было бы достижимо из s. Следовательно, пропускная способность разреза (A,B) равна нулю, а значит и поток через него всегда равен нулю. Следовательно, сумма потоков из источника всегда равна нулю.

Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети. Доказательство: пускай такой путь P есть. Пусть c - минимальная из пропускных способностей рёбер, принадлежащих P, в остаточной сети. Для всех пар увеличим f(u,v) на c и уменьшим f(v,u) на c. Мы увеличили суммарный поток из источника на s, следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток f в исходной сети обеспечивает максимальный суммарный поток из s. Пусть это не так, тогда есть поток f', обеспечивающий больший суммарный поток из s. Легко убедиться, что f'-f - поток в остаточной сети, обеспечивающий в ней положительный суммарный поток из s. Следовательно, в остаточной сети есть путь из источника в сток, то есть увеличивающий путь. Мы получили противоречие.

 

9.Функция j (x), определенная на множестве X дуг транспортной сети D, и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если:

1) для любой дуги x О X величина j(x), называемая потоком по дуге х, удовлетворяет условию 0 j(x) c(x);

2) для любой промежуточной вершины v выполняется равенство

т.е. сумма потоков по дугам, заходящими в v, равна сумме потоков по дугам, исходящими из v.

Величиной потока j в транспортной сети D называется величина j, равная сумме потоков по всем дугам, заходящим в vn, или, что то же самое, величина, равная сумме потоков по всем дугам, исходящим из v1, т.е.

Пусть j - допустимый поток в транспортной сети D.

Дуга x О X называется насыщенной, если поток по ней равен ее пропускной способности, т.е. если j(x) = c(x). Поток j называется полным, если любой путь в D из v1 в vn содержит, по крайней мере, одну насыщенную дугу.

Определение. Поток j называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.

Очевидно, что максимальный поток j обязательно является полным. Обратное неверно. Существуют полные потоки, не являющиеся максимальными. Тем не менее, полный поток можно рассматривать как некоторое приближение к максимальному потоку.

 

10. Теорема Форда—Фалкерсо́на — теорема о максимальном потоке в графе.

Звучит так: величина максимального потока равна величине минимального разреза.

Достаточность: любой поток между вершинами t и s меньше или равен величине любого сечения. Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин «грузов», перевозимых по всем возможным путям из вершины t в s. Каждый такой путь обязан иметь общее ребро с данным сечением. Так как по каждому ребру сечения суммарно нельзя перевести «груза» больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна сумме всех пропускных способностей рёбер данного сечения. Утверждение доказано.

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

Лемма 1 о пополнении потока. Пусть задан орграф G(V,X), транспортная сеть S=(G,Q), источник - α и сток – β (единственные). Пусть φ - поток транспортной сети S с величиной π(φ), μαβ: α→vi1→vi2→...→vim=β – простая орцепь, соединяющая α с β. Если все дуги этой простой цепи ненасыщенные, то поток φ можно пополнить (по этой цепи).

Лемма 2 о пополнении потока. Пусть задан орграф G(V,X), транспортная сеть S=(G,Q), источник - α и сток – β (единственные). Пусть φ - поток транспортной сети S с величиной π(φ), μαβ: α→vi1→vi2→...→vim= β - простая цепь в графе G(V,X), который является основанием орграфа G(V,X), но не является простой орцепью в орграфе G. Если любому ребру этой цепи {vik,vik+1} соответствует ненасыщенная дуга (vik,vik+1) орграфа G или дуга (vik+1,vik) с ненулевым потоком, то поток φ можно пополнить.

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.