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

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

Метод латинской композиции используется и для получения всех эйлеровых и гамильтоновых циклов и цепей графа. Свойство маршрутов: «проходить через каждое ребро не более одного раза» является латинским, и, значит, все эйлеровы циклы будут в диагональных элементах тензора Lm, а все эйлеровы цепи будет в не диагональных элементах тензора L(m-1).

Свойство маршрутов: «проходить через каждую вершину не более одного раза» является латинским, и, значит, все гамильтоновы циклы будут в диагональных элементах тензора Ln, а все гамильтоновы цепи будут в не диагональных элементах тензора L(n-1).

Минимальные маршруты и пути

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

В алгоритме используются поэтапно два вспомогательных квадратных размера n массива: массив p и массив s. Массив p хранит длины минимальных путей, а в массиве s запоминаются номера предпоследних вершин минимальных путей. Покажем на примере орграфа, как работает алгоритм:

Матрица смежности A орграфа и знаки её квадрата и куба:

Массивы p и s для трёх этапов нашего примера (поскольку простой путь максимальной длины в орграфе на четырёх вершинах равен трём) имеют вид:

Здесь точками заменены ещё не определённые на данном этапе элементы матриц p и s. В массиве s первого этапа (s1) предпоследней вершиной пути длиной единица (дуги) является начало дуги. В массиве s второго этапа (s2) предпоследней вершиной пути длиной два является промежуточная (средняя) вершина пути. В массиве s третьего этапа (s3) предпоследней вершиной пути длиной три является вторая, ближняя к концу пути промежуточная вершина.

Построим теперь минимальный путь из третьей вершины орграфа во вторую. По матрице p третьего этапа (p3) видно, что длина его равна трём, а по матрице s третьего этапа (s3) видно, что предпоследней вершиной этого минимального пути является первая вершина орграфа. Искомый путь принимает вид: – 1 – 2. По матрице p второго этапа (p2) видно, что длина минимального пути из третьей вершины в первую действительно равна двум, а по матрице s второго этапа (s2) видно, что предпоследней вершиной этого минимального пути является четвёртая вершина орграфа. Искомый минимальный путь имеет вид: 3 - 4 – 1 – 2.

Элементы матрицы s, начиная со второго этапа, определяются при получении степеней матрицы смежности A орграфа. Например, первую и четвёртую вершины графа не связывает дуга, но они связаны путём длины два. При возведении матрицы смежности A в квадрат элемент A(1,4) получается умножением первой строки матрицы A на её четвёртый столбец: и суммировании результатов умножения. Не нулевыми при умножении будут второй и третий слагаемые суммы, что соответствует второй и третьей вершинам графа как промежуточным вершинам пути длиной два из первой вершины в четвёртую. Это можно проверить и по орграфу. В матрицу s (s2) можно взять любую из них.

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

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

Длина маршрута в нагруженном графе равна сумме весов составляющих маршрут рёбер. Алгоритм Флойда построения минимальных путей в нагруженном орграфе похож на метод Уоршелла. Алгоритм Флойда работает и для нагруженных графов.

