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

Цепь: S₁(2, 7)=(2, 3, 4, 5, 7)= (U₃, U₅, U₇, U₁₀,)

S₂(2, 7)=(2, 4, 6, 7)

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

S₃(2, 2)=(2, 3, 5, 4, 2)

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

Путь:

S₁(1, 7)=(1, 3, 5, 7)=( U₁ U₂ U₃)

S₂(1, 7)=(1, 3, 5, 4, 7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разряд в сети

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

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

R₁={1, 2} ={3, 4, 5} (R_1, )={(1, 3);(1, 4);(2, 4);(2, 5)}

C(R_1, )= C₁₃ +C₁₄ +C₂₄ +C₂₅=17+4+3+2=26

R₁={1, 2, 3}; ={4, 5}

(R_2, )={(1, 4);(2, 4);(2, 5);(3, 4) ;(3, 5)}

C(R_2, )=4+3+2+10+5=24

R₃={1, 2, 3, 4}; ={5}

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

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

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

Т. о. если нам удастся построить такой поток {X_ij^*}, величина котор. V^* и одновременно эта велич. будет равна пропускной способности C, то V^* , будет велич. максимального потока в сети , а разрез и будет минимальным.