Шумейко Д.Л. - библиотека

Источник:
Хэмди А. Таха. "Введение в исследование операций", 6-е издание:
Пер. с англ. - М.: Издательский дом "Вильямс", 2001.

СЕТЕВЫЕ МОДЕЛИ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Сеть состоит из множества узлов, связанных дугами (или ребрами). Таким образом, сеть описывается парой множеств (N, А), где N - множество узлов, а А - множество ребер. Например, сеть, показанная на рис.1, описывается следующим образом.

N = {1, 2, 3, 4, 5},

А = {(1, 3), (1, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}.

Рис.1

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

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

Путем называется последовательность различных ребер, соединяющих два узла, независимо от направления потока в каждом ребре. Путь формирует цикл, если начальный и конечный узлы совпадают. Например, на рис.1 ребра (2, 3), (3, 4) и (4, 2) составляют цикл. Ориентированный цикл - это цикл, в котором все дуги ориентированы в определенном направлении.

Связная сеть - такая сеть, у которой любые два узла связаны по крайней мере одним путем. На рис.1 показан именно такой тип сети. Деревом называется связная сеть, содержащая подмножество узлов исходной сети и не имеющая циклов. Остовное дерево - это дерево, содержащее все узлы сети. На рис.2 показаны дерево и остовное дерево для сети из рис.1.

Остовное дерево Дерево

Рис.2

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