Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Главные разрезы и части ствола
  2. Графическое изображение геологических тел. Карты и разрезы
  3. Разрезы
  4. ТЕМА 3.2 Изображения - виды, разрезы, сечения

Лекция № 16

 

СЕТИ

 

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

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

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

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

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

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

 

 

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

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

Рассмотрим граф 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; просмотров: 139 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Международное движение капитала.| Диагностика хронического панкреатита

mybiblioteka.su - 2015-2021 год. (0.007 сек.)