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

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

В полном двудольном графе всегда существует совершенное паросочетание мощностью, равной мощности меньшей доли вершин. Каждый K даёт по три пары, итого получается семь пар вместо восьми. Частичное паросочетание вместо полного.

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

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

Здесь парные рёбра выделены рисованной кривой. В графе остались две непарных вершины: пятая и десятая. Они связаны чередующейся цепью длины три относительно паросочетания мощности четыре: 5 – 6 = 2 – 10 вершины и парное ребро находится в середине цепи. Совершенное паросочетание этого графа: 1 – 8; 2 – 10; 3 – 7; 4 – 9; 5 – 6.

Паросочетание будет максимальным тогда и только тогда, когда не будет существовать чередующейся цепи относительно него. Чередующиеся циклы в двудольном графе позволяют находить все максимальные паросочетания. В чередующемся цикле все вершины парные, а рёбра поочерёдно то парные, то непарные. Относительно вышеприведённого совершенного паросочетания существует чередующийся цикл: 4 = 9 – 2 = 10 – 4. Сделав парные рёбра из этого цикла непарными, а непарные – парными, получим ещё одно совершенное паросочетание графа: 1 – 8; 2 – 9; 3 – 7; 4 – 10; 5 – 6.

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

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

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

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

Паросочетания используются при трассировке больших интегральных схем (БИС). Некоторые БИС состоят из программируемых логичесих модулей, которые могут быть соединены между собой и с глобальными входами и выходами БИС с помощью так называемых трассировочных ресурсов. Каждый трассировочный ресурс может быть использован только для реализации одного соединения, но имеет возможность реализовать несколько соединений.

Программирование логических модулей и соединение их между собой и с входами и выходами БИС осуществляется в соответствии с проектируемым на БИС цифровым устройством (сумматором, например). Одна доля двудольного графа – это соединения БИС (например, выход 5 – на вход 14), а вторая – её трассировочные ресурсы. Рёбра делают смежными трассировочные ресурсы и те соединения БИС, которые эти ресурсы могут реализовать.

Трассировка может быть автоматической, полуавтоматической и ручной. Если автоматическая трассировка смогла реализовать на БИС все желаемые для реализации цифрового устройства соединения, то необходимости в других видах трассировки нет. В противном случае можно взять не реализованные автоматической трассировкой соединения, и реализовать их вручную, перепрограммируя некоторые логические модули, например. Это будет полуавтоматическая трассировка.

Рассмотрим приложение теории орграфов к изучению цепей Маркова. В цепи Маркова имеется n состояний (E1, … , En), квадратная матрица перехода P размером n и вектор x длины n, определяющий начальное состояние цепи. Каждый элемент P матрицы перехода равен вероятности перехода цепи из i-го состояния в j-е за единицу времени.

Рассмотрим, например, одномерное случайное блуждание. Броуновское движение молекул газа является трёхмерным случайным блужданием. Имеем для одномерного случайного блуждания шесть состояний E1, … , E6. Состояния отстоят друг от друга на 10 метров, например. Начальное положение объекта задаётся вектором x длины шесть. Пусть, например, x = (0, 0, 0, 1, 0, 0), что означает, что вначале объект находится в состоянии E4. Состояния E2, E3, E4 и E5 могут быть начальными для объекта:

Если объект попадает в E1 или в E6, то он из них уже не выходит, это «поглощающие» состояния. Каждую единицу времени (минуту, например) во всех состояниях, кроме поглощающих, объект передвигается либо в сторону E1 с вероятностью ½, либо в сторону E6 с вероятностью 1/3, либо остаётся на месте с вероятностью 1/6. Теория орграфов позволяет решить: в каком поглощающем состоянии объект окажется с наибольшей вероятностью и какое наиболее вероятное время его попадания туда, если известно его начальное положение. Матрица перехода P для этой цепи Маркова имеет вид:

Из матрицы перехода P видно, что вероятность перехода из E2 в E3 за одну минуту равна 1/3 (элемент P= 1/3), а вероятность перехода из E2 в E4 за одну минуту равна нулю (элемент P= 0). В матрице перехода P каждый элемент не отрицателен и сумма элементов по каждой из строк равна единице. Положение объекта через минуту (единицу времени) описывается вектором xP, а через k минут (единиц времени) – вектором xP. j-я компонента вектора xP – это вероятность нахождения объекта через k минут в состоянии Ej.

