|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[158] оставшихся вершину г с максимальным значением f[v]. Любая оставшаяся вершина и, из которой достижима г, будет иметь г своим предшественником (ни одна из отброшенных вершин не достижима из и, иначе и г была бы достижима из и и вершина и попала бы в число отброшенных). Таким образом мы найдём вторую сильно связную компоненту - в неё входят те из оставшихся вершин, из которых достижима вершина г (другими словами, те из оставшихся, которые достижимы из г в транспонированном графе). Теперь понятен смысл строки 3 алгоритма Strongly-Connected-Components: поиск в глубину в транспонированном графе поочерёдно «отслаивает» сильно связные компоненты. Скажем то же самое более формально: Теорема 23.17 Алгоритм Strongly-Connected-Components правильно находит сильно связные компоненты ориентированного графа. Доказательство. В строке 3 алгоритма происходит вызов алгоритма DFS на транспонированном графе. Этот алгоритм просматривает вершины в порядке убывания параметра f[v], вычисленного в строке 1. При этом строятся деревья поиска, про которые мы хотим доказать, что они будут сильно связными компонентами. На каждом шаге цикла рассматривается очередная (в порядке убывания параметра /) вершина v. Вершины уже построенных деревьев поиска в этот момент чёрные, а остальные вершины - белые. (Заметим, что при этом всякая вершина, достижимая в графе GT из чёрной, сама будет чёрной.) Если очередная вершина и оказывается чёрной, то алгоритм DFS не делает ничего. Если же она белая, то вызов процедуры DFS-Visit(m) в строке 7 алгоритма DFS сделает её и все достижимые из неё в графе GT вершины чёрными. Мы должны показать, что эти вершины образуют сильно связную компоненту. Если какая-то белая вершина v достижима из и в графе GT, то и будет предшественником v, поскольку и достижима из v в G, никакие чёрные вершины не достижимы из v в G и и имеет максимальное значение параметра / среди всех белых вершин. С другой стороны, если белая вершина v не достижима из и в графе GT, то она не может иметь и своим предшественником. Чёрные вершины также не могут иметь и своим предшественником (их предшественники найдены на предыдущих шагах). Поэтому множество белых вершин, достижимых из и в графе GT, совпадает с множеством вершин, имеющих и своим предшественником, то есть является сильно связной компонентой. Упражнения 23.5-1 Как может изменится количество сильно связных компонент гра- фа при добавлении к нему одного ребра? 23.5-2 Применте алгоритм Strongly-Connected-Components к графу рис. 23.6. Найдите времена завершения, вычисляемые в строке 1, и лес, создаваемый строкой 7. Считайте, что цикл в строках 5-7 алгоритма DFS перебирает вершины в алфавитном порядке и что списки смежных вершин также упорядочены по алфамиту. 23.5-3 Профессор решил, что алгоритм поиска сильно связных компонент можно упростить, если использовать исходный (а не транспо-нированноый) граф при втором поиске, но вершины сортировать в порядке увеличения времён завершения. Прав ли он? 23.5-4 Пусть G - ориентированный граф. Если стянуть каждую его сильно связную компоненту в точку, и после этого отождествить рёбра с одинаковыми началами и концами, получится граф компонент (component graph) GSGG = {VSGG, ESGG). Другими словами, элементами VSGG являются сильно связные компоненты С, и ESGG содержит ребро (и, v) в том и только в том случае, если в G есть ориентированное ребро, начало которого принадлежит и, а конец - v (см. пример на рис. 23.9 (с)). Докажите, что граф компонент не имеет циклов. 23.5-5 Постройте алгоритм, находящий за время 0{E-\-V) граф компонент данного ориентированного графа. (В строимом графе любые две вершины должны быть соединены не более чем одним ребром.) 23.5-6 Дан ориентированный граф G = (V, Е). Как построить как можно меньший граф G = (V, Е), который имел бы те же самые сильно связные компоненты и тот же граф компонент? Постройте эффективный алгоритм решения этой задачи. 23.5-7 Ориентированный граф называется G = (V, Е) называется полусвязным (semiconnected), если для любых двух его вершин и и v либо v достижима из и, либо и достижима из v. Придумайте эффективный алгоритм, определяющий, будет ли граф полусвязным. Каково время его работы? Задачи 23-1 Классификация ребер при поиске в ширину Классифицируя рёбра графа по типам, мы исходили из дерева поиска в глубину. Аналогичная классификаия возможно и для дерева поиска в ширину (для рёбер, достижимых из начальной вершины). а. Докажите следующие свойства для случая поиска в ширину в неориентированном графе: 1.Не бывает прямых и обратных рёбер. 2.Если (и, v) - ребро дерева, то d[v] = d[u] + 1. Рис. 23.8 23.10 Точки раздела, мосты и двусвязные компоненты связного неориентированного графа (задача 23-2). Точки раздела и мосты - тёмно-серые, двусвязные компоненты - наборы рёбер в пределах одной серой области (внутри которой указано Ьсс). 3. Если (и, v) - перекрёстное ребро, то d[v] = d[u] или d[v] = d[u] + 1. b. Докажите следующие свойства для случая поиска в ширину в ориентированном графе: 1.Не бывает прямых рёбер. 2.Если (и, v) - ребро дерева, то d[v] = d[u] + 1. 3.Если (и, v) - перекрёстное ребро, то d[v] d[u] + 1. 4.Если (и, v) - обратное ребро, то 0 d[v] < d[u]. 23-2 Точки раздела, мосты и двусвязные компоненты Пусть G = (V, Е) - связный неориентированный граф. Точка раздела (articulation point) графа G - это вершина, при удалении которой граф G перестаёт быть связным. Мост (bridge) - это ребро с аналогичным свойством. Двусвязная компонента (bicon-nected component) - это максимальный набор рёбер, любые два ребра которого принадлежат общему простому циклу (см. пример на рис. 23.10). Точки раздела, мосты и двусвязные компоненты можно найти с помощью поиска в глубину. Пусть Gv = (V, Ev) - дерево поиска в глубину в графе G. a.Докажите, что корень Gv является точкой раздела, если и только если у него более одного сына в Gv. b.Пусть v - отличная от корня вершина Gv. Докажите, что v - точка раздела G, если и только если не существует обратного ребра (u,w), для которого и - потомок v и w - предок v в Gv, отличный от w. c.Пусть /ом?[и] - минимальное число среди d[v] и чисел d[w] для всех w, для которых имеется обратное ребро (и, w) для некоторой вершины и, являющейся потомком v. Покажите, как можно вычислить /ом? [и] для всех v £ V за время 0(V). d.Как найти все точки раздела за время О(Е)? e.Докажите, что ребро графа G является мостом в том и только том случае, когда оно не входит ни в какой простой цикл. f.Как найти все мосты графа G за время О(Е)? g.Докажите, что двусвязные компоненты графа составляют разбиение множества всех рёбер графа, не являющихся мостами. h.Придумайте алгоритм, который за время 0(E) помечает каждое ребро е графа G некоторым целым числом Ьсс[е], при этом метки двух рёбер совпадают, если и только если рёбра принадлежат одной двусвязной компоненте. 23-3 Эйлеров цикл Эйлеровым циклсш(Еи1ег tour) связного ориентированного гра- |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||