ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
4.3. Изоморфизм графов Два графа G 1 = (V 1 ,E 1 ) и G 2 = (V 2 ,E 2 ) называются изоморфными, если существует взаимнооднозначное соответствие p : V 1 → V 2 между вершинами графов, сохраняющее смежность, те. если вершины v i и смежны в графе G 1 , то вершины и p(v j ) смежны в графе G 2 , если же вершины v i и v j не смежны в графе G 1 , то вершины и p(v j ) не смежны в графе Изоморфные графы можно изобразить диаграммами (рис, которые различаются только обозначениями вершин. 1 2 2 1 3 4 3 4 Рис. Диаграммы изоморфных графов Взаимнооднозначное соответствие между вершинами графов G 1 =(V 1 ,E 1 ) и G 2 =(V 2 ,E 2 ) можно задать вектором p, в котором номер элемента представляет собой вершину графа G 1 , а его значение — соответствующую вершину графа G 2 . Вектор p можно рассматривать как перестановку множества V 2 . Если одна из перестановок определяет соответствие, сохраняющее смежность, то графы G 1 и G 2 изоморфны. Пусть граф G 1 задан матрицей A, аграф матрицей B. Соответствие p сохраняет смежность в том случае, если A i,j = B Pi,Pj для всех элементов. Таким образом для определения изоморфизма графов можно использовать алгоритм порождения перестановок, в котором для каждой порождаемой перестановки проверяется условие определяет ли она соответствие между вершинами графов, сохраняющее смежность. 4.4. Маршруты Маршрутом в графе называется чередующаяся последовательность вершин и ребер, начинающаяся и кончающаяся вершиной, в которой любые два соседних элемента инцидентны, причем однородные элементы (вершины, ребра) через один смежны или совпадают. Очевидно, маршрут может быть задан только последовательностью вершин (или ребер. Произвольная последовательность вершин является маршрутом только тогда, когда каждая пара соседних вершин представляет собой пару смежных вершин. Длина маршрута определяется количеством ребер в нем. Маршрут длины l может быть задан последовательностью из l + вершины. Получить все маршруты W длины l в графе G, начинающиеся вершиной можно, используя метод поиска с возвращением. Сначала на первое место маршрута W поставим вершину v. Затем, начиная со второго элемента, последовательно формируем элементы маршрута. Формирование го элемента маршрута опишем рекурсивным алгоритмом 4.1, блок-схема которого представлена на рис. В цикле перебираются вершины, смежные вершине, стоящей нам месте в маршруте W, те. элементы множества Г, которые можно поставить на е место. Если заполнено последнее, l + 1-еместо, то маршрут получен и выводим его, иначе заполняем следующее i + е место по алгоритму. Алгоритм 4.1 получения всех маршрутов W длины l в графе G, начинающихся вершиной v. Вход i — заполняемое место в маршруте W. Выход последовательность всех маршрутов W длины l в графе G, начинающиеся вершиной v. Глобальные параметры W — формируемый маршрут l — длина маршрута. 158 + Рис. Рекурсивный алгоритм получения всех маршрутов W длины l в графе G, начинающихся вершиной Для определения количества маршрутов длины l между каждой парой вершин графа можно использовать алгоритм 4.1: 1. Обнулить все элементы матрицы R порядка n n, где n — количество вершин в графе. 2. v := 1. 3. Пока v n выполнять пп.4, 5. 4. Получить все маршруты W длины l в графе G, начинающиеся вершиной v, используя алгоритм 4.1. После получения очередного маршрута увеличить на единицу элемент матрицы R v,u , где u = W l+1 5. v := v + 1. 6. Элемент R i,j содержит количество маршрутов длины l между вершинами и j. Если граф G задан матрицей смежности A, то R = A l , те. для определения количества маршрутов длины l между каждой парой вершин графа достаточно матрицу смежности A возвестив ю степень. Маршрут, в котором все ребра различны, называется цепью. Цепь, также как и маршрут, может быть задана последовательностью вершин. Пусть задана последовательность вершин и требуется определить, является ли она цепью в заданном графе. Для этого будем использовать множество E' (в исходном состоянии оно пустое) ребер. Последователь- Маршруты (i) Г := x Конец Маршруты (i+1) W 159 но перебирая пары соседних вершин в заданной последовательности, проверяем условие, являются ли эти вершины смежными и принадлежит ли ребро, образованное этими вершинами множеству E’, и, если вершины смежны и ребро, образованное ими, не принадлежит множеству, то ребро включаем в множество E’ и переходим к следующей паре вершин. Если жена некотором шаге обнаруживаем, что вершины не смежны или ребро, образованное ими, принадлежит множеству E’, то заданная последовательность вершин не является цепью в заданном графе. Получить все цепи W длины l в графе G, начинающиеся вершиной v можно, используя метод поиска с возвращением. Сначала на первое место цепи W поставим вершину v. Множество ребер E', включенных в цепь,пусто.Затем, начиная со второго элемента, последовательно формируем элементы цепи. Формирование го элемента цепи опишем рекурсивным алгоритмом 4.2, блок-схема которого представлена на рис. В цикле перебираются вершины, смежные вершине, стоящей нам месте вцепи и не образующие с ней ребро, принадлежащее множеству E’, те. элементы множества Г – {y | {W i-1 ,y} E’}, которые можно поставить на е место. Если заполнено последнее, l + е место, то цепь получена и выводим ее, иначе заполняем следующее i + е место по алгоритму 4.2 с учетом последнего включенного в цепь ребра. Алгоритм 4.2 получения всех цепей W длины l в графе G, начинающихся вершиной v. Вход i — заполняемое место вцепи множество ребер, включенных в цепь. Выход последовательность всех цепей W в графе G, начинающихся вершиной v. Глобальные параметры W — формируемая цепь l — длина цепи. Маршрут, в котором все вершины (а значит, и ребра) различны, называется простой цепью. Пусть задана последовательность вершин и требуется определить, является ли она простой цепью в заданном графе. Для этого будем использовать множество V’ вершин (в исходном состоянии оно содержит только первую вершину заданной последовательности. Последовательно перебирая пары соседних вершин в заданной последовательности, проверяем условие, являются ли эти вершины смежными и принадлежит ли вторая вершина пары множеству V’, и, если вершины смежны и вторая вершина пары не принадлежит множеству, то вторую вершина пары включаем в множество V’ и переходим к следующей паре вершин. Если жена некотором шаге обнаруживаем, что вершины не смежны или вторая вершина пары принадлежит множеству, то заданная последовательность вершин не является простой цепью в заданном графе. + Рис. Рекурсивный алгоритм получения всех цепей W длины l в графе G, начинающихся вершиной v Получить все простые цепи W длины l в графе G, начинающиеся вершиной v можно, используя метод поиска с возвращением. Сначала на первое место цепи W поставим вершину v и запомним ее в множестве V’. Затем, начиная со второго элемента, последовательно формируем элементы цепи. Формирование го элемента цепи опишем рекурсивным алгоритмом 4.3, блок-схема которого представлена на рис. В цикле перебираются вершины, смежные вершине, стоящей нам месте вцепи за исключением тех, которые уже включены в цепь, те. элементы множества Г – V’, которые можно поставить на е место. Если заполнено последнее, l + 1-еместо, то простая цепь длины l получена и выводим ее, иначе заполняем следующее I + е место по алгоритму 4.3 с учетом последней включенной в цепь вершины. Алгоритм 4.3 получения всех простых цепей W длины l в графе G, начинающихся вершиной v. Вход i— заполняемое место вцепи множество вершин, включенных в цепь. Цепи) Г := x i=l+1 Конец Цепи, E ’ { W i-1 , x} ) W 161 Выход последовательность всех простых цепей W длины l в графе, начинающихся вершиной v. Глобальные параметры W — формируемая простая цепь l — длина цепи. + Рис. Рекурсивный алгоритм получения всех простых цепей длины l в графе G, начинающихся вершиной v Простая цепь, начинающаяся вершиной v, называется максимальной простой цепью, если она не является частью никакой другой простой цепи, начинающейся вершиной v. Пусть задана последовательность вершин и требуется определить, является ли она максимальной простой цепью в заданном графе. Последовательность вершин будет максимальной простой цепью, если она является простой цепью и все вершины, смежные с последней вершиной последовательности, содержатся в этой последовательности. Это означает, что в максимальную простую цепь нельзя добавить ни одной вершины так, чтобы последовательность оставалась простой цепью. Получить все максимальные простые цепи W в графе G, начинающиеся вершиной можно, используя метод поиска с возвращением. Сначала на первое место цепи W поставим вершину v и запомним ее в множестве V’. Затем, начиная со второго элемента, последовательно формируем элементы цепи. Формирование го элемента цепи опишем рекурсивным алгоритмом 4.4, блок-схема которого представлена на Цепи (i,V’) Г := x Конец Цепи (i+1, V’ {x} ) W 162 рис. В цикле перебираются вершины, смежные вершине, стоящей нам месте вцепи за исключением тех, которые уже включены в цепь, те. элементы множества Г — V’, которые можно поставить на е место. Если все вершины, смежные вершине, установленной на е место, уже находятся вцепи, то максимальная простая цепь получена и выводим ее, иначе заполняем следующее i + е место по алгоритму 4.4 с учетом последней включенной в цепь вершины. Алгоритм 4.4 получения всех максимальных простых цепей W в графе G, начинающихся вершиной v. Вход i — заполняемое место вцепи множество вершин, включенных в цепь. Выход последовательность всех максимальных простых цепей W в графе G, начинающихся вершиной v. Глобальные параметры W — формируемая максимальная простая цепь, начинающаяся вершиной v. + Рис. Рекурсивный алгоритм получения всех максимальных простых цепей W в графе G, начинающихся вершиной v Цепи (i,V’) Г := x Г Конец Цепи (i+1, V’ {x} ) W 163 4.5. Метрические характеристики графа Пусть v 1 и v 2 — две вершины графа G = (V,E). Длина кратчайшего маршрута, соединяющего вершины v 1 и v 2 называется расстоянием между вершинами v 1 и v 2 , обозначается через d(v 1 ,v 2 ). Для любой вершины величина называется эксцентриситетом вершины v. Максимальный из всех эксцентриситетов вершин называется диаметром графа и обозначается d(G). Минимальный из всех эксцентриситетов вершин называется радиусом графа и обозначается r(G). Вершина v называется периферийной, если ее эксцентриситет равен диаметру графа, те. e(v) = d(G). Простая цепь, в которой расстояние между концевыми вершинами равно диаметру графа, называется диаметральной цепью. Вершина v называется центральной, если ее эксцентриситет равен радиусу графа, те. e(v) = r(G). Множество всех центральных вершин графа называется его центром. Рассмотрим граф, диаграмма которого представлена на рис. 1 5 6 7 2 3 4 Рис. Диаграмма графа Эксцентриситеты вершин этого графа представлены в табл. 4.1. Таблица 4.1 Эксцентриситеты вершин графа Вершина 1 2 3 4 5 6 7 Эксцентриситет 3 3 4 3 2 3 4 Диаметр этого графа равен 4, радиус равен 2. Периферийные вершины и 7, диаметральные цепи (3,2,5,6,7) и (3,4,5,6,7), центральная вершина 5. 164 4.6. Циклы Циклом в графе называется цепь, в которой начальная и конечная вершины совпадают (замкнутая цепь. Простая замкнутая цепь называется простым циклом. В простом цикле никакая вершина, за исключением начальной, не встречается более одного раза. Простой цикл не содержит внутри себя других циклов. Граф, содержащий в себе хотя бы один цикл, называется циклическим, в противном случае — ациклическим. Циклический граф может иметь несколько простых циклов с заданной начальной вершиной. Алгоритм 4.5 получения всех простых циклов W в графе G, начинающихся вершиной v, отличается от алгоритма только условием получения решения. Простой цикл получен, если на очередное е место поставлена вершина v (в исходном состоянии вершина v в множество V’ не включается. Блок-схема алгоритма 4.5 представлена на рис. Алгоритм 4.5 получения всех простых циклов W в графе G, начинающихся вершиной v. Вход i — заполняемое место в цикле W; V’ — множество вершин, включенных в цикл. Выход последовательность всех простых циклов W в графе G, начинающихся вершиной v. Глобальные параметры W — формируемый цикл v — исходная вершина. + Рис. Рекурсивный алгоритм получения всех простых циклов W в графе, начинающихся вершиной v Циклы (i,V’) Г := x x=v и Конец Циклы (i+1, V’ {x} ) W 165 Если граф имеет простой цикл, содержащий все вершины графа (по одному разу, то такой цикл называется гамильтоновым циклом, аграф гамильтоновым графом. Вопрос о принадлежности графов к классу гамильтоновых решается, как правило, очень трудно. Известны лишь достаточные условия гамильтоновости графов, например, теорема Оре: если для любой пары x и y несмежных вершин графа G порядка n 3 выполняется условие d(x) + d(y) n , то G — гамильтонов графили теорема Дирака : если для любой вершины x графа G порядка n 3 выполняется условие d(x) n/2 , то G — гамильтонов граф. Убедиться в том, что граф гамильтонов можно, например, отыскав в нем один из гамильтоновых циклов, используя методпоиска с возвращением. На рис представлена блок-схема рекурсивного алгоритма 4.6 нахождения всех гамильтоновых циклов графа. Этот алгоритм отличается от алгоритма 4.5 нахождения всех простых циклов только условием получения решения, так как гамильтонов цикл — это простой цикл, содержащий все вершины графа. Алгоритм 4.6 получения всех гамильтоновых циклов W в графе G. Вход i — заполняемое место в цикле W; V’ — множество вершин, включенных в цикл. Выход последовательность всех гамильтоновых циклов W в графе начинающихся вершиной v. Глобальные параметры W — формируемый цикл. + Рис. Рекурсивный алгоритм получения всех гамильтоновых циклов W в графе G Гамильтон (i,V’) Г := x x=v и Конец Гамильтон (i+1, V’ {x} ) W 166 Если граф имеет цикл (необязательно простой, содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, аграф эйлеровым графом. Эйлеров цикл содержит не только все ребра, но и все вершины графа (возможно, по несколько раз. Принадлежность графа классу эйлеровых легко устанавливается теоремой Эйлера связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны. Эйлеров цикл представляет собой замкнутую цепь, содержащую все ребра графа, поэтому можно получить все эйлеровы циклы используя алгоритм 4.2 получения всех цепей заданной длины, изменив в нем условие получения решения. Алгоритм 4.7 получения всех эйлеровых циклов представлен блок-схемой на рис. Алгоритм 4.7 получения всех эйлеровых циклов W в графе G. Вход i — заполняемое место в цикле W; E’ — множество ребер, включенных в цикл. Выход последовательность всех эйлеровых циклов W в графе G, начинающихся вершиной v. Глобальные параметры W — формируемый цикл v — исходная вершина. + Рис. Рекурсивный алгоритм получения всех эйлеровых циклов W в графе G, начинающихся вершиной v Эйлер (i,E’) Г := x x=v и Конец Эйлер (i+1,E ’ { W i-1 , x} ) W 167 В эйлеровом графе найти один из эйлеровых циклов можно следующим образом 1. Стек пуст. Множество отмеченных ребер пусто. Произвольную вершину v положить в стек. 2. Пока стек не пуст, выполнять п. 3. x := верхний элемент стека. Если все ребра, инцидентные вершине x, отмечены, то взять вершину из стека и поставить ее на очередное место цикла, иначе выбрать неотмеченное ребро {x,y}, отметить его и вершину y положить в стек. Процесс нахождения эйлерова цикла в эйлеровом графе, диаграмма которого изображена на рис, представлен в табл. 4.2. 3 1 5 2 4 6 Рис. Диаграмма эйлерова графа Таблица 4.2 Процесс нахождения эйлерова цикла Шаг Стек Отмеченные ребра Эйлеров цикл 1 1 2 1,4 {1,4} 3 1,4,2 {1,4},{4,2} 4 1,4,2,3 {1,4},{4,2},{2,3} 5 1,4,2,3,1 {1,4},{4,2},{2,3},{3,1} 6 1,4,2,3 {1,4},{4,2},{2,3},{3,1} 1 7 1,4,2 {1,4},{4,2},{2,3},{3,1} 1,3 8 1,4 {1,4},{4,2},{2,3},{3,1} 1,3,2 9 1,4,5 {1,4},{4,2},{2,3},{3,1},{4,5} 1,3,2 10 1,4,5,6 {1,4},{4,2},{2,3},{3,1},{4,5},{5,6} 1,3,2 11 1,4,5,6,4 {1,4},{4,2},{2,3},{3,1},{4,5},{5,6},{6,4} 1,3,2 12 1,4,5,6 {1,4},{4,2},{2,3},{3,1},{4,5},{5,6},{6,4} 1,3,2,4 13 1,4,5 {1,4},{4,2},{2,3},{3,1},{4,5},{5,6},{6,4} 1,3,2,4,6 14 1,4 {1,4},{4,2},{2,3},{3,1},{4,5},{5,6},{6,4} 1,3,2,4,6,5 15 1 {1,4},{4,2},{2,3},{3,1},{4,5},{5,6},{6,4} 1,3,2,4,6,5,4 16 {1,4},{4,2},{2,3},{3,1},{4,5},{5,6},{6,4} 1,3,2,4,6,5,4,1 |