Строится последовательность квадратных матриц B0, B1, … , Bn. B0 = L, только с обнулённой главной диагональю. Элемент матрицы Bt(j, k) содержит значение минимального пути из вершины j в вершину k такого, что внутренние вершины этого пути принадлежат множеству вершин {1, 2, … , t}. Bt(j, k) = min(Bt`(j, k), (Bt`(j, t)+Bt`(t, k))), где t` = t-1. Включение вершины t в путь от вершины j к вершине k:

Возьмём нагруженный орграф:

Его матрица длин дуг L и матрицы B0, B1, B2 и B3:

В матрице B1 по сравнению с матрицей B0 первая вершина добавила путь длиной восемь из второй вершины в третью (элемент B1(2,3)). В матрице B2 по сравнению с матрицей B1 вторая вершина добавила путь длиной пять из третьей вершины в первую (элемент B2(3,1)). В матрице B3 по сравнению с матрицей B2 третья вершина изменила путь длиной восемь на меньший, длиной семь, из первой вершины во вторую (элемент B3(1,2)).

Матрицы B0, … , Bn – это аналог массива p длин минимальных путей. В массиве s хранятся номера предпоследних вершин минимальных путей, как и для не нагруженных графов и орграфов. Элемент s(j, k) содержит номер вершины t, полученный при нахождении минимального значения элемента B(j, k). Если s(j, k) равен нулю, то кратчайший путь из вершины j в вершину k состоит из одной дуги. Матрица s для нашего примера имеет вид:

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

Глава 13. Деревья. Циклы в двудольных графах

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

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

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

Пусть, например, существует ребро между вершинами выбранной второй доли. Тогда цикл (не обязательно простой), начинающийся и заканчивающийся в выбранной вершине 1-й доли и проходящий через эти две вершины 2-й доли с ребром между ними, имеет нечётную длину:

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

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

Лес – это граф без циклов. Связный лес называют деревом. Дерево, как ни рисуй (беря корнем разные вершины), всё равно получишь дерево, так как циклов в нём нет. Следующие утверждения эквивалентны:

·  граф G – дерево;

·  G связен и не имеет циклов;

·  G связен и n = m + 1;

·  любые две вершины G можно соединить единственной и притом простой цепью;

·  G не содержит циклов, но добавляя к нему любое новое ребро, получим в графе G ровно один и притом простой цикл, проходящий через добавленное ребро.

Любое дерево может быть задано его двоичным кодом. Код дерева имеет длину 2m и состоит из m нулей и m единиц. Для любого начального отрезка кода дерева число единиц в нём не больше числа нулей. Код дерева всегда начинается с 0 и заканчивается 1. Код дерева зависит от того, какую вершину мы выберем в качестве корня. Дерево с одним ребром и двумя вершинами имеет код 01.

Каждое ребро дерева имеет в коде свой ноль и свою единицу, причем единица всегда находится в коде далее нуля. Код получается в результате обхода дерева. Обход начинается и заканчивается в корне дерева. Если ребро дерева встречается при обходе первый раз, то в коде появляется 0 этого ребра, а если второй (и последний), то в коде появляется 1 этого ребра. Цепочка из 5 вершин (C) является простейшим деревом и имеет код . Например, дерево с кодом :

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

Утверждение: для дерева m = n – 1. Доказательство индукцией по n. Для n = 1 m = 0 и m = n – 1. Делаем индуктивное предположение, что утверждение верно и для дерева с (n-1) вершинами. Докажем из этого, что утверждение верно и для дерева с n вершинами.

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

Остовным деревом связного графа называется дерево, содержащее все его вершины и некоторое подмножество рёбер графа. Цикломатическим числом связного графа называется число рёбер, которое надо удалить из графа, чтобы превратить его в дерево (своё собственное остовное дерево). = p + m – n. Цикломатическое число дерева и леса равно нулю. Для получения остовного дерева надо найти в графе цикл и удалить из цикла любое ребро. Процедуру удаления продолжать до тех пор, пока циклов в графе не останется. Остовных деревьев у графа может быть несколько. Остовные деревья колеса на шести вершинах – это граф – звезда и цепь:

Теорема: Число рёбер в графе удовлетворяет неравенствам:

n – p m (n – p) (n – p + 1)/2.

Доказательство: для p = 1 это очевидно: n – 1 m (n – 1) n /2, где (n - 1) - это число рёбер у дерева (связный граф с минимальным числом рёбер), а (n – 1) n /2 – это число рёбер у полного графа (связный граф с максимальным числом рёбер).

Если имеется лес из p деревьев, то число рёбер в каждом дереве на единицу меньше числа вершин в нём. Отсюда из числа вершин n в лесе p раз вычитается единица. Тогда для леса из p деревьев n – p = m. Оценка снизу доказана.

Оценку снизу сначала докажем для двух компонент связности (p = 2). В одной компоненте связности n1 вершин, а в другой – ( n – n1) вершин. 1 n1 (n – 1), в каждой компоненте связности есть хоть одна вершина. Максимальное число рёбер в этом графе из двух компонент связности зависит от n1 и равно: f(n1) = n1 (n1-1) /2 + (n-n1) (n-n1-1)/2 = (n1 – n1 + n - 2n1n +n1- n + n1)/2 = (n +2 (n1) - 2 n n1)/2. Здесь каждая из двух компонент связности является полным графом.

Для определения экстремумов функции f(n1) берём её первую и вторую производные: f ` (n1) = 2n1 – n и f `` (n1) = 2. Приравниваем нулю первую производную и получаем, что n1 = n/2 и это минимум, так как вторая производная больше нуля. Значит, максимумы функции f(n1) находятся на концах отрезка и достигаются при n1 = 1 или при n1 = n-1.

Это значит, что максимальное число рёбер у графа с двумя компонентами связности (f(1) = (n-1) (n-2)/2 = f(n-1)) достигается тогда, когда одна из компонент состоит из одной вершины, а другая является полным графом на (n-1)-й вершине.

Для доказательства оценки сверху считаем каждую компоненту связности графа полным графом. Пусть Cj и Ck – это две компоненты связности каждая соответственно с nj и nk вершинами, где 1 < nk nj. Если заменить Cj и Ck на полные графы с (nj +1) и (nk-1) вершинами, то число вершин не изменится, а число рёбер увеличится на положительную величину: ((nj + 1) nj – nj (nj-1))/2 – (nk (nk – 1) – (nk-1) (nk-2))/2 = nj – nk +1.

Следовательно, чтобы число рёбер в графе было максимально возможным при заданных n и p, граф должен состоять из (p – 1) изолированных вершин и полного графа на (n – p + 1) вершинах. Оценка сверху доказана.

Следствие: любой граф с n вершинами и более чем (n-1) (n-2)/2 рёбрами связен. Это так, так как максимальное число рёбер при p = 2 – это (n-1) (n-2)/2, а у нас их больше.

Дерево можно задать матрицей смежности, но это будет очень не экономно, так как в ней будет много нулей. Код дерева – это не единственный экономный способ задания дерева. Обычно каждый выбирает для своей задачи наиболее удобный в данном случае способ задания дерева.

Число Каталана – это число бинарных деревьев с n вершинами. Бинарное дерево с n=0 – это пустое дерево, а с n > 0 вершинами – это тройка Д=(Л, К, П), где К – вершина, называемая корнем дерева, Л – левое поддерево с Л вершинами и П – правое поддерево с П вершинами и n=Л+1+П. С- число различных бинарных деревьев с k вершинами (число Каталана). C= C=1 и если 0<=s<=k, то существует CC различных бинарных деревьев вида (s, 1, k-1-s). Число вершин левого поддерева s принимает значения от 0 до k-1, и, значит, С= C С+ C С+ . . . + С C и k>0. Это рекурсивное задание чисел Каталана. Числа Каталана от C до C и соответствующие им бинарные деревья:

Для получения аналитической формулы для чисел Каталана рассмотрим производящую функцию: C(x) = . C(x) C(x) = C(x) = = = / x = (C(x) - C)/x. Итого: C(x) x = C(x) –1. Отсюда C(x) = (1 )/(2x). Разложим в ряд. Для k > 0 имеем () = ½ (½ - 1) (½ - 2) … (½ - k + 1)

(1 – 4 x) = 2 1 3 … (2k – 3) (1 – 4 x) и, значит, = 1 - =

= 1 - = 1 – 2 = 1 – 2 . Для получения решения с положительными коэффициентами берём C(x) = (1 )/(2x) = = . С помощью производящей функции получается, что С=C/(k+1) =

= (2k)!/(k! k! (k+1)).

Число Каталана равно числу всевозможных расположений скобок в произведении x0x1…xn. Например, при n = 2 имеется два способа расстановки скобок: (x0x1)x2 и x0(x1x2).

Число Каталана равно числу способов, которыми можно разбить выпуклый (n+2) – угольник на различные треугольники с помощью (n-1) диагоналей, не пересекающихся внутри этого (n+2) – угольника. Например, для четырёхугольника (n = 2) существует только два способа

разбиения на треугольники с помощью одной диагонали:

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

Ассоциированный граф ордерева (орлеса) является деревом (лесом). У растущего ордерева у корня полустепень захода равна нулю, а у остальных вершин полустепень захода равна единице:

Глава 14. Теорема Холла и цепи Маркова

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

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

Теорема Холла: паросочетание будет максимальным тогда и только тогда, когда любые k вершин из меньшей доли вершин мощностью n будут иметь рёбра в совокупности по меньшей мере с k вершинами из большей доли вершин мощностью n, где 1<=k<= n и n<= n. Если взять подграф двудольного графа, образованный k вершинами меньшей доли и всеми смежными с ними вершинами большей доли, то он будет двудольным, так как любой подграф двудольного графа тоже двудольный. Количество вершин этого подграфа из большей доли вершин не должно быть меньше k.

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

Для доказательства достаточности воспользуемся индукцией и допустим, что теорема справедлива для числа вершин меньшей доли, меньшее m. При m = 1 теорема верна – это первый шаг индукции. Пусть теперь в меньшей доле m вершин и рассмотрим два возможных случая.

Сначала будем считать, что любые k вершин меньшей доли (0 <k <m) имеют рёбра в совокупности по меньшей мере с (k + 1) вершинами большей доли (т. е. условие теоремы всегда выполняется с одной «лишней» вершиной большей доли вершин). Тогда, если взять любую вершину меньшей доли и спарить её с любой смежной ей вершиной большей доли, то для других (m – 1) вершин меньшей доли останется в совокупности не менее (m-1) смежных вершин большей доли и по индуктивному предположению для них существует совершенное паросочетание из (m - 1) пар. Добавив первую пару вершин, получим паросочетание из m пар.

Допустим теперь, что имеется k вершин меньшей доли (k < m), которые имеют рёбра в совокупности ровно с k вершинами большей доли. По индуктивному предположению для этих k вершин можно получить совершенное паросочетание из k пар.

Остаются ещё (m – k) вершин меньшей доли, но любые h из них ( 0 < h < m – k + 1) имеют рёбра в совокупности по меньшей мере с h вершинами большей доли из оставшихся вершин большей доли. В противном случае эти h вершин меньшей доли вместе с уже выбранными k вершинами меньшей доли будут иметь рёбра в совокупности меньше, чем с (h + k) вершинами большей доли, а это противоречит условию теоремы. Следовательно, для этих (m – k) вершин меньшей доли выполнено условие теоремы и для них работает индуктивное предположение. Значит, для этих (m – k) вершин можно получить совершенное паросочетание из (m - k) пар. Добавив ранее полученные k пар вершин, получим совершенное паросочетание из m пар. Теорема доказана.

Для получения частичного паросочетания, имеющего на одну пару вершин меньше, чем совершенное, любые k вершин из меньшей доли вершин должны иметь рёбра в совокупности по меньшей мере с (k – 1) вершинами из большей доли. Для получения частичного паросочетания, имеющего на две пары вершин меньше, чем совершенное, любые k вершин из меньшей доли вершин должны иметь рёбра в совокупности по меньшей мере с (k – 2) вершинами из большей доли. И так далее.

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

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

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

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