ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
4.10. Покрывающие деревья минимальной стоимости Пусть задан граф со взвешенными ребрами и его покрывающее дерево. Сумма весов ребер, принадлежащих покрывающему дереву, называется стоимостью дерева Покрывающее дерево графа, имеющее наименьшую стоимость по сравнению со всеми другими покрывающими деревьями этого же графа, называется покрывающим деревом минимальной стоимости. Рассмотрим задачи, решение которых сводится к нахождению покрывающего дерева минимальной стоимости. Задача 4.2. В управлении шоссейных дорог рассматривается проект строительства новых дорог, которые должны связать несколько городов некоторого района (причем необязательно непосредственно каждую пару городов. Стоимость прокладки дороги между каждой парой городов известна. Необходимо определить, между какими городами нужно проложить дороги, чтобы суммарная стоимость прокладки дорог была минимальной. Задача 4.3. Необходимо соединить проводами клеммы электрической сети, минимизируя длину проводника. Расстояния между каждой парой клемм известно. Для нахождения покрывающего дерева минимальной стоимости можно получить все покрывающие деревья, определить их стоимость и выбрать дерево минимальной стоимости. Такой подход не является эффективным. Алгоритм Краскала строит покрывающее дерево минимальной стоимости, если ребра графа просматривать в порядке неубывания их весов. Поэтому для нахождения покрывающего дерева минимальной стоимости можно предварительно использовать алгоритм сортировки ребер, а затем применить алгоритм Краскала. Тогда на каждом шаге будет выбираться ребро с минимальным весом, которое можно включить в покрывающее дерево. Такой выбор можно осуществить ив процессе выполнения алгоритма Краскала без предварительной сортировки ребер. В этом случае при выборе ребра используем алгоритм нахождения ребра минимального веса среди ребер, не включенных в дерево, при этом все ребра, образующие цикл с ребрами, включенными в дерево, исключаются из дальнейшего рассмотрения. Рассмотрим еще один алгоритм построения покрывающего дерева минимальной стоимости, не требующий предварительной сортировки ребер. Это алгоритм Прима (алгоритм ближайшего соседа. Он отличается от алгоритма Краскала тем, что в нем формируется только один букет. На очередном шаге выбирается ребро минимального веса среди 179 ребер, у которых одна концевая вершина принадлежит букету, а другая — не принадлежит. Такое ребро включается в дерево, а концевая вершина, не принадлежащая букету, включается в него. Для эффективного выбора ребра в алгоритме Прима каждой вершине v i графа, не принадлежащей букету Б приписывается метка t(v i ) — ближайшая к v i вершина, принадлежащая букету Б, и число d(v i ) — вес ребра {t(v i ),v i }. На каждом шаге выполнения алгоритма вершина v i с наименьшим числом d(v i ) добавляется к букету Б, а ребро {t(v i ),v i } — к покрывающему дереву. После добавления новой вершины v i к букету Б метка t(v j ) и число вершины v j , не принадлежащей букету, изменятся, если вес ребра меньше числа Алгоритм Прима. Вход G = (V,E) — взвешенный граф, где V — множество вершин, E — множество ребер. Выход T — покрывающее дерево минимальной стоимости. 1. Начальная установка. Каждой вершине v i приписать t(v i ) = 0; Б := {v}, v — произвольная вершина графа включается в букет Б каждой вершине v i , не принадлежащей букету, приписать d(v i ) = , y := v, y—– последняя вершина, включенная в букет T := , дерево пусто. 2. Пересчет чисел d(v i ) и меток t(v i ). v i Г – Б пересчитать d(v i ): d(v i ) := min(d(v i ), вес. Если число d(v i ) изменилось (уменьшилось, то t(v i ):= y. 3. Из всех вершин v i Б выбрать вершину v j с наименьшим числом d(v j ); Б := Б {v j }, включить выбранную вершину в букет y := v j , y — последняя вершина, включенная в букет T := T {t(v i ),v i }, добавить ребро в дерево. 4. Если все вершины графа включены в букет (Б = V), то конец алгоритма, иначе перейти к п При программной реализации алгоритма Прима букет можно представить бинарным массивом Б, й элемент которого соответствует вершине и, если вершина v i принадлежит букету, то Б = 1, иначе Б = 0. Числа d(v i ) целесообразно хранить в массиве D, й элемент которого соответствует вершине v i , а его значение D i — числу d(v i ). Для хранения меток можно использовать массив T, й элемент которого соответствует вершине v i , а его значение T i — метке t(v i ). Заметим, что массив по окончании алгоритма хранит полную информацию о структуре построенного покрывающего дерева минимальной стоимости пара {T i ,i} соответствует ребру дерева, если T i ≠ 0, а сумма всех элементов массива D равна стоимости дерева. Работу алгоритма Прима при построении покрывающего дерева минимальной стоимости графа, диаграмма которого изображена на рис, представим в табл. 4.4, отображающей изменения значений массивов Б, D и T на каждом шаге выполнения алгоритма. v 2 2 v 4 1 2 v 1 v 6 7 4 8 9 5 5 v 3 v 5 Рис. Диаграмма графа Таблица 4.4 Работа алгоритма Прима Номер шага Пункт алгоритма Состояние массивов Б и T Вершина y 1 2 3 4 1 1 Б, 0, 0, 0, 0, 0) D=(0, , , , , ) T=(0, 0, 0, 0, 0, 0) 1 2 2 Б, 0, 0, 0, 0, 0) D=(0, 1 , 9, , , ) T=(0, 1, 1, 0, 0, 0) 1 3 3 Б, 1, 0, 0, 0, 0) D=(0, 1 , 9, , , ) T=(0, 1, 1, 0, 0, 0) 2 4 4 Б, продолжить 2 5 2 Б, 1, 0, 0, 0, 0) D=(0, 1 , 7, 2, , ) T=(0, 1, 2, 2, 0, 0) 2 6 3 Б, 1, 0, 1, 0, 0) D=(0, 1 , 7, 2, , ) T=(0, 1, 2, 2, 0, 0) 4 181 Окончание табл 1 2 3 4 7 4 Б, продолжить 4 8 2 Б, 1, 0, 1, 0, 0) D=(0, 1 , 4, 2, 8 , 2) T=(0, 1, 4, 2, 4, 4) 4 9 3 Б, 1, 0, 1, 0, 1) D=(0, 1 , 4, 2, 8 , 2) T=(0, 1, 4, 2, 4, 4) 6 10 4 Б, продолжить 6 11 2 Б, 1, 0, 1, 0, 1) D=(0, 1 , 4, 2, 5 , 2) T=(0, 1, 4, 2, 6, 4) 6 12 3 Б, 1, 1, 1, 0, 1) D=(0, 1 , 4, 2, 5 , 2) T=(0, 1, 4, 2, 6, 4) 3 13 4 Б, продолжить 3 14 2 Б, 1, 1, 1, 0, 1) D=(0, 1 , 4, 2, 5 , 2) T=(0, 1, 4, 2, 6, 4) 3 15 3 Б, 1, 1, 1, 1, 1) D=(0, 1 , 4, 2, 5 , 2) T=(0, 1, 4, 2, 6, 4) 5 16 4 Б, конец 5 Диаграмма построенного покрывающего дерева минимальной стоимости представлена на рис. v 2 2 v 4 12 v 1 v 6 4 5 v 3 Рис. Диаграмма покрывающего дерева минимальной стоимости 182 4.11. Поиcк в орграфе Задача 4.4. Система состоит из конечного числа объектов. Между некоторыми из них установлены одно- или двусторонние каналы связи. Определить, каким объектам системы может передать сообщение по каналам связи заданный объект. Решение. Рассматриваемую систему можно представить орграфом, в котором вершины соответствуют объектам, а дуги – каналам связи. Объект, соответствующий вершине v i , может передать сообщение объекту, соответствующему вершине v j , если в орграфе существует путь изв, те. если вершина v j достижима из v i . Пусть заданному объекту соответствует вершина v i . Тогда для решения задачи необходимо найти все вершины орграфа, достижимые из v i . Процесс нахождения вершин, достижимых из заданной, называется поиском в орграфе. Одним из методов поискав орграфе является поиск в глубину. Порядок посещения вершин при поиске в глубину определяется следующими правилами 1. Посещаем начальную вершину v i и считаем ее текущей. 2. Если v t — текущая вершина, v j — вершина, смежная вершине v t и еще не посещалась, то посещаем ее и считаем текущей. 3. Если исходная вершина v i — текущая вершина и все смежные с ней уже посещались, то поиск заканчивается. 4. Если v t — текущая вершина и все смежные с ней уже посещались, то текущей считаем вершину, из которой пришли в вершину Процесс поискав глубину можно представить как построение ориентированного дерева, корнем которого является начальная вершина орграфа, остальные вершины дерева — вершины орграфа, достижимые изначальной. Дуги дерева соответствуют дугам орграфа, по которым осуществлялось движение вовремя поиска. На рис представлен орграфа на рис — дерево поискав глубину с начальной вершиной 1. Нижний индекс около номера вершины дерева определяет порядок посещения вершин. Для программной реализации метода поискав глубину можно использовать рекурсивный или итеративный алгоритм. В алгоритмах используется множество V’ вершин, достижимых изначальной. В исходном состоянии оно содержит только начальную вершину. В итеративном алгоритме для запоминания вершин, предшествующих текущей, используется стек. Дерево поиска можно сохранить в массиве T, количество элементов которого равно количеству вершин орграфа. Элемент T i представляет собой вершину, предшествующую вершине i в дереве. Если вершина i — корень дерева, то T i = 0. Если вершина i недостижима 183 1 2 3 4 5 6 7 8 9 1 1 2 2 4 8 3 3 7 9 5 4 6 5 8 7 9 6 изначальной. В исходном состоянии элемент массива T, соответствующий начальной вершине, равен 0, а все остальные равны –1. Рис. Диаграмма графа Рис. Дерево поискав глубину 184 Рекурсивный алгоритм 4.9 (рис) поискав глубину Вход v — текущая вершина. Выход последовательность вершин орграфа в порядке их посещения в процессе поискав глубину (начальная вершина выводится перед первым обращением T — дерево поискав глубину. Глобальные параметры V’ — множество вершин, достижимых изначальной. Рис. Рекурсивный алгоритм поискав глубину Итеративный алгоритм 4.10 (рис) поискав глубину Вход v — начальная вершина. Выход последовательность вершин орграфа в порядке их посещения в процессе поискав глубину T — дерево поискав глубину. Поиск в глубину (v) Конец Поиск в глубину ( x) x T x := v Г 185 +Рис. Итеративный алгоритм поискав глубину Поиск в глубину (v) v := верх стека Г Конец извлечь из стека v V’ :={v} T v := поместить v в стек x V’ := V’ {x} T x := v поместить x в стек стек пуст 186 1 1 2 2 4 3 5 4 3 5 7 6 6 7 8 8 9 9 Задача 4.5. Система состоит из конечного числа объектов. Между некоторыми из них установлены одно- или двусторонние каналы связи. Определить пути передачи сообщения по каналам связи от заданного объекта ко всем достижимым, содержащие минимальное число промежуточных объектов. Решение. Рассматриваемую систему можно представить орграфом, в котором вершины соответствуют объектам, а дуги – каналам связи. Пути передачи сообщения от заданного объекта ко всем достижимым можно представить деревом поиска. Поиск в глубину не позволяет найти пути, содержащие минимальное число промежуточных объектов. Для нахождения таких путей используется поиск в ширину Порядок посещения вершин при поиске в ширину определяется следующими правилами 1. Посещаем начальную вершину v i и считаем ее текущей. 2. Если v t — текущая вершина, Г) — множество вершин, смежных сто вершины из множества Г, которые еще не посещались, последовательно посещаем, а вершину, которую посетили вслед засчитаем текущей. 3. Если v t — последняя вершина, которая посещалась при поиске, является текущей и все вершины, смежные с ней, уже посещались, то поиск заканчивается. Дерево поискав ширину с начальной вершиной 1 для орграфа рис) представлено на рис. Нижний индекс около номера вершины дерева определяет порядок посещения вершин. Рис.4.32. Дерево поискав ширину При программной реализации метода поискав ширину для запоминания порядка посещения вершин используется очередь, а множество V’ — для хранениявершин, достижимых изначальной. Дерево поискав ширину можно сохранить в массиве T, в котором элемент T i представляет собой вершину, предшествующую вершине i в дереве. Алгоритм 4.11 (рис) поискав ширину Вход v — начальная вершина. Выход последовательность вершин орграфа в порядке их посещения в процессе поискав глубину T — дерево поискав ширину. Рис. Алгоритм поискав ширину Поиск в ширину (v) v := элемент из очереди Конец v V’ := {v} T v := поместить v в очередь x V’ :=V’ {x} T x := v поместить x в очередь очередь пуста Г) –V’ 188 4.12. Связность в орграфе. Компоненты сильной связности Две вершины v i и v j орграфа G = (V,E) называются сильно связанными, если v i достижима из v j и v j достижима из v i , те. вершины v i и v j взаимодостижимы. Две вершины v i и v j орграфа G = (V,E) называются односторонне связанными, если v i достижима из v j или v j достижима из Две вершины v i и v j орграфа G = (V,E) называются слабосвязанными, если они связаны в графе G’, полученном из орграфа G’ путем отмены ориентации дуг. Если все вершины в орграфе сильно (односторонне, слабо) связаны, то орграф называется сильно (односторонне, слабосвязанным. На рис показаны диаграммы сильно, односторонне и слабосвязанных орграфов. а v 1 v 2 б v 1 v 2 в v 1 v 2 v 3 v 4 v 3 v 4 v 3 Рис. Диаграммы орграфов а — диаграмма сильно связного орграфа б — диаграмма односторонне связного орграфа в — диаграмма слабо связного орграфа На множестве вершин орграфа можно определить отношение взаи- модостижимости. Пара вершин (v i ,v j ) принадлежит отношению взаи- модостижимости, если v i и v j взаимодостижимы. Отношение взаимодос- тижимости является отношением эквивалентности оно рефлексивно, симметрично и транзитивно, поэтому оно разбивает множество вершин на классы эквивалентных вершин. Подграф, построенный на множестве вершин одного класса эквивалентности, представляет собой компоненту сильной связности орграфа. Для нахождения отношения H взаимодостижимости используются отношения R достижимости и Q контрдостижимости. Пара вершин (v i ,v j ) принадлежит отношению R достижимости, если v j достижима из v i . Пара вершин (v i ,v j ) принадлежит отношению Q контрдостижимости, если достижима из v j . Отношения достижимости, контрдостижимости и взаимодостижимости будем задавать матрицами R, Q и H соответственно Рассмотрим два способа получения матрицы R достижимости. Первый способ. Получить матрицу R достижимости можно, используя поиск в орграфе. Для этого необходимо инициализировать матрицу R нулями, а затем последовательно формировать строки матрицы. При формировании й строки, используя поиск в орграфе, находится множество V’ вершин, достижимых из вершины i. Если вершина j принадлежит множеству, то элементу с присвоить значение 1. Второй способ. Вычислить матрицу R достижимости можно по формуле R = I + M + , где I — бинарная матрица, содержащая единицы только на главной диагонали М — матрица смежности орграфа M + — транзитивное замыкание отношения, представленного матрицей смежности орграфа, которое можно вычислить, используя алгоритм 3.10 объединения степеней или алгоритм 3.11 Уоршалла. Отношение Q контрдостижимости вычисляется по формуле Q := R –1 , а отношение H взаимодостижимости — по формуле H := R Q. По матрице H взаимодостижимости можно построить разбиение множества вершин орграфа на классы эквивалентности, используя алгоритм, тем самым найдем подмножества вершин, образующих компоненты сильной связности орграфа. На рис представлена диаграмма орграфа, на рис — матрицы отношений достижимости, контрдостижимости и взаимодостижимо- сти, а на рис — компоненты сильной связности. 1 2 3 4 5 6 7 8 9 10 11 Рис. Диаграмма орграфа 190 а 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 б 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 в 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 Рис. Матрицы отношений а — достижимости б — контрдостижимости; в — взаимодостижимости 191 1 2 3 4 5 6 7 8 9 10 11 Рис. Компоненты сильной связности Множество V вершин орграфа (рис) разбивается отношением H взаимодостижимости на пять классов эквивалентности V 1 = {1,2,6}, V 2 = {3,4,8,9}, V 3 = {5}, V 4 = и V 5 = {10,11}, следовательно, орграф имеет пять компонент сильной связности. Орграф G * = (V * ,E * ), в котором V * = {V 1 ,V 2 ,…,V n }, где n — количество компонент сильной связности, V i — множество вершин й компоненты сильной связности, E * = {(V i ,V j ) | v i и v j и E}, называется конденсацией орграфа G = (V,E). Конденсация G * орграфа получается стягиванием в одну вершину каждой компоненты сильной связности. Конденсация G * орграфа G (рис) показана на рис. V 1 V 2 V 3 Рис. Конденсация орграфа Базой B орграфа G называется такое множество вершин, которое удовлетворяет следующим двум условиям 1) каждая вершина орграфа G достижима хотя бы из одной вершины множества B; 2) в B нет вершины, которая достижима из другой вершины множества. Из этих двух условий следует, что 192 1) в множестве B нет двух вершин, которые принадлежат одной и той же компоненте сильной связности орграфа G; 2) в любом орграфе без циклов существует единственная база — она состоит из всех таких вершин орграфа, полустепени захода которых равны нулю. Конденсация G * орграфа G не содержит циклов, поэтому имеет единственную базу B * , состоящую из вершин орграфа G * , полустепени захода которых равны нулю. Базы орграфа G можно строить так из каждой компоненты сильной связности, соответствующей вершине базы B * конденсации G * надо взять по одной вершине. Базой орграфа G * (рис) является множество B * = {V 1 ,V 3 }, абазами орграфа G (рис) являются множества B 1 = {1,5}, B 2 = и B 3 = {6,5}. Антибазой B орграфа G называется такое множество вершин, которое удовлетворяет следующим двум условиям 1) из любой вершины орграфа G достижима хотя бы одна вершина множества B ; 2) в B нет вершины, из которой достижима другая вершина множества Из этих двух условий следует, что 1) в множестве B нет двух вершин, которые принадлежат одной и той же компоненте сильной связности орграфа G; 2) в любом орграфе без циклов существует единственная антибаза — она состоит из всех таких вершин орграфа, полустепени исхода которых равны нулю. Конденсация G * орграфа G не содержит циклов, поэтому имеет единственную антибазу B * , состоящую из вершин орграфа G * , полу- степени исхода которых равны нулю. Антибазы орграфа G можно строить так из каждой компоненты сильной связности, соответствующей вершине антибазы B * конденсации G * надо взять по одной вершине. Антибазой орграфа G * (рис) является множество B * = {V 4 ,V 5 }, а антибазами орграфа G (рис) являются множества B 1 ={7,10} и = {7,11}. Задача 4.6. Руководство организации должно иметь возможность получать информацию от каждого сотрудника и иметь власть над каждым сотрудником. Необходимо сформировать эффективное руководство для управления организацией из наименьшего числа людей. Решение. 1. Построим орграф G = (V,E), в котором вершины соответствуют членам организации и (v i ,v j ) E, если член организации, соответствующий вершине v i , имеет возможность непосредственно связываться с членом организации, соответствующим вершине v j . Наименьшее число лиц, которые знают или могут получать все сведения об организации, образуют одну из антибаз B орграфа G. 2. Построим орграф G’ = (V,E’), в котором вершины соответствуют членам организации и (v i ,v j ) E’, если член организации, соответствующий вершине v i , имеет непосредственное влияние на члена организации, соответствующего вершине v j . Наименьшее число лиц, имеющих власть над каждым сотрудником, образуют одну из баз B’ орграфа G’. 3. Руководство может представлять собой множество B B’ наименьшей мощности. |