Элементы теории графов. Задача о максимальном потоке.


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

Цепь: S1(2, 7)=(2, 3, 4, 5, 7)= (U3, U5, U7, U10,)

S2(2, 7)=(2, 4, 6, 7)

Замкнутая цепь называется циклом:

S3(2, 2)=(2, 3, 5, 4, 2)

Ориентированый граф:

Путь:

S1(1, 7)=(1, 3, 5, 7)=( U1 U2 U3)

S2(1, 7)=(1, 3, 5, 4, 7)

Понятие сети. Поток в сети.

Граф, элементом которого поставлены в соответствие некотор. параметры, называют сетью.

Параметры задаются на вершинах и на дугах сети или на подмножествах вершин дуг.

В зав – ти от приложений различают сети: транспортные, электрич., информационные, водопроводные и т. д. Их харак – ми явл. Пропускная способность, токи, понтенциалы, сечения, объемы поставок и потребления.

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

Каждой вершине i графа характеризуются интенсивностью di . Те вершины i для котор. di>0, называется источниками для котор. di<0 – стоками.

di=0 – нейтральные. Источник можно интериретировать как пункт производства продукции , стоки – как пункты потребления продукции, нейтралбные вершины – это т. н. перевалочные пункты, где продукция не производится и не потребляется.

Каждой дуге (i, j) сети ставится в соответствие некоторое число Cij , означает ее пропускную способность. Множество этих чисел задают т. н. функцию пропускной способности.

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

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

Будем обозначать сеть: G=(J, U)

J – множество вершин

U – множество дуг (ребер)

Рассмотрим сеть G=(J, U) с одним источником S и с одним стоком t и пусть для каждой дуги (i, j) задана проп. способность Сij>0. Тогда в сети можно задать др. функцию, которая

называется потоком в сети .

Потоком в сети будем называть функцию, которая каждой дуге (i, j) ставит в соответствие не отрицательное число xijclip_image0020 и удовлетворяет след. условиям:

Условие (1) означает, что поток по дуге неотрицателен и не может превышать ее пропускную способность

Условие (2) означает, что поток (продукция) доставляемый в кажд. нейтральн. вершине К, равен потоку (продукции), выпускающему из этой вершины.

Условие (3) говорит, что величина потока V (V едениц продукции), вытекающего из источника, равна величине, притекающей в сток.

Одной из основеых задач является задача нахождения величины максимального потока в сети:

Найти такой поток в сети {Xij}, который удовлетворял условиям (1) и (2) и доставляет максимальное значение функции (3).

Разряд в сети

Расмотрим сеть G=(J, U) с одним источником s и одним стоком t. На дугах сети заданы их пропускные способности Cij. Множество всех вершин сети J разобъем на 2 подмножества R и clip_image004, чтобы clip_image006, а clip_image008. Разрез будем обозначать clip_image010. Разрез в сети образует те дуги (i, j), для которых clip_image012 а clip_image014, clip_image016. Пропускная способность разреза равна сумме пропускная способности дуг этого разреза и обозначает:

В сети всегда можно построить конечное число разрезов.

R1={1, 2} clip_image018={3, 4, 5} (R1, clip_image018[1])={(1, 3);(1, 4);(2, 4);(2, 5)}

C(R1, clip_image018[2])= C13 +C14 +C24 +C25=17+4+3+2=26

R1={1, 2, 3}; clip_image022={4, 5}

(R2, clip_image022[1])={(1, 4);(2, 4);(2, 5);(3, 4) ;(3, 5)}

C(R2, clip_image022[2])=4+3+2+10+5=24

R3={1, 2, 3, 4}; clip_image026={5}

Из примеров видим, что у различных разрезов разные пропускные способности. Разрез в сети имеющий наименьшую пропускную способность , будем называть минимальным разрезом.

Рассмотрим произв clip_image028 в сети G=(J, U). Какой бы путь в сети мы ни рассмотрели, по крайней мере одна дуга этого пути будет принадлежать разрезу, т. к. вершины S и t (источник и сток) принадлежат разным подмножествам. Если из сети удалить все дуги, принадлежащие какому-нибудь разрезу, то в сети не останется ни одного пути, соединяющего источник со стоком.

Рассмотрим в сети любой путь который соединяет источник со стоком. Дугу пути имеющею наименьшую пропускную способность, будем наз. минимальной дугой этого пути. И очевидно, что пропускная способность пути равна пропускной способнрсти минимальной дуги этого пути. Величина потока V, которая перемешаеися по всем возможным путям из источника в сток, не может превышать пропускнойпособности любого разреза сети: Vclip_image030Cclip_image010[1].

Т. о. если нам удастся построить такой поток {Xij*}, величина котор. V* и одновременно эта велич. будет равна пропускной способности Cclip_image032, то V* , будет велич. максимального потока в сети , а разрез clip_image032[1] и будет минимальным.