Разрезы. Практическое применение графов

Лекция № 16

СЕТИ

Практическое применение графов

При решении следующих задач графы нашли широкое применение.

1. Задача анализа потоков.

Одной из таких задач является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой конечной вершине t (стоку). Каждой дуге (x_i, х_j) графа G приписана пропускная способность q_ij. Пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге.

Такие задачи возникают в таких приложениях, как при определении максимальной интенсивности транспортного поток между двумя пунктами на карте магистралей, представляемой графом. При решении данной задачи можно получить ответ и на «узкое место» в отношении потока между двумя указанными концевыми пунктами. Эту методику можно использовать и при анализе автотранспорта и при транспортировке газа, нефти и нефтепродуктов и другие.

Аналогичная задача возникает при проведении, какого либо технологического процесса при заданном количестве техники с заданными техническими показателями, например, строительство.

Расширим область применения графа и на его основе введем понятие сеть.

Сеть – это граф (орграф) с рассматриваемой на нем функцией, приписываемой каждому ребру некоторое действительное число.

Рассмотрим граф G = <V,E> у которого есть такие вершины, у которых полустепени исхода и захода равны нулю. Вершина полустепень захода, которой равна нулю, т.е. d⁺(v) = 0, называется источником, такие вершины будем обозначать s. Вершина, у которой полустепень исхода равна нулю, т.е. d^-(v) = 0, то такая вершина называется стоком и будем обозначат t.

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

Потоки в сетях

Сеть – это пара S = <G,c>, где G = <V,E> - произвольный ориентированный граф, а c: E → R – функция, которая каждой дуге <u,v> ставит в соответствие неотрицательное вещественное число c(u,v), называемое пропускной способностью этой дуги, таким образом сеть это совокупность S = <V,E,c>, где V – множество вершин или полюсов сети, E - множество ребер (дуг) сети и c – пропускная способность ребра сети.

Поток

Пусть S = <V,E,c> - сеть с s источником и t стоком. Каждой дуге сети (u,v) соответствует своя пропускная способность c(u,v): E → R⁺. Матрица пропускной способности С представляет сеть и, если С[u,v] = 0, т.е дуга (u,v) имеет нулевую пропускную способность.

Пусть задана функция f: E → R⁺.

Дивергенцией функции f в узле v называется число div(f,v), которое определяется по формуле

Функция f: E → R⁺ называется потоком в сети S = <V,E,c>, если:

1. 0 ≤ f(u,v) ≤ c(u,v), т.е. поток через дугу неотрицателен и не превосходит пропускной способности дуги;

2. div(f,u)= 0, т.е. дивергенция потока равна нулю во всех узлах, кроме источника и стока.

Число называется величиной потока f. Если f(u,v) = c(u,v), то дуга (u,v) называется насыщенной (по Новикову Ф.А.).

Разрезы

Обозначим (s,t) -разрез через P, при чем . Любой разрез определяется разбиением множества вершин V на два подмножества S и T, так что & & & & & , а в P попадают все дуги, соединяющие S и T.

Разрез будет равен , где P⁺ - дуги от S к T, а где P^- - дуги от T к S. Сумма потоков через дуги разреза P обозначим через F(P). Сумма пропускных способностей дуг разреза P называется пропускной способностью разреза и обозначим через C(P).

Дата добавления: 2015-07-07