§ 2.11.2. Количество остовных деревьев графа.

В некоторых ситуациях возникает необходимость в построении полного списка деревьев графа G.

Рассмотрим два (ориентированных или неориентированных) остовных дерева T₁=(X,A₁) и T₂=(X,A₂) графа G=(X,A).

«Расстояние» между деревьями обозначается через d(T₁,T₂) и определяется как число дуг из T₁, которых нет в T₂ (или, что эквивалентно, как число дуг из T_2, которых нет в T_1, поскольку оба дерева T₁ и T₂ имеют n-1 дуг).

§ 2.11.3. Кратчайший остов графа (sst)

Рассмотрим взвешенный связный неориентированный граф G=(X,A). Вес ребра (х_i,x_j) обозначим с_ij. Из большого числа остовов графа нужно найти один, у которого сумма весов рёбер наименьшая.

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

Задача построения кратчайшего остова графа является одной из немногих задач из теории графов, которые можно считать полностью решёнными. Существует несколько алгоритмов построения SST.

Итак, пусть T_i и T_j – два произвольных поддерева, полученных путём добавки рёбер при построении SST. Если символ T_i использовать также для обозначения множества вершин данного поддерева, то величина ∆_ij может быть определена как кратчайшее из расстояний между вершинами из T_i и вершинами из T_j, т.е.

∆_ij=min(min{x_i,x_j)}), i j (1)

_{xiTi, xjTj.}

Введём операцию J, многократное применение которой приводит к построению SST-графа.

Для поддерева T_s найти такое поддерево T_j, чтобы ∆_sj*= [∆_sj]. Пусть ) будет тем ребром, вес которого соответствует величине ∆_sj* в выражении (1). Тогда ребро ) принадлежит SST и может быть добавлено к другим рёбрам частично сформированного SST.

Алгоритм Краскала.

Шаг 1. Начать с вполне несвязного графа T, содержащего n вершин.

Шаг 2. Упорядочить рёбра графа G в порядке неубывания их весов.

Шаг 3. Начав с первого ребра в этом списке, добавлять рёбра в графе T, соблюдая условие: такое добавление не должно приводить к появлению цикла в Т.

Шаг 4 . Повторить шаг 3 до тех пор, пока число рёбер в Т не станет равным n-1. Получившееся дерево является кратчайшим остовом (SST) исходного графа G.

§ 2.13. Сети. Потоки в сетях.

Если в орграфе G=(X,A),полустепень захода некоторой вершины s равно нулю (_t(s)=0), то такая вершина называется источником. Если в орграфе G=(X,A) полустепень исхода некоторой вершины t равно нулю (_O(s)=0), то такая вершина называется стоком.

Опр. Орграф с одним источником и с одним стоком называется сетью.

В теории графов встречается задача определения максимального потока, протекающего в орграфе G =(X,A), являющемся сетью, от источника s к стоку t. При этом каждой дуге (х_i,х_j) графа G приписана некоторая пропускная способность q_ij, и эта пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге. Эта задача может возникнуть, например, при определении максимальной интенсивности транспортного потока между двумя пунктами на карте дорог, представляемой графом. Решение этой задачи также укажет ту часть сети дорог, которое образует «узкое место» в отношении потока между двумя концевыми пунктами.

Постановка задачи о максимальном потоке от s к t.

Рассмотрим сеть G =(X,A) с пропускными способностями дуг q_ij, источником s и стоком t, s,tX. Множество чисел _ij, определённых на дугах (х_i,х_j)A , называют потоками в дугах, если выполняется следующие условия:

(1)

(2)

Уравнение (1) является уравнением сохранения потока. Оно утверждает, что поток, втекающий в вершину, равен потоку, вытекающему из вершины, за исключением источника s и стока t, для которых существуют вытекание и приток величины v соответственно. Соотношение (2) указывает на то, что потоки ограничены пропускными способностями для каждой дуги графа G.

Задача состоит в том, чтобы величина

была максимальной.

- 31 -