Ориентированные и неориентированные сети

Определения

Сетью (графом) G может быть назван любой объект, который можно представить как совокупность множества узлов N и множества дуг A, соединяющих их. G = {N, A}. Каждый элемент множества A есть пара (i, j) элементов множества N. Примеры графического представления сетей и задающих их множеств см. рис. 1.

Узлы также называют вершинами или точками, а дуги - ребрами, звеньями, линиями или ветвями. Граф G конечен, если конечны оба задающие его множества N и A.

Сеть G ₁, состоящую из узлов и дуг, входящих в сеть G, называют подграфом сети G; то есть G ₁ = {N ₁, A ₁ } - подграф G = {N, A}, если N ₁ N и A ₁ A. Наиболее простое представление сети получается, если использовать в качестве элементов { N }натуральные числа - номера узлов. Тогда каждая дуга характеризуется парой чисел - номерами узлов, которые она связывает.

Однако каждый узел и дуга сети характеризуются еще одной числовой величиной, смысл которой определяется в конкретных задачах. В общем случае такое поставленное в соответствие узлу число называют его интенсивностью d. Узлы называют источниками (если d > 0), стоками (если d < 0) и нейтральными узлами (если d = 0). Таким образом: N = {N₊} {N_-} {N_o}; N₊ = {n: d_n > 0 }, N_- = {n: d_n < 0 }, N_o = {n: d_n = 0 }.

Аналогично, поставленное в соответствие дуге (i, j) число той же природы, что и интенсивность узла, называют пропускной способностью дуги r_ij.

Потоком F = {f_ij: (i, j) A} в сети G называют совокупность величин f_ij - потоков в дугах, удовлетворяющих соотношениям:

f_ij - f_ji = d_i, i N; 0 £ f_{ij £} r_ij. (1)

Здесь первое выражение отражает закон сохранения потока в сети, а второе задает допустимую область изменения потоков в дугах. Во многих задачах на сетях для каждой дуги вводят дополнительную числовую характеристику - обобщенную стоимость c_ij прохождения единицы потока по дуге, не имеющую аналога для узлов. В таком случае может быть поставлена задача об оптимальном по суммарной обобщенной стоимости потоке:

c_ij f_ij ® opt (2)

при одновременном выполнении условий (1). В результате эта задача принимает вид стандартной задачи линейного (если c_ij = const), либо нелинейного (если c_ij = F (f_kl), (k, l) A) программирования.

При решении задач в дальнейшем будут упоминаться методы и алгоритмы.

Метод - путь, способ получения решения; совокупность приемов, операций, направленных на достижение некоторой цели.

Алгоритм - последовательность четко определенных правил (команд) для получения решения за конечное число шагов.

Любой алгоритм - метод; но не любой метод является алгоритмом.

Ориентированные и неориентированные сети

Дугу (i, j) называют направленной от узла i к узлу j, если дополнительный поток из i в j, протекающий по этой дуге, увеличивает величину уже существующего в ней потока, а противоположный дополнительный поток уменьшает эту величину. Направленные дуги иногда обозначают следующим образом: [ i, j ]. Направленная дуга называется ориентированной и в графическом представлении сети обозначается линией со стрелкой (см. рис. 2а). Дуга, не имеющая направления, называется неориентированной и в графическом представлении сети обозначается линией (см. рис. 2б).

Сети также могут быть ориентированными (содержащими ориентированные дуги) и неориентированными (содержащими только неориентированные дуги).

Цепью [ i, j,..., k ] из узла i в узел k называют подграф G ₁ сети G, состоящий из последовательности дуг и узлов, в которой конечный узел каждой дуги (исключая узлы i и k) является начальным узлом следующей дуги. Цепь может включать неориентированные дуги.

Путем (i, j,..., k) из узла i в узел k называют подграф G ₂ сети G, состоящий из последовательности дуг и узлов, в которой каждый узел (исключая узлы i и k) является начальным или конечным узлом только двух дуг из G ₂ и каждая дуга пути начинается и заканчивается в узлах из G ₂.

Контур - конечная цепь с началом и концом в одном и том же узле.

Цикл - конечный путь с началом и концом в одном и том же узле.

Петля - цикл или контур из одной дуги и одного узла.

Не содержащие контуров сети называют бесконтурными, а не содержащие циклов - ациклическими.

Сеть связна, если для любых двух ее узлов существует соединяющий их путь.

Сеть сильно связна, если для любых двух ее узлов существует соединяющая их цепь.

На рис. 3 приведены примеры ориентированной и неориентированной (а), (е) сетей и содержащихся в них цепи (б) и контура (в); пути (б, д), цикла (в, е) и петли (г); бесконтурной (ж) и ациклической (з); связной (а, е, ж, з) и сильно связной (а, е) сетей.

Разрез C в графе - множество его дуг, исключение которых из сети G разделяет ее на два несвязных между собой подграфа G₁, G₂ исходной сети. То есть:

C = {(i, j): (i, j) A}:

G = G ₁ G ₂ C; G ₁ G ₂ = , G ₁ C = , G ₂ C = ; i, j G: i G ₁, j G ₂; (i, j) C.

Величина разреза C, его пропускная способность R_c (G ₁ G ₂ ) в направлении от G ₁ к G ₂- это сумма пропускных способностей r_ij всех дуг [ i, j ] разреза C, начинающихся в G ₁ и оканчивающихся в G ₂:

R_c (G ₁ G₂) = r_ij.

Таким образом, каждый разрез ориентированной сети характеризуется двумя пропускными способностями: R_c (G ₁ G ₂ ) и R_c (G ₂ G ₁ ). В приложениях теории графов для сетей с одним источником s и одним стоком r большое значение имеют разрезы, разделяющие сток и исток, причем важной оказывается только величина разреза в направлении от источника к стоку. Для таких разрезов s G ₁, r G ₂; а R_c (s r) = R_c. В каждой конкретной сети разрезов этого типа может быть несколько. Тот из них, величина которого наименьшая, называется минимальным разрезом, а тот, величина которого наибольшая - максимальным разрезом.

Деревья и древовидности

Частным случаем связных сетей являются деревья.

Дерево G ₁ сети G, это связный подграф G, не содержащий циклов.

Подграф является деревом, если выполнены любые два из трех следующих условий:

1. Подграф связный.

2. Подграф ациклический.

3. Число дуг подграфа меньше числа его вершин на единицу.

Для любых двух узлов дерева существует единственный путь между ними. Остовным деревом (остовом) сети называют дерево, содержащее все узлы исходной сети. Таким образом, G _o = {N, A_o} - остовное дерево G = {N, A}, если A _oc A и G _o - дерево.

Весом дерева в сети, для дуг которой определена обобщенная стоимость c_ij, называют сумму с_ij по всем дугам дерева.

Кратчайшим остовом называют остов с наименьшим для всех остовов данной сети весом.

Максимальным остовом называют остов с наибольшим для всех остовов данной сети весом.

Древовидностью называют дерево, состоящее только из ориентированных дуг и имеющее единственный корень - узел, из которого дуги только исходят.

Древовидное дерево - дерево, являющееся древовидностью.

Древовидный остов, являющийся древовидностью.

Примеры дерева, остова, древовидности, древовидного остова приведены на рис. 5.