Если в матрице перехода P все положительные (не нулевые) значения заменить единицами, то получим матрицу смежности A ассоциированного с этой цепью Маркова орграфа: A = sign(P). Очевидно, что различные цепи Маркова с различными матрицами перехода могут иметь одинаковые ассоциированные орграфы. В ассоциированном с цепью Маркова орграфе состояния цепи представляются в виде вершин орграфа, а дуги между вершинами существуют тогда и только тогда, когда можно перейти из одного состояния в другое за одну минуту. Для ассоциированного орграфа важно, положительна ли вероятность перехода между состояниями, а само её значение не важно. Ассоциированный орграф одномерного случайного блуждания имеет вид:

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

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

Состояния бывают возвратные и невозвратные. В возвратные состояния цепь Маркова возвращается независимо от продолжительности процесса, а в невозвратные цепь попадает несколько раз и более не возвращается. Более того, если начальное состояние цепи Ei, и вероятность возвращения в Ei на некотором более позднем шаге равна единице, то Ei называют возвратным (рекурентным) состоянием. Для случайного блуждания состояния E1 и E6 возвратны, тогда как другие состояниеяневозвратны.

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

Рассмотрим ещё одну цепь Маркова с матрицей перехода P:

Её ассоциированный орграф имеет вид:

Эта цепь тоже не является неприводимой. В её ассоциированном орграфе существует орцепь из первой вершины в четвёртую, но не существует обратной цепи из четвёртой вершины в первую. Это значит, что состояние E1 и, аналогично, состояние E3 невозвратны. Состояния E2, E4, E5 и E6 возвратны, причём E2 – это поглощающее состояние, так как из него нельзя попасть ни в какое другое состояние. Заметим, что состояния E4, E5 и E6 образуют как бы «поглощающий» треугольник. Это один приём классификации состояний.

Другой приём классификации состояний опирается на понятие периодичности состояний. Состояния бывают периодические и не периодические. Состояние будет периодическим с периодом t (t>1), если в состояние можно вернуться по истечении времени, кратного t. Если такого t не существует, то состояние называют непериодическим.

Очевидно, что если у соответствующей состоянию вершине в орграфе есть петля, то оно непериодическое (t = 1). Отсюда поглощающее состояние непериодическое. В задаче о случайном блуждании все состояния непериодические.

Во втором примере только E2 единственное непериодическое состояние, так как состояния E1 и E3 имеют период два, а E4, E5 и E6 – период три. Состояние будет периодическим тогда и только тогда, когда в ассоциированном орграфе длина каждого орцикла, проходящего через соответствующую этому состоянию вершину, кратна t.

Состояние цепи Маркова называется эргодическим, если оно возвратно и непериодично. Если все состояния являются эргодическими, то это эргодическая цепь Маркова. Пример эргодической цепи:

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

Глава 15. Планарность и теорема Куратовского. Грани графа. Теорема Эйлера

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

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

Теорема: графы K и K не планарны. Доказательство: предположим сначала, что граф K планарен. Поскольку он содержит цикл длины пять, то изобразим этот цикл правильным пятиугольником: v – w – x – y - z - v. Для оставшихся вне этого цикла пяти рёбер два ребра (например, z – w и z - x) можно уложить внутри пятиугольника. Чтобы рёбра v – x и v – y не пересекались с уложенными внутри пятиугольника двумя рёбрами, их надо уложить снаружи пятиугольника:

Оставшееся ребро w – y нельзя уложить ни снаружи, ни внутри пятиугольника так, чтобы оно не пересекалось с уже уложенными четырьмя рёбрами. Получили противоречие.

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

Получили противоречие. Теорема доказана.

Каждый подграф планарнрго графа планарен и любой граф, содержащий в качестве подграфа непланарный граф, сам непланарен. Значит, любой граф, содержащий K и K в качестве подграфа, не планарен. Оказывается, что K и K - это по существу единственные не планарные графы в том смысле, что любой не планарный граф содержит один из них.

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

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

Операция подразбиения дуг и понятие гомеоморфизма существуют и для орграфов.

Теорема Куратовского: граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K или K. Без доказательства.

Плоский граф разбивает плоскость, на которой он изображён, на грани, окружённые рёбрами графа. Одна грань у графа всегда не ограничена, она называется бесконечной. Вот плоский граф с тремя гранями: f1, f2 и f3, и грань f3 – бесконечная:

