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

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

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

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

Рис. 6.1. Пример сети

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

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

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

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

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

Рис. 6.2. Дерево и остовное дерево для сети из рис. 6.1

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

УПРАЖНЕНИЯ 6.1

1. Для каждой сети, показанной на рис. 6.3, определите: а) путь, б) цикл, в) ориентированный цикл, г) дерево, д) остовное дерево.

Рис. 6.3. Сети для упражнения 1

2. Определите множества N и А для сетей, представленных на рис. 6.3.

3. Нарисуйте сеть, заданную множествами

4. iV-{1,2, 3,4, 5, 6},

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

6. Дано восемь равных квадратиков, расположенных в три линии: на первой находится два квадратика, на второй - четыре и на третьей - два. Квадратики на каждой линии располагаются симметрично вертикальной оси. Необходимо приписать каждому квадратику число от 1 до 8 так, чтобы смежные (по вертикали, горизонтали или диагонали) квадратики не имели последовательных номеров. Сформулируйте эту задачу как сетевую, и на основе сетевого представления задачи разработайте алгоритм симметричного решения.

7. Троих заключенных в сопровождении трех стражников необходимо переправить на лодке из Сан-Франциско в тюрьму на острове Алкатрас для исполнения приговора. Лодка не может перевести более двух человек одновременно. Заключенные определенно сильнее стражников, если их количество в какой-то момент превысит количество стражников. Разработайте сетевую модель, позволяющую найти такую последовательность перевозки заключенных, чтобы не возникло каких-либо инцидентов между заключенными и стражниками.

6.2. АЛГОРИТМ ПОСТРОЕНИЯ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА

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

Опишем процедуру выполнения этого алгоритма. Обозначим через N = {1, 2, п} множество узлов сети и введем новые обозначения:

Ск - множество узлов сети, соединенных алгоритмом после выполнения k-й итерации этого алгоритма,

Q - множество узлов сети, не соединенных с узлами множества Ск после выполнения k-й итерации этого алгоритма. Этап 0. Пусть С0 = 0 и С0 = N.

Этап 1. Выбираем любой узел i из множества С0 и определяем С, = {i}, тогда С, =N - {i}. Полагаем k = 2.

Основной этап к. В множестве Ск 1 выбираем узел /, который соединен самой короткой дугой с каким-либо узлом из множества Ск х. Узел / присоединяется к множеству Ск х и удаляется из множества Ск 1. Таким образом, Ск = Ск , + {;*}, С, = - {/}.

Если множество С, пусто, то выполнение алгоритма заканчивается. В противном случае полагаем k - k + 1 и повторяем последний этап.

Пример 6.2.1

Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов. На рис. 6.4 показана структура планируемой сети и расстояния (в милях) между районами и телецентром. Необходимо спланировать наиболее экономичную кабельную сеть.

Рис. 6.4. Кабельная сеть телевизионной компании

Чтобы начать выполнение алгоритма построения минимального остовного дерева, выберем узел 1 (или любой другой узел). Тогда

С,-{1}и С, ={2,3,4,5,6}.

Последовательные итерации выполнения алгоритма представлены на рис. 6.5. Здесь тонкими линиями показаны ребра, соединяющие узлы, принадлежащие множествам С* и Ct , среди которых ищется ребро с минимальной стоимостью

(длиной). Это найденное ребро показано пунктирной линией. Толстыми сплошны- т линиями обозначены ребра, соединяющие узлы множества Q (и которые ранее )зн чались пунктирными линиями).