ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
4.7. Связность Задача 4.1. Из шести человек каждый знаком с двумя другими. Может ли каждый из них через своих знакомых познакомиться со всеми остальными Решение. Отношение знакомства представим графом, в котором каждая вершина соответствует человеку и две вершины смежны, если соответствующие им люди знакомы. Если диаграмма полученного графа имеет вид, например то ответ на вопрос задачи будет положительным, а если диаграмма полученного графа имеет вид то ответ будет отрицательным. В первом случае граф является связным, а во втором — несвязным. Граф называется связным, если в нем для каждой пары вершин найдется соединяющая их цепь, иначе – несвязным. Две вершины графа 169 называются связанными, если существует соединяющая их цепь. В связном графе все пары вершин связаны. Отношение связанности вершин является отношением эквивалентности оно рефлексивно (каждая вершина соединена с собой цепью нулевой длины, симметрично (всякая цепь, записанная в обратном порядке, также является цепью) и тран- зитивно (если имеется цепь, соединяющая вершины x и y и цепь, соединяющая вершины y и z, то соединение этих цепей в вершине y даст маршрут из вершины x в вершину z, из которого можно выделить цепь, соединяющую вершины x и z), поэтому оно разбивает множество вершин на классы эквивалентных вершин. Подграф, построенный на множестве вершин одного класса эквивалентности, представляет собой связную компоненту графа. Связный граф имеет одну компоненту связности, несвязный — более одной. Отношение связанности вершин графа G=(V,E) можно задать матрицей связанности С порядка n n , где n=|V| . Элемент матрицы связанности, если вершины i и j связаны и c ij =0, если вершины i и j не связаны. Рассмотрим два способа получения матрицы связанности. Первый способ. Получить матрицу связанности С можно, используя алгоритм 4.4 нахождения всех максимальных простых цепей, основанный на методе поиска с возвращением. Для этого необходимо инициализировать матрицу С нулями, а затем последовательно формировать строки матрицы. При формировании й строки находятся все максимальные простые цепи с начальной вершиной i. Если цепь найдена и содержит вершину j, то элементу с присвоить значение 1. Второй способ. Вычислить матрицу связанности С можно по формуле С = I + M + , где I — бинарная матрица, содержащая единицы только на главной диагонали М — матрица смежности графа M + — транзитивное замыкание отношения, представленного матрицей смежности графа, которое можно вычислить, используя алгоритмы 3.10 — 3.11 или их модификации. По матрице связанности С можно построить разбиение множества вершин графа на классы эквивалентности, используя алгоритм 3.14, тем самым найдем подмножества вершин, образующих связные компоненты графа. Найти разбиение S множества вершин графа G = (V,E) на подмножества вершин, образующих связные компоненты, можно и без формирования матрицы связанности, используя алгоритм 4.4 нахождения всех максимальных простых цепей следующим образом 1. A := V; S := . 2. Пока A выполнять пп.3 — 5. 3. Выбрать вершину v A; М := {v}. 4. Найти все максимальные простые цепи с начальной вершиной v и все вершины, входящие в максимальные простые цепи, включить в множество М. M — множество вершин, образующих связную компоненту графа. 5. S := S {M}; A := A – M. Мостом называется ребро, удаление которого увеличивает число связных компонент графа. Существует несколько признаков мостов 1) ребро {v i ,v j } является мостом в томи только в том случае, если (v i ,v j ) — единственный маршрут, соединяющий вершины v i и v j ; 2) ребро {v i ,v j } является мостом в томи только в том случае, если найдутся две вершины v k и v l такие, что каждый маршрут, соединяющий их, содержит v i и v j ; 3) ребро {v i ,v j } является мостом в томи только в том случае, если оно не принадлежит ни одному циклу. Множество ребер, исключение которых увеличивает число связных компонент графа, называется разрезом. Реберной связностью связного графа называется наименьшее число ребер, удаление которых приводит к несвязному графу. Вершина графа называется точкой сочленения, если ее удаление увеличивает число связных компонент. Концевые вершины мостов являются точками сочленения, но точка сочленения может не являться концевой вершиной моста. Граф без точек сочленения называется двусвязным. Вершинной связностью связного графа называется наименьшее число вершин, удаление которых приводит к несвязному графу. 4.8. Деревья Связный ациклический граф называется деревом. Несвязный ациклический граф называется лесом. Лес представляет собой множество деревьев. Дерево и лес обладают следующими свойствами 1) количество ребер любого дерева на единицу меньше количества вершин 2) количество ребер любого леса меньше количества вершин на количество деревьев в нем 3) любые две вершины, принадлежащие различным деревьям — не смежны 171 4) любую пару вершин дерева соединяет единственная простая цепь 5) если в дереве любую пару несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл 6) если две вершины леса, принадлежащих различным деревьям, соединить ребром, то количество деревьев уменьшится на единицу. Вершина дерева, степень которой равна единице, называется висячей вершиной или листом Центральная вершина дерева (эксцентриситет которой равен радиусу) называется корнем. Если из дерева D, имеющего радиус r, удалить все его листья, то получим дерево D 1 , имеющее радиус r – 1 и те же самые корни. Продолжая процесс, получим дерево с одной либо с двумя вершинами, которое имеет те же корни, что и исходное дерево, следовательно, любое дерево имеет один, либо два корня. На рис представлена диаграмма дерева, в котором вершины 1, 3, 5, 6, 8, 9 и 11 являются листьями, а вершины 4 и 7 – корнями. 1 6 8 2 4 7 10 11 3 5 9 Рис. Диаграмма дерева Каждому дереву с n вершинами можно поставить во взаимно однозначное соответствие последовательность длины n – 2, элементы которой берутся из множества вершин. Получить такую последовательность для заданного дерева, множество вершин которого V = {1, 2,…, n}, можно следующим образом 1. Выполнить п n – 2 раза. 2. Найти лист с минимальным номером, исключить его, вершину, смежную с ним, занести в последовательность. Рассмотрим дерево, диаграмма которого изображена на рис. Выбираем у него лист с наименьшим номером. Это вершина 1. Удалим ее вместе с инцидентным ребром и вершину 2, смежную с ней, запишем на первое место последовательности. После этого листом с наименьшим номером будет вершина 3. Удалим ее вместе с инцидентным ребром и 172 вершину 2, смежную с ней, запишем на второе место последовательности. Далее листом с наименьшим номером будет вершина 2. Удалим ее вместе с инцидентным ребром и вершину 4, смежную с ней, запишем на третье место последовательности. Продолжая выполнять такие действия, получим для данного дерева определенную единственным образом последовательность (2, 2, 4, 4, 7, 7, 10, 10, 10). Каждая последовательность P длины n – 2, элементы которой берутся из множества вершин, однозначно определяет дерево с n вершинами. Построить такое дерево для заданной последовательности P можно следующим образом 1. Составить множество N натуральных чисел (1,2,…,n). 2. i := 1. 3. Выполнять п, пока |N| > 2. 4. Найти в множестве N минимальное число m, которого нет в последовательности ребро дерева. Число m удалить из множества N, а P i — из последовательности P. i := i + 1. 5. Последнее ребро образуется оставшимися элементами множества. Построим дерево, которое определяется последовательностью P = (4, 2, 4, 7, 7, 7, 10, 11, 11). В этой последовательности девять элементов, поэтому в дереве будет 11 вершин. Составим множество N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Найдем в этом множестве минимальное число, которого нет в последовательности P. Это число 1. Оно с первым элементом последовательности образует ребро {1,4}. Удалим из множества N число 1, из последовательности P — число 4 и получим P = ( , 2, 4, 7, 7, 7, 10, 11, 11) и N = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Теперь снова найдем в множестве N минимальное число, которого нет в последовательности. Это число 3. Оно со вторым элементом последовательности образует ребро {3,2}. Удалим из множества N число 3, из последовательности число 2 и получим P = ( , ,4, 7, 7, 7, 10, 11, 11) и N = {2, 4, 5, 6, 7, 8, 9, 10, 11}. Продолжая выполнять такие действия будем получать новые ребра дерева. Когда все элементы из последовательности будут исключены, в множестве N останутся два элемента N = {10, 11}, которые образуют последнее ребро дерева. Диаграмма полученного дерева представлена на рис. Так как каждому дереву с n вершинами можно поставить во взаимно однозначное соответствие последовательность длины n – 2, элементы которой берутся из множества вершин, то количество различных деревьев, которые можно построить на n вершинах равно количеству таких последовательностей (размещений с повторениями из n элементов по n – 2 местам, те. n n–2 . 173 1 6 8 2 4 7 10 11 3 5 9 Рис. Диаграмма дерева, которое определяется последовательностью P = (4, 2, 4, 7, 7, 7, 10, 11, 11) 4.9. Покрывающие деревья графа Покрывающим (остовным) деревом графа G называется дерево, являющееся подграфом графа G и содержащее все его вершины. Если граф G несвязный, то множество, состоящее из остовных деревьев каждой связной компоненты, называется покрывающим (остовным) лесом. Для того, чтобы получить покрывающее дерево связного графа, из него нужно удалить ребра, образующие циклы. Количество ребер связного графа, которые нужно удалить из него для получения покрывающего дерева, не зависит от порядка удаления ребер и равно m – n + 1, где m — количество ребер графа, n — количество вершин, так как дерево с n вершинами содержит n – 1 ребро и это на m – n + 1 меньше, чем m. Удаление не каждого подмножества из m – n + 1 ребер превращает связный граф в покрывающее дерево. Для того, чтобы получить покрывающий лес несвязного графа, содержащего связных компонент, из него нужно удалить m – n + k ребра, так как из каждой й связной компоненты нужно удалить m i – n i + 1 ребра для получения покрывающего дерева этой компоненты. Удаление не каждого подмножества из m – n + k ребер превращает несвязный граф, содержащий k связных компонент, в покрывающий лес. Рассмотрим алгоритм построения покрывающего леса, предложенный Дж. Краскалом в 1957 г. Суть алгоритма состоит в просмотрев произвольном порядке ребер исходного графа. Для каждого ребра принимается решение о том, будет ли оно включено в покрывающий лес или нет. Очередное ребро включается в лес, если оно с уже включенными ранее в лес ребрами не образует цикл. Для определения, образует ли ребро с ранее включенными в лес ребрами цикл, будем использовать понятие букет. Букет — это множество вершин, принадлежащих одной связной компоненте. Некоторое 174 ребро образует цикл с ребрами, уже включенными в лес, если обе его концевые вершины принадлежат одному и тому же букету. Если граф связный, то после просмотра всех ребер будет сформировано покрывающее дерево и один букет, содержащий все вершины графа. Если граф несвязный, то после просмотра всех ребер будет сформирован покрывающий лес из k деревьев и k букетов, где k — количество связных компонент в графе. Алгоритм Краскала. 1. Начальная установка. Лес не содержит ни одного ребра и ни один из букетов не сформирован. 2. Выбрать любое ребро, включить его в лес и сформировать букет, включив в него концевые вершины выбранного ребра. 3. Пока в графе есть необработанные ребра, выполнять п. 4. Выбрать необработанное ребро. После этого выбора возможны четыре различных случая А. Обе концевые вершины выбранного ребра принадлежат одному и тому же букету. В этом случае ребро не включается в лес. Б. Одна из концевых вершин выбранного ребра принадлежит некоторому букету, а другая концевая вершина не принадлежит ни одному из уже сформированных букетов. В этом случае выбранное ребро включается в лес и его концевая вершина, не принадлежащая ранее ни одному букету, включается в букет, которому принадлежит другая концевая вершина рассматриваемого ребра. В. Ни одна из концевых вершин не принадлежит ни одному из сформированных букетов. В этом случае выбранное ребро включается в лес и формируется новый букет из его концевых вершин. Г. Концевые вершины выбранного ребра принадлежат различным букетам. В этом случае выбранное ребро включается в леса оба букета, которым принадлежат его концевые вершины, объединяются в один новый букет и количество букетов при этом уменьшается. Не нарушая понятия букета, можно упростить алгоритм Краскала, если при начальной установке сформировать n букетов по одной вершине в каждом (n — количество вершин в графе. В этом случаев п после выбора очередного ребра возможны только два случая — Аи Г . При программной реализации алгоритма Краскала для хранения букетов целесообразно использовать массив В натуральных чисел, в котором количество элементов равно количеству вершин в графе. Индекс i элемента массива B i соответствует й вершине графа, а значение B i — номеру букета, которому принадлежит я вершина. Если i и j — концевые вершины ребра, то для распознавания случая А или Г пункта 4 алгоритма, достаточно сравнить на равенство значения элементов B i и Для объединения букетов B i и B j необходимо просмотреть все элементы массива В и значения, равные B j , заменить на B i . При этом количество букетов уменьшится. Рассмотрим работу упрощенного алгоритма Краскала на примере графа (рис. Процесс работы алгоритма представим в табл. 4.3. 1 2 3 4 6 5 Рис. Диаграмма графа Таблица 4.3 Работа алгоритма Краскала Шаг Ребро Решение Массив В Примечание 1 2 3 4 5 6 1 1 2 3 4 5 6 Начальная установка 2 {1,2} Включать в лес 1 1 3 4 5 6 На шаге 1 B 1 B 2 3 {1,4} Включать в лес 1 1 3 1 5 6 На шаге 2 B 1 B 4 4 {2,3} Включать в лес 1 1 1 1 5 6 На шаге 3 B 2 B 3 5 {2,4} Не включать На шаге 4 B 2 = B 4 6 {3,4} Не включать На шаге 5 B 3 = B 4 7 {3,5} Включать в лес 1 1 1 1 1 6 На шаге 6 B 3 B 6 8 {3,6} Включать в лес 1 1 1 1 1 1 Дерево построено 9 {5,6} Не включать На шаге 8 B 5 = B 6 10 {6,1} Не включать На шаге 9 B 6 = B 1 176 Связный граф может иметь несколько покрывающих деревьев. Количество всех различных покрывающих деревьев равно определителю матрицы |B B t |, где B — матрица инцидентности с одной удаленной строкой, B t — транспонированная матрица к B. Рассмотрим алгоритм, позволяющий найти все покрывающие деревья. Пусть задан связный граф, содержащий n вершин и m ребер. Покрывающее дерево содержит k = n – 1 ребери представляет собой элементное подмножество элементного множества ребер, те. сочетание из m по k. Ноне каждое сочетание из m по k представляет собой покрывающее дерево. Поэтому для получения всех покрывающих деревьев можно использовать алгоритм 2.5 порождения сочетаний и, когда сочетание получено, нужно проверить, является ли полученное сочетание деревом или циклическим графом. Для того, чтобы порождать только те сочетания, которые являются покрывающими деревьями, выполним следующие действия 1. Выберем произвольную вершину v. 2. Ребрам, инцидентным вершине v, припишем номера 1, 2, …, Га остальным — Г + 1, Г + 2, …, m. 3. Покрывающее дерево будем представлять последовательностью T ребер в возрастающем порядке. 4. На первое место последовательности ставить только ребра, инцидентные вершине v. 5. Очередное е место последовательности T заполняется по алгоритму. Алгоритм 4.8 формирования всех покрывающих деревьев в графе G. Вход i — заполняемое место в последовательности T; b — минимальный элемент, который можно поставить на е место последовательности T. Выход последовательность всех покрывающих деревьев. Глобальные параметры T — формируемая последовательность ребер m — количество ребер в графе G; k — количество ребер в покрывающем дереве. Алгоритм 4.8 формирования всех покрывающих деревьев представлен блок-схемой на рис. В этом алгоритме в цикле перебираются ребра с большим номером, чем ребра, включенные в частично сформированное дерево, и такие, добавление которых к частично сформированному дереву не образует цикл. Для определения, образует ли ребро с ранее включенными в дерево ребрами цикл, можно использовать понятие букет аналогично тому, как это делалось в алгоритме Краскала. 177 + Рис. Рекурсивный алгоритм формирования всех покрывающих деревьев Процесс формирования всех покрывающих деревьев графа, диаграмма которого дана на рис, представлен в виде дерева на рис. Вершины дерева соответствуют ребрам графа, а ветвь от корня до листа содержит ребра покрывающего дерева. Диаграммы покрывающих деревьев изображены на рис. 2 1 4 3 5 Рис. Диаграмма графа 1 2 3 2 3 4 3 4 4 3 5 4 5 5 4 5 5 Рис. Процесс формирования всех покрывающих деревьев Дерево (i, b) x|x {b..m–k+i} и дерево T i := x i=k Конец Дерево (i+1, x+1) T |