Здесь грань f1 имеет (ограничена) семь рёбер, грань f2 – четыре, а грань f3 – пять. Число граней в планарном графе обозначается буквой f. В качестве бесконечной грани можно взять любую грань, достаточно по - другому перерисовать граф. Например, тот же граф с тремя гранями, но слева бесконечной сделана грань f1, а справа – грань f2:

Теорема Эйлера: для связного плоского графа n+f=m+2, где f, n и m – число соответственно граней, вершин и рёбер у графа. Доказательство индукцией по числу рёбер m в графе. Если m = 0, то n = 1 (граф связен) и f = 1, т. е. n + f = m + 2 для m = 0. Сделан первый шаг индукции.

Делаем индуктивное предположение, что теорема верна для каждого графа, имеющего (m – 1) рёбер, и добавим к графу новое ребро. Тогда оно либо петля, либо соединяет две вершины из графа, либо соединяет вершину графа и новую вершину:

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

Для не связных плоских графов теорема Эйлера имеет вид: n+f=m+p+1, где p – число компонент связности. Это следствие теоремы Эйлера. Результат получается применением теоремы Эйлера к каждой компоненте связности по отдельности. При этом бесконечная грань считается только один раз.

У дерева и у леса, например, f = 1 (одна бесконечная грань). Следствие теоремы Эйлера: для связного планарного графа с n >= 3 вершинами m <= 3n - 6. Превращаем планарный граф в плоский. Так как каждая грань ограничена по крайней мере тремя рёбрами (минимальная длина цикла в графе равна трём), то при подсчёте числа рёбер вокруг каждой из граней получим, что 3f <= 2m (множитель 2 появляется оттого, что ребро ограничивает не больше двух граней).

По теореме Эйлера n + f = m + 2, отсюда 3f = (m + 2 – n ) 3 и, подставив 3f в неравенство, получим (m + 2 – n ) 3 <= 2m. Окончательно: m <= 3n – 6 .

Ещё одно доказательство теоремы, что графы K и K не планарны. Если K планарен, то для него m <= 3n – 6. Для K m = 10 и n = 5 и получаем, что 10 <= 9, что невозможно.

В K каждая грань ограничена по крайней мере четырьмя рёбрами, так как циклы в двудольном графе имеют чётную длину. Значит, каждая грань приносит как минимум 4 ребра, при этом каждое ребро посчитали дважды (каждое ребро разделяет две грани). Отсюда: 4f<=2m. По теореме Эйлера для плоского связного графа f = m + 2 - n. Значит, 4(m+2-n) <= 2m. Отсюда: 2m<=4n - 8 или 18 <= 16, противоречие. Значит, K не планарен.

Теорема: в любом планарном графе существует вершина, степень которой не больше 5. Доказательство от противного. Считаем граф плоским, связным и n >= 3. Если степень каждой вершины не менее 6, то каждая вершина «приносит» по меньшей мере 6 рёбер, при этом каждое ребро посчитали дважды. Получили: 6n <= 2m. Но по теореме Эйлера m <= 3n-6, то есть получили 6n <= 6n-12, противоречие. Теорема доказана.

Толщина графа t – это наименьшее число планарных графов, объединение (наложение) которых даёт граф. Толщина графа t является мерой его не планарности. Толщина планарного графа равна 1, а толщина K и K - двум. Оценка снизу для толщины графа t получается из теоремы Эйлера. Часто эта оценка является истинным значением толщины. t>={m/(3n-6)} t>=[(m+3n-7)/(3n-6)], где [x] и {x} – целые числа и [x]<=x<={x} и {x}=-[-x].

Толщина графа определяет, сколько понадобится плат для реализации схемы. На каждой плате находятся все вершины графа, а рёбра разбросаны по всем t платам. Так как каждая плата – это плоский граф, то для 1 <= j <= t число рёбер m<= 3n - 6. Так как m = m, то m <= t (3n – 6), а так как t - целое число, то t >= {m/(3n-6)}. {a/b} = [(a + b –1}/b], где a и b - целые числа, большие двух. Отсюда получается и второе неравенсто для толщины графа t.

Глава 16. Задачи коммивояжёра и водопроводчика

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

Для этой задачи существует много точных и эвристических (не точных) методов её решения. Точные методы занимают много времени и памяти ЭВМ на их выполнение. Одним из эвристических методов является так называемый «жадный» алгоритм. «Жадным» этот алгоритм называется потому, что на каждом этапе своего выполнения он берёт наилучшее подходящее по условиям, не думая о последующих этапах.

