Дискретная математика (стр. 9 )

Утверждение: в орпсевдографе из всякого контура можно выделить простой. Доказательство аналогично доказательству для псевдографов.

Утверждение: из всякого незамкнутого пути в орпсевдографе можно выделить простой путь с теми же концевыми вершинами. Доказательство аналогично доказательству для псевдографов.

Матрица смежности орграфов

В теории графов квадратные матрицы смежности орграфов размера nn обозначаются буквой A как и для графов. Элемент A(j, k) матрицы смежности орграфа равен единице, если существует дуга из вершины j в вершину k и равен нулю в противном случае. Пример орграфа и его матрицы смежности: в

из

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

У каждой дуги орграфа, исходящей из вершины j в вершину k, в матрице смежности орграфа имеется соответствующая ей единица: A(j, k) = 1. Полустепень исхода j-й вершины графа равна сумме элементов его матрицы смежности A по j-й строке, а полустепень захода j-й вершины графа равна сумме элементов его матрицы смежности A по j-у столбцу. Отсюда сток в графе имеет соответствующую ему нулевую строку в матрице смежности, а исток - соответствующий ему нулевой столбец в матрице смежности орграфа. Сумма элементов матрицы смежности орграфа равна числу дуг в нём.

Матрица смежности существует и для ормультиграфов, только она в общем случае не будет булевой. Её элементы будут равны кратности соответствующих им дуг. Пример ормультиграфа и его матрицы смежности: в

из

Висячая вершина орграфа может быть либо стоком, либо истоком. Висячая вершина – сток имеет соответствующую ей нулевую строку и ровно одну единицу в соответствующем ей столбце. Висячая вершина – исток имеет соответствующий ей нулевой столбец и ровно одну единицу в соответствующей ей строке.

Полустепени исхода и захода ормультиграфа определяются по его матрице смежности так же, как и для орграфа.

Утверждение: элемент A(j, k) t-й степени матрицы смежности A (A) орграфа равен числу всех путей длины t из вершины j в вершину k. Без доказательства. Следствием является утверждение: для того, чтобы n – вершинный орграф с матрицей смежности A имел хотя бы один контур, необходимо и достаточно, чтобы матрица K = A + A + … + A имела не нулевые диагональные элементы. Без доказательства.

Матрица A будет иметь не нулевую главную диагональ, если в орграфе есть контур длины два (симметричная пара дуг), матрица A будет иметь не нулевую главную диагональ, если в орграфе есть контур длины три, … , матрица A будет иметь не нулевую главную диагональ, если в орграфе есть контур длины n.

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

Связность орграфов

Орграф называется сильно связным, если для каждой пары его вершин существуют пути в обе стороны, их соединяющие. Другими словами, каждая пара вершин сильно связного орграфа входит в контур. Пример сильно связного орграфа на трёх вершинах:

Орграф называется односторонне связным, если для каждой пары его вершин существует соединяющий их путь по крайней мере в одну сторону. Пример односторонне связного орграфа на трёх вершинах:

Если в орграфе дуги заменить рёбрами, то получим ассоциированный с орграфом граф. Орграф называется слабо связным, если ассоциированный с ним граф является связным. Пример слабо связного орграфа (слева) и его связного ассоциированного с ним орграфа (справа) на трёх вершинах:

Если орграф не является ни сильно связным, ни односторонне связным, ни слабо связным, то он является не связным.

Компонентой сильной связности орграфа называется его сильно связный орподграф, не являющийся собственным орподграфом никакого другого сильно связного орподграфа орграфа. Число компонент сильной связности у орграфа тоже обозначается переменной p.

Пусть орпсевдограф D(V, X) имеет p компонент сильной связности: D1(V1,X1), D2(V2,X2), …, Dp(Vp, Xp). Тогда из определения компоненты сильной связности следует:

