Ремонт принтеров, сканнеров, факсов и остальной офисной техники


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




[159]

фа G = (V, Е) называется цикл, проходящий по каждому ребру G ровно один раз (в одной и той же вершине можно бывать многократно).

a.Покажите, что в G есть эйлеров цикл тогда и только тогда, когда входящая степень каждой вершины равна ее исходящей степени.

b.Придумайте алгоритм, который за время О(Е) находит в графе эйлеров цикл (если таковой имеется). (Указание: объединяйте циклы, у которых нет общих рёбер.)

Замечания

Прекрасные руководства по алгоритмам на графах написали Ивен [65] и Тарьян [188].

Поиск в ширину рассмотрел Мур [150] при изучении путей в лабиринтах. Ли [134] независимо открыл тот же алгоритм применительно к соединениям контактов в электронных схемах.

Хопкрофт и Тарьян [102] указали на пользу представления в виде списков смежных вершин для редких графов и обнаружили важность поиска в глубину для построения алгоритмов на графах. Сам по себе поиск в глубину начал использоваться незадолго до 1960 года, в превую очередь в программах, связанных с «искусственным интеллектом».

Тарьян [185] придумал алгоритм поиска сильно связных компонент за линейное время. Алгоритм раздела 23.5 взят из книги Ахо, Хопкрофта и Ульмана [5], которые ссылаются на Косараю (S.R. Kosaraju) и Шарира (М. Sharir). Кнут [121] первым построил алгоритм тополигической сортировки за линейное время.


Минимальные покрывающие деревья

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

Упрощая ситуацию, можно сформулировать задачу так. Пусть имеется связный неориентированный граф G = (V,E), в котором V - множество контактов, а Е - множество их возможных попарных соединений. Для каждоого ребра графа (и, v) задан вес w(u, v) (длина провода, необходимого для соединения и и v). Задача состоит в нахождении подмножества Т С Е, связывающего все вершины, для которого суммарный вес

w(T) =w(u,v)

(u,v)eT

минимален. Такое подмножество Г будет деревом (поскольку не имеет циклов: в любом цикле один из проводов можно удалить, не нарушая связности). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом (spanning tree) этого графа. (Иногда используют термин «остовное дерево»; для краткости мы будем говорить просто «остов». )

В этой главе мы рассматриваем задачу о минимальном покрывающем дереве (minimum-spanning-tree problem). (Здесь слово «минимальное» означает «имеющее минимально возможный вес».)

На рисунке 24.1 приведён пример связного графа и его минимального остова.

[Возвращаясь к примеру с проводниками на печатной плате, объясним, почему задача о минимальном дереве является упрощением реальной ситуации. В самом деле, если соединяемые контакты находятся в вершинах единичного квадрата, разрешается соединять его любые вершины и вес соединения равен его длине, то минимальное покрывающее дерево будет состоять из трёх сторон квадрата. Между тем все его четыре вершины можно электрически


Рис. 24.1 24.1 Минимальное покрывающее дерево. На каждом ребре графа указан вес. Выделены ребра минимального покрывающего дерева (суммарный вес 37). Такое дерево не единственно: заменяя ребро (Ь, с) ребром (a,h), получаем другое дерево того же веса 37.

соединить двумя пересекающимися диагоналями (суммарная длина 2 у/2 < 3) и даже ещё короче (введя две промежуточные точки, в которых проводники сходятся под углом 120°.).]

В этой главе мы рассмотрим два способа решения задачи о минимальном покрывающем дереве: алгоритмы Крускала и Прима. Каждый их них легко реализовать с временем работы O(ElgV), используя обычные двоичные кучи. Применив фибоначчиевы кучи, можно сократить время работы алгоритма Прима до 0(E-\-V\gV) (что меньше E-\-\gV, если \V\ много меньше \Е\).

Оба алгоритма (Крускала и Прима) следуют «жадной» стратегии: на каждом шаге выбирается «локально наилучший» вариант. Не для всех задач такой выбор приведёт к оптимальному решению, но для задачи о покрывающем дереве это так. (Мы обсуждали это в главе 17; задача о покрывающем дереве является превосходной иллюстрацией введённых там понятий.)

В разделе 24.1 описана общая схема алгоритма построения минимального остова (добавление рёбер одного за другим). В разделе 24.2 указаны две конкретных реализации общей схемы. Первый алгоритм, восходящий к Крускалу, аналогичен алгоритму поиска связных компонент из раздела 22.1. Другой (алгоритм Прима) аналогичен алгоритму Дейкстры поиска кратчайших путей (раздел 25.2).

24.1. Построение минимального остова

Итак, пусть дан связный неориентированный графа G = (V, Е) и весовая функцией w : Е -> Ж. Мы хотим найти минимальное покрывающее дерево (остов), следуя жадной стратегии.

Общая схема всех наших алгоритмов будет такова. Искомый остов строится постепенно: к изначально пустому множеству А на каждом шаге добавляется одно ребро. Множество А всегда является подмножеством некоторого минимального остова. Ребро (и, v), добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства: Аи{(и, v)} тоже должно быть подмножеством минимального остова. Мы называем такое ребро безопасным ребром (safe edge) для А.

\textsc{Generic-MST> $(G,w)$

1$А \leftarrow \emptyset$

2{\bf while} $A$ не является остовом



[стр.Начало] [стр.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] [стр.294]