Например, возьмём нагруженный граф с матрицей длин рёбер L:

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

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

Следующее минимальное ребро имеет длину два и соединяет вторую и шестую вершины. Берём его в окончательный гамильтонов цикл в качестве третьего ребра. Следующее минимальное ребро имеет длину три и соединяет первую и пятую вершины. Берём его в окончательный гамильтонов цикл в качестве четвёртого ребра. Следующее минимальное ребро имеет длину четыре и соединяет шестую и пятую вершины. Берём его в окончательный гамильтонов цикл в качестве пятого ребра.

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

Метод прямого перебора всех гамильтоновых цепей является самым простым из точных методов, но и самым длительным по времени его выполнения. При методе прямого перебора рассматриваются все (n – 1)! перестановок из множества {2, 3, … , n}. Метод Беллмана решения задачи коммивояжёра тоже является точным, но он работает быстрее метода прямого перебора. Покажем, как метод Беллмана работает на нагруженном орграфе с матрицей длин дуг L:

В тензорах L1, L2, … ,L(n-1) строим пути длиной соответственно 1, 2, … ,(n-1) из первой вершины орграфа во все (n – 1) остальных вершин. С путей длины три и далее проводим оптимизацию. Тензоры L1 и L2 (отпимизация ещё не проводится):

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

Пути длиной k строятся из путей длиной (k – 1) (тензор L(k-1)) и матрицы длин дуг L. Например, путь длиной два из 1-й в 4-ю вершину через 2-ю вершину вычисляется так: путь из 1-й во 2-ю берётся из L1 (это 9), а дуга из 2-й в четвёртую - из L (это 8). В сумме получаем 17. Тензор L3:

В тензоре L3 оптимизация производится по порядку внутренних вершин пути. Например, путь из 1-й и 5-ю через 2-ю и 4-ю равен 26, а через 4-ю и 2-ю равен 11. Столбцы, из которых выбирается оптимальное значение, помечены в L3 одинаковым символом. Например, столбцы с промежуточными вершинами 2,4 и 4,2 помечены символом «+». Из двух значений выбирается одно, минимальное. Оптимальные значения в тензоре L3 подчёркнуты. Для вычисления тензора L4 будут использоваться только оптимальные значения тензора L3.

Тензор L3 строится из тензора L2 и матрицы длин дуг орграфа L. Например, путь длиной три из 1-й в 4-ю вершину через 2-ю и 3-ю вершины вычисляется так: путь из 1-й в 3-ю через 2-ю берётся из L2 (это 15), а дуга из 3-й в четвёртую - из L (это 1). В сумме получаем 16. Тензор L4 (в двух частях):

В тензоре L4 оптимизация производится по порядку внутренних вершин пути. Например, путь из 1-й в 5-ю через 2-ю, 3-ю и 4-ю равен 21, через 2-ю, 4-ю и 3-ю равен 18, а через 3-ю, 4-ю и 2-ю равен 11. Тут уже учитывается оптимазация по первым двум промежуточным вершинам, поэтому рассматривается не шесть (3!) наборов промежуточных вершин, а только три. Первые две вершины из трёх промежуточных подчёркнуты, так как их реальный порядок надо определять из тензора L3.

Из трёх значений выбирается одно, минимальное. Столбцы, из которых выбирается оптимальное значение, помечены в L4 одинаковым символом. Например, столбцы с промежуточными вершинами 2,3,5, 2,5,3 и 3,5,2 помечены символом «+». Оптимальные значения в тензоре L4 подчёркнуты. Для вычисления тензора L5 будут использоваться только оптимальные значения тензора L4.

Тензор L4 строится из оптимизированных значений тензора L3 и матрицы длин дуг орграфа L. Например, путь длиной четыре из 1-й в 4-ю вершину через 2-ю, 3-ю и 5-ю вершины вычисляется так: оптимальный путь из 1-й в 5-ю через 2-ю и 3-ю берётся из L3 (это 9 и на самом деле он через 3-ю и 2-ю), а дуга из 5-й в четвёртую - из L (это 1). В сумме получаем 10. Тензор L5 получается из оптимальных значений тензора L4 добавлением дуги, завершающей гамильтонов цикл в орграфе, и в первой строке предпоследняя вершина цикла – это 2-я, во второй – это 3-я, в третьей – это 4-я и в четвёртой – это 5-я: