5.4. Матрица графов

Граф может быть задан разными способами: рисунком, перечислением вершин и ребер (или дуг) и т. д. Одним из самых удобных способов является задание графа с помощью матрицы. Пусть некоторый граф G имеет п вер­шин и т ребер . Построим матрицу, имею­щую п строк и т столбцов. Каждая строка матрицы будет соответствовать вершине, а столбец - ребру графа. В столбце все элементы, кроме двух, будут равны нулю. Для ориентированного графа в строке, соответствующей начальной вершине дуги , ставят число +1, а в строке, соответствующей конечной вершине, - число -1. Для неориентированного графа в строках матрицы, соответствующих концевым вершинам ребра , ставят 1, а в ос­тальных строках - 0. Построенные матрицы называются матрицами инциденций графа.

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

Сетью называется граф, элементам которого поставлены в соответст­вие некоторые параметры. Далее элементы множества N будем называть узлами, а множества А - дугами. Пусть каждой дуге некоторой сети G = [N, а] поставлено в соответствие неотрицательное (действительное) число , называемое пропускной способностью дуги . Функ­ция С, отображающая множество А в множество неотрицательных чисел, называется функцией пропускной способности. Пусть s и t - два различных узла из N. Стационарный поток величины v из s в t в сети [N, а] есть функция f, отображающая множество А в множество неотрицательных чисел, удовлетворяющая линейным уравнениям и неравенствам

(4)

для всех , (5)

где («после x»), («перед x»).

Будем называть узел s - источником, узел t - стоком, а остальные уз­лы - промежуточными.

Если дан поток f, то число f(x,y) называется дуговым пото­ком f(x,y) или потоком по дуге (х,у). Поскольку f=0 и v=0 удовлетво­ряют условиям (4) и (5), вопрос о существовании потока не возникает. Система уравнений (4) избыточна, так как складывая все строки ее матри­цы, мы получаем нулевой вектор. Таким образом, не нарушая общности, можно отбросить одно из уравнений системы.

Потоком в сети [N,A] или [N,C] назовем функцию f, сопоставляющую каж­дому ребру (х,у) сети целое число f(x,y)и обладающую следующими свойствами:

(кососимметрия),

(допустимость).

5.6. Задача о максимальном потоке сети

Рассмотрим сеть, имеющую только один источник s и только один сток t. Рассмотрим задачу о потоке из узла s в узел t, причем s и t могут быть связаны произвольно сложной промежуточной сетью. Задача о максималь­ном потоке состоит в определении количества, которое можно перевезти из s в t. Формализуем эти понятия.

Узел s множества N называется источником потока f , если f(s, N) > 0; узел t называется стоком потока f, если f(t, N)<0; узел х называется ней­тральным, если f(s, N)=0. Поток с одним источником s и стоком t называ­ется потоком от s к t. При всех f(x, N)=0;f(s, N)=f(N,t) (все, что «вытекает» из источника, попадает в сток). Мощностью потока f называется число f(s,N)=f(N,t). Поток наибольшей мощности носит название макси­мального потока. Сечением (или разрезом) сети G = [N, а] относительно s и t называется разбиение узлов N на такие два множества S и S', что . Пропускной способностью сече­ния называется величина (сумма пропускных способностей дуг, начала которых находятся в S, а концы - в S'). Сечение с наименьшей пропускной способностью называется минимальным сечени­ем. Связь между сечениями и потоками устанавливается следующей леммой.

Лемма. Если f - поток в сети G=[N,A]от s к t и (S, S’) - сече­ние в сети G, то мощность потока f не превосходит

C(S, S'), т. е. (6)

Если в (6) имеет место равенство, то сразу можно сделать вывод о максимальном потоке f и минимальном сечении C(S, S').

Теорема (о максимальном потоке и минимальном сечении). Для любой сети величина максимального потока из s в t равна пропускной спо­собности минимального сечения, отделяющего s от t.

Алгоритм отыскания максимального потока в сети называется алго­ритмом Форда - Фалкерсона.