назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [ 76 ] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


76

УПРАЖНЕНИЯ 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 (и которые ранее )зн чались пунктирными линиями).



Итерация 1 Итерация 2

Итерация 3 Итерация 4

Итерация 5 Итерация 6

(Минимальное остовное дерево)

Рис. 6.5. Последовательные итерации выполнения алгоритма построения минимального остовного дерева

Например, на первой итерации ребро (1,2) имеет наименьшую стоимость (т.е. наименьшее расстояние между пунктами сети) среди всех других ребер, соединяющих узел 1 с узлами множества С, (отметим, что узел 6 не имеет ребра, непосредственно

соединяющего его с узлом 1). Поэтому/ = 2 и С, = {1, 2}, С2 = {3, 4, 5, 6}.

Решение в виде минимального остовного дерева получено на 6-й итерации (рис. 6.5). Минимальная длина кабеля для построения такой сети равна 1 + 3 + 4 + 4- 3 + 5 = 16 милям.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [ 76 ] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]