1) множество вершин орграфа D – это объединение множеств вершин его компонент сильной связности: V = V1V2…Vp, а множество дуг орграфа D – это подмножество объединения множеств дуг его компонент сильной связности: X X1X2…Xp;

2) любые две различные компоненты сильной связности орграфа не имеют общих вершин и общих дуг: VjVk = и XjXk = при jk;

3) число вершин орграфа равно сумме чисел вершин его компонент сильной связности: n = n1 + n2 + … +np, а число дуг орграфа больше или равно сумме чисел дуг его компонент связности: m m1 + m2 + … + mp.

Пример орграфа с двумя компонентами сильной связности, причем дуга из вершины а в вершину б не входит ни в одну из компонент:

В полном орграфе могут быть сток, или исток, или и сток и исток, а могут и не быть. В сток можно попасть по дуге из любой вершины полного орграфа или турнира, а из истока можно попасть по дуге в любую вершину полного орграфа или турнира. Контуры в орграфе можно определять как вручную по рисунку орграфа, так и по матрице смежности A орграфа. При n=4 для определения контуров орграфа надо получить его матрицу смежности, её квадрат, куб и четвёртую степень.

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

Одна вершина орграфа достижима из другой вершины, если существует орцепь (в том числе и длиной единица – дуга) из этой другой вершины в достижимую из неё вершину. Считается, что сама вершина достижима из самой себя, как бы путь длиной ноль. Матрицей достижимости T орграфа называется квадратная матрица порядка n, в которой каждый элемент T=1, если j-я вершина достижима из i-й вершины, и T=0 в противном случае. Матрица достижимости T орграфа всегда имеет единичную главную диагональ.

Матрицу достижимости можно получить как вручную из рисунка орграфа, так и из его матрицы смежности A орграфа по формуле: T=Esign(AA…A), где E – единичная квадратная матрица порядка n.

Изложенный выше алгоритм Уоршелла работает и для орграфов. Используя его, можно получить матрицу достижимости T орграфа.

Матрицей сильной связности S орграфа называется квадратная матрица порядка n, в которой каждый элемент S=1, если j-я вершина достижима из i-й вершины и, наоборот, i-я вершина достижима из j-й вершины, и S=0 в противном случае. Матрицу сильной связности можно получить как вручную из рисунка орграфа, так их из матрицы достижимости T орграфа по формуле: S=TT, где - это поэлементная операция «and», а T означает операцию транспонирования матрицы T, когда строки матрицы становятся её столбцами и наоборот.

Изложенный выше для графов алгоритм получения компонент связности из матрицы связности графа работает и для орграфов. Этот алгоритм выделяет компоненты сильной связности орграфа по его матрице сильной связности.

Глава 12. Маршруты в графах и пути в орграфах

Эйлеровы цепи и циклы

Цепь в псевдографе называется эйлеровой, если она проходит по одному разу через каждое ребро. Цикл в псевдографе называется эйлеровым, если он проходит по одному разу через каждое ребро. Граф с эйлеровым циклом называется эйлеровым. В эйлеровом графе существуют и несколько эйлеровых цепей, так как эйлеров цикл можно разбить и на эйлеровы цепи. Граф с эйлеровой цепью, но без эйлерова цикла, называется полуэйлеровым. В полуэйлеровом графе может быть и несколько эйлеровых цепей. Все остальные графы называются не эйлеровыми. Пример эйлерова графа (слева), полуэ йлерова графа (в середине) и не эйлерова графа:

Теорема: Связный граф будет эйлеровым, если все вершины в нём имеют чётную степень. Доказательство: берём любую вершину и выходим из неё по любому её ребру, которых у неё как минимум два. В следующей вершине выходим по новому ребру. И так до тех пор, пока новых рёбер, по которым можно выйти из вершины, не останется. Этот маршрут может закончиться только в начальной вершине маршрута, так как все степени у вершин чётные и, если мы вошли в не начальную вершину маршрута, то и выйдем из неё по новому ребру.

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

