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

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

(14.4)

(14.5)

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

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

       Если   дан   поток   f,   то   число      называется   дуговым   потоком   или потоком по дуге  . Поскольку   и   удовлетворяют условиям (14.4) и (14.5), вопрос о существовании потока не возникает. Система уравнений (14.4) избыточна, так как складывая все строки ее матрицы, мы получаем нулевой вектор. Таким образом, не нарушая общности, можно отбросить одно из уравнений системы.

        Потоком в сети   назовем функцию f, сопоставляющую каждому ребру   сети целое число   и обладающую следующими свойствами:

   (кососимметрия),     (допустимость).

 

Алгоритм построения максимальных

независимых множеств вершин

Приведённый ниже алгоритм, обоснование которого дано в предыдущем под-

разделе, строит все максимальные независимые множества вершин заданного

графа.

Алгоритм 10.3 Построение максимальных независимых множеств

Вход: граф G(V, Е), заданный списками смежности Г [и].

Выход: последовательность максимальных независимых множеств.

к: = 0 { количество элементов в текущем независимом множестве }

S[k]: = 0 { S[k] — независимое множество из к вершин }

: = 0 — множество вершин, уже использованных для расширения S[k] }

Q+[k]: = V

{ Q+[k] — множество вершин, которые можно использовать для расширения S[k] }

Ml : { шаг вперед }

select v е Q+[k] { расширяющая вершина }

S[k + 1]: = S[k] U {г>} { расширенное множество }

Q~[k + 1]: = Q~[k] \ Г [г;] { вершина v использована для расширения }

Q+[k+l]: = Q+[k)\(r[v]U{v})

{ все вершины, смежные с v, не могут быть использованы для расширения }

к: = к + 1

М2 : { проверка }

for и е Q~ [/с] do

if Г [и] П Q+[k] = 0 then

goto М3 { можно возвращаться }

end if

end for

if Q+[k] = 0 then

if Q~[k\ = 0 then

yield S[k] { множество S[k] максимально }

end if

goto M3 { можно возвращаться }

else

goto Ml { можно идти вперед }

end if

M3 : { шаг назад }

v. = last(S[fc]) { последний добавленный элемент }

к: = к- 1

ЗД: = 5[А: + 1].- М

Q~ [/с]: = Q~ [fc] U {г>} { вершина v уже добавлялась }

Q+[k]: = Q+[k]\ М

if к = 0 к Q+ [*;] = 0 then

stop { перебор завершён }

else

goto М2 { переход па проверку }

end if

10.6. Доминирующие множества 353

Пример Известная задача о восьми ферзях (расставить па шахматной доске

8 ферзей так, чтобы они не били друг друга) является задачей об отыскании

максимальных независимых множеств. Действительно, достаточно представить

доску в виде графа с 64 вершииами (соответствующими клеткам доски), которыесмежны, если клетки находятся на одной вертикали, горизонтали или диагонали.

Остов наименьшего веса Остовом графа G называют граф, не содержащий циклов и состоя- щий из ребер графа G и всех его вершин. Таким образом, остов графа является деревом. Число ребер остова равно рангу графа (ν ∗ = n − −k). Число остовов графа можно вычислить по матрице Кирхгофа (см. с. 76). З а д а ч а. Дан взвешенный граф (рис. 4.33). Найти число остовов графа и остов графа минимального веса. В таблице ответов на с. 76 даны веса ребер минимального остова, суммарный вес остова Σ и число остовов графа n0.

Найти число остовов графа и остов графа минимального веса (экс- тремальное дерево). Р е ш е н и е. Число остовов графа. Число остовов графа можно вычислить по его матричным характеристикам. Известна следующая теорема.

Волновой алгоритм
	Дано: непyстой гpаф G=(V,E). Требуется найти путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). I. каждой вершине vi приписывается целое число T(vi) - волновая метка (начальное значение T(vi)=-1); заводятся два списка OldFront и NewFront (старый и новый "фpонт волны"), а также пеpеменная T (текyщее вpемя); OldFront:={s}; NewFront:={}; T(s):=0; T:=0; для каждой из веpшин, входящих в OldFront, пpосматpиваются инцидентные (смежные) ей веpшины uj, и если T(uj) = -1, то T(uj):=T+1, NewFront:=NewFront + {uj}; если NewFront = {}, то ВЫХОД("нет решения"); если t  NewFront (т.е. одна из веpшин uj совпадает t), то найден кpатчайший пyть между s и t с T(t)=T+1 промежуточными ребрами; ВЫХОД("решение найдено"); OldFront:=NewFront; NewFront:={}; T:=T+1; goto (4). Замечание: на шаге (4) "соседними" вершинами для неориентированных графов считаются все смежные вершины, а для орграфов - вершины, в которые из данной вершины ведут дуги. II. Если на шаге (6) была достигнyта веpшина t, то восстановить кpатчайший пyть можно следyющим обpазом: сpеди соседей веpшины t найдем любую веpшину с волновой меткой T(t)-1, сpеди соседей последней - веpшину с меткой T(t)-2, и т.д., пока не достигнем s. Найденная последовательность вершин определяет один из кpатчайших пyтей из s в t. Hа пpактике выгодно сохpанять на шаге (4) инфоpмацию о том, из какой веpшины "волна" пpишла в веpшинy uj - тогда восстановление пyти осyществляется быстpее.    Разметка графа после выполнения волнового алгоритма. А в разделе игр для этого алгоритма есть две реализации и менее формальное описание.