Строим подцикл из новых рёбер из вершины полученного цикла, в которой остались ещё эти новые рёбра. И так до тех пор, пока все рёбра графа не войдут в его эйлеров цикл. Теорема доказана.

Теорема: Связный граф будет полуэйлеровым, если он имеет ровно две вершины нечётной степени. Доказательство: соединяем эти две вершины нечётной степени помеченным дополнительным ребром и тогда граф становится эйлеровым, так как все вершины в нём имеют теперь чётную степень. Строим эйлеров цикл, удаляем из этого цикла помеченное ребро и получаем эйлерову цепь. Теорема доказана. Эйлерова цепь в полуэйлеровом графе начинается и заканчивается в вершинах нечётной степени.

Сумма элементов матрицы смежности A графа равна 2m – удвоенному числу рёбер в графе. По матрице смежности A графа можно проверять условия существования эйлеровых цепей и циклов в графах.

Эйлеровы цепи и циклы можно строить по рисунку графа и его по матрице смежности A. Возьмём, например, матрицу смежности A=. Степени всех трёх вершин чётны – равны двум. В графе с такой матрицей смежности существует эйлеров цикл. Берём любой не нулевой элемент матрицы, например A, и уменьшаем его и симметричный ему элемент A на единицу, так как в матрице смежности графа у каждого ребра имеется ровно две единицы. Матрица принимает после этого вид: , а в эйлеровом цикле теперь две вершины: 1 и 2, и находимся мы во второй вершине. Находим во второй строке не нулевой элемент – это A, и повторяем процедуру. Матрица принимает вид: , а в эйлеровом цикле теперь три вершины: 1, 2 и 3, и находимся мы в третьей вершине. Находим в третьей строке не нулевой элемент – это A, и повторяем процедуру. После чего матрица обнуляется полностью, а мы получаем эйлеров цикл: 1, 2, 3, 1.

При построении эйлеровой цепи в качестве начальной вершины надо брать вершину с нечётной степенью. Возьмём, например, матрицу смежности A=. В графе с такой матрицей смежности ровно две вершины нечётной степени – это первая и третья, и это полуэйлеров граф. В качестве начальной вершины берём любую из двух, например, третью. Находим в третьей строке не нулевой элемент и обнуляем его и симметричный ему относительно главной диагонали элемент. Матрица принимает вид: и в эйлеровой цепи теперь две вершины: 3 и 2. Повторяем процедуру для второй строки, после чего матрица полностью обнуляется, а мы получаем эйлерову цепь: 3, 2 и 1.

Эйлеровыми могут быть и псевдографы. Возьмём, например, матрицу смежности A=. Степени всех трёх вершин чётны. Начнём строить эйлеров цикл с первой вершины и через четыре шага построения получим матрицу и пять вершин в эйлеровом цикле: 1, 2, 1, 3, 1. Матрица ещё не обнулилась, а в первой строке, где мы находимся, уже нет не нулевых элементов. Находим строку с не нулевыми элементами и строим из соответствующей этой строке вершины маршрут, который затем вставим в эйлеров цикл: 2, 3, 3, 2. Находясь в третьей вершине, мы прошли петлю. Итого, эйлеров цикл имеет вид: 1, 2, 3, 3, 2, 1, 3, 1 и встроенный маршрут выделен в нём жирным шрифтом.

Сильно связный орграф будет эйлеровым, если в нём для каждой вершины полустепень исхода равна полустепени захода. Сильно связный орграф будет полуэйлеровым, если в нём для всех вершин, кроме двух, полустепень исхода равна полустепени захода, в одной из двух оставшихся вершин есть одна лишняя исходящая дуга, а в другой – одна лишняя заходящая дуга.

Эйлеровы цепи и циклы можно строить по рисунку орграфа и его по матрице смежности A. Возьмём, например, матрицу смежности A=. Для всех трёх вершин полустепени исхода совпадают с полустепенями захода. В орграфе с такой матрицей смежности существует эйлеров цикл. Берём любой не нулевой элемент матрицы, например A, и уменьшаем его на единицу. Матрица принимает после этого вид: , а в эйлеровом цикле теперь две вершины: 1 и 2, и находимся мы во второй вершине. Находим во второй строке не нулевой элемент – это A, и повторяем процедуру. Матрица принимает вид: , а в эйлеровом цикле теперь три вершины: 1, 2 и 3, и находимся мы в третьей вершине. Находим в третьей строке не нулевой элемент – это A, и повторяем процедуру. После чего матрица обнуляется полностью, а мы получаем эйлеров цикл: 1, 2, 3, 1.

Эйлерову цепь в орграфе надо начинать строить из вершины, имеющей лишнюю выходящую дугу.

Гамильтоновы цепи и циклы

Цепь в псевдографе называется гамильтоновой, если она проходит по одному разу через каждую вершину. Цикл в псевдографе называется гамильтоновым, если он проходит по одному разу через каждую вершину. Граф с гамильтоновым циклом называется гамильтоновым. В гамильтоновом графе существуют несколько гамильтоновых цепей, так как из гамильтонова цикла можно получить n гамильтоновых цепей. Граф с гамильтоновой цепью, но без гамильтонова цикла, называется полугамильтоновым. В полугамильтоновом графе может быть несколько гамильтоновых цепей. Все остальные графы называются не гамильтоновыми.

Пример гамильтонова графа (слева), полугамильтонова графа (в середине) и не гамильтонова графа (справа):

Графы могут быть эйлеровыми (1-я строка) и не эйлеровыми (2-я стр.), гамильтоновыми (1-й столбец) и не гамильтоновыми (2-й столбец):

Для нахождения всех гамильтоновых цепей и циклов можно использовать метод, аналогичный методу ветвей и границ. Возьмём граф с матрицей смежности: . Дерево ветвления строим, например, из первой вершины.

Гам. цикл 1

5 Х

-6 Х

-1 Гам. цикл 2

--3 Гам. цепь

-4 Гам. цепь

--1 Гам. цикл 2

-3 Гам. цепь

Гам. цикл 3

Гам. цикл 1

6-----4 Гам. цепь

--1 Гам. цикл 3

--2 Х

Дерево ветвления строим так, чтобы на каждой его ветви были только уникальные вершины, за исключением конечной седьмой, совпадающей с начальной, первой вершиной, с целью обозначить гамильтонов цикл в графе. Корень (здесь первая вершина)– это нулевой уровень. Из первой вершины есть выход во вторую, шестую и пятую. Первый уровень состоит из этих трёх вершин. Из второй есть выход в 1, 3 и 5, но в первой мы уже были, остаются только 3 и 5. Аналогично, из 6 – в 3 и 4, а из 5 – в 4 и 2. Второй уровень состоит из 6 вершин: 3, 5, 3, 4, 2, 4. и так далее.

Получили три гамильтоновых цикла, каждый цикл получили два раза: в одну сторону и в другую. Если будем строить дерево из другой вершины, например пятой, то получим те же три гамильтоновых цикла. Получили 4 гамильтоновых цепи из первой вершины, две из них кончаются в третьей вершине, а две – в четвёртой. Если будем строить гамильтоновы цепи из третьей вершины, то получим две такие цепи, кончающиеся в первой вершине. Если из третьей вершины будут ещё получены гамильтоновы цепи, то они обязательно закончатся не в первой вершине.

Получили три «безнадёжных» ветви, они помечены буквой «Х». Все они имеют длину пять и из последней пятой вершины есть выходы только в уже пройденные этой веткой вершины.

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

В полном графе с более чем двумя вершинами гамильтонов цикл всегда существует. Если в графе существует точка сочленения, то гамильтонова цикла в нём нет, так как точку сочленения при обходе вершин графа придётся пройти не менее двух раз, а это уже не простой цикл. Для нахождения всех гамильтоновых цепей и циклов в связном графе можно использовать метод прямого перебора. Надо перебрать все n! перестановок из n вершин и выбрать перестановки, которые соответствуют реальным маршрутам в графе.

Теорема Дирака: если n >2 и для каждой вершины её степень больше числа (n/2-1), то граф гамильтонов. Ясно, что если граф имеет достаточное число рёбер (в пределе полный граф), то он гамильтонов. Доказательство: Добавим к графу G k новых вершин, соединив каждую из них с каждой вершиной из графа G. Пусть число k – это минимальное число вершин, которое надо добавить к графу G, чтобы новый граф G` стал гамильтоновым. Затем придём к противоречию, считая, что k>0.

Пусть v – p – w - … - v гамильтонов цикл в графе G`, где v и w – старые вершины из графа G, а p – новая вершина из k новых вершин. Тогда w не смежна с v, так как в противном случае мы могли бы не использовать новую вершину p, что противоречит минимальности k. Более того, вершина w`, смежная с w, не может в гамильтоновом цикле следовать непосредственно за вершиной v`, смежной с v, так как можно было бы заменить гамильтонов цикл v – p – w - … - v` - w` - … - v на гамильтонов цикл v – v` - … - w – w` - … - v, перевернув часть цикла между w и v`. И опять вершина p была бы не нужна.

Каждая вершина v`, смежная с v, должна в цикле предшествовать не смежным с w вершинам. Отсюда число вершин графа G`, не смежных с w, не меньше числа вершин, смежных с v. Смежных вершин у каждой вершины графа G` (у вершин v и w тоже) не менее (n/2 + k). Значит, и число вершин G`, не смежных w, тоже не менее (n/2 + k). Получили, что число вершин G`, равное (n + k), не менее чем число (n+2k), так как все вершины G` делятся на смежные и не смежные с вершиной w (как и с любой другой вершиной). Получили противоречие.

Каждая не смежная пара вершин при такой минимальной степени вершин (n/2) имеет как минимум одну общую смежную с ними вершину и, значит, соединена друг с другом маршрутом длины два.

У не гамильтонова графа может быть так называемый фактор. Это когда все вершины графа разделяются между несколькими простыми циклами. Например, у графа Петерсена нет гамильтонова цикла, но есть фактор из двух циклов длины пять:

Метод латинской композиции

Маршрут в графе называется латинским со свойством , или – латинским маршрутом, если любой его подмаршрут длины, большей единицы, тоже обладает этим свойством. Свойство тоже называется латинским.

Латинские свойства маршрутов в графе:

·  не проходить через заданную вершину (множество вершин);

·  не проходить через данное ребро;

·  быть простой цепью;

·  быть цепью;

·  не проходить через данную вершину более k раз.

Всё вышеперечисленное используется и в орграфах. Матричный (вернее тензорный) способ перечисления - латинских путей в графе и в орграфе называется методом латинской композиции. Тензором называется матрица, элементами которой могут быть переменные, векторы, матрицы, символы и текстовые строки и даже другие тензоры.

Рассмотрим метод латинской композиции на примере. Надо найти все простые цепи длины три в орграфе:

Свойство здесь – это «быть простой цепью». Тензор L1 содержит простые цепи длины один, то есть дуги. Тензор L2 содержит простые цепи длины два. Тензор L2 получается из тензора L1 возведением его в квадрат. Тензор L3 содержит простые цепи длины три. Тензор L3 получается умножением тензоров L1 и L2 друг на друга:

При возведении тензора L1 в квадрат получаются и простые контуры длиной два (симметричная пара дуг). Например, получаются два контура:иЭти контуры не заносятся в тензор L2. В L2 заносятся только простые цепи длиной два:

При умножении тензоров L1 и L2 друг на друга для получения тензора L3 получаются и простые контуры длиной три. Например, получаются контуры,иЭти контуры не заносятся в тензор L3. В L3 заносятся только простые цепи длиной три: