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

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

Теперь покажем, как получается реальный путь из оптимального. Например, контур 1-3-4-5-2-1 имеет длину 16. Из тензора L4 оптимальный путь 1-3-4-5-2 имеет реальный прототип: 1-4-5-3-2, а из тензора L2 оптимальный путь 1-4-5-3 имеет реальный прототип: 1-5-4-3. Итого реальный цикл имеет оптимальную длину 16, как и реальный цикл .

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

В тензорах L1 и L2 содержатся не только маршруты длины один и два из первой вершины графа во все остальные его вершины, но и обратные маршруты из остальных вершин графа в первую. Из оптимизированного тензора L3, содержащего маршруты длиной три, составим гамильтоновы циклы длиной шесть (тензор L6) и выберем из них цикл минимальной длины. В каждой строке L6 содержатся циклы, имеющие одинаковую среднюю вершину. Тензор L3 (в двух частях), содержащий маршруты длиной три из первой вершины нагруженного графа во все остальные пять его вершин и обратные маршруты длиной три из всех остальных вершин графа в первую:

Итоговый тензор L6, из которого будет определяться гамильтонов цикл минимальной длины:

Отсюда гамильтонов цикл минимальной длины в нагруженном графе имеет длину 18. Этот оптимальный путь имеет вид: 1-3-4-2-5-6-1, а его реальный прототип, полученный из тензора L3, имеет вид: -1. Маршрут длины три из 2-й вершины в первую через 5-ю и 6-ю вершины надо брать из L3 обратным маршруту из 1-й во вторую. Заметим, что «жадный» алгоритм получил гамильтонов цикл -1 длины 19.

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

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

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

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

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

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

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

В принципе, имеет право на жизнь и задача нахождения максимального остовного дерева в нагруженных графах. «Жадный» алгоритм работает и для этой задачи, только в качестве оптимальных рёбер надо брать рёбра максимальной длины. Например, для нагруженного графа с шестью вершинами, для которого задача коммивояжёра решалась двумя способами, минимальное остовное дерево имеет сумму рёбер 11, а максимальное – 41. Для этого графа минимальное остовное дерево – это цепь, полученная при решении задачи коммивояжёра: , так как вершин степени, большей двух, не возникало.

Глава 17. Раскрашивание графов. Хроматические многочлены

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

Граф без петель называют k – раскрашиваемым, если каждой его вершине можно приписать один из k цветов так, чтобы никакие его две смежных вершины не оказались одного цвета. Если граф G является k – раскрашиваемым, но не является (k – 1) – раскрашиваемым, то он будет k – хроматическим, а число k будет хроматическим числом графа и обозначается буквой (G).

Раскрашиваемые графы не содержат петель, но могут содержать кратные рёбра. Кратность рёбер не влияет на раскрашиваемость. Пример 4 – хроматического графа, где a, b, c и d – это цвета вершин графа:

Для полного графа (K) = n, для графа без рёбер (N) = 1, для двудольного графа G (G) = 2, и всегда (G) n. Если граф содержит в качестве подграфа K, то его хроматическое число не меньше числа R.

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

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

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

Теорема: любой планарный граф 6-раскрашиваем. Доказательство индукцией по числу вершин n в графе. Первый шаг индукции: для планарных графов с n < 7 шести красок хватит для раскраски графа. Делаем индуктивное предположение, что шести красок хватит для раскраски планарного графа с (n – 1)-й вершинами.

Берём планарный граф с n вершинами и удаляем из него вершину, степень которой не больше пяти, вместе с рёбрами, у которых она является концом. По вышедоказанной теореме такая вершина существует в любом планарном графе. Оставшийся планарный граф имеет (n – 1) вершину и по индуктивному предположению он 6 – раскрашиваем.

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

Теорема: любой планарный граф 5-раскрашиваем. Доказательство индукцией по числу вершин n в графе. Для планарных графов, имеющих менее шести вершин, результат очевиден. Имеем планарный граф с n вершинами и все планарные графы с (n – 1) вершинами 5-раскрашиваемы. Аналогично предыдушей теореме удаляем вершину со степенью не больше пяти вместе с рёбрами, у которых она является концом.

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

Пусть теперь степень возвращённой вершины равна пяти и смежные с ней вершины v1, …, v5 располагаются вокруг неё по часовой стрелке:

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

Пусть теперь всем пяти вершинам vj присвоены разные цвета. Каждая вершина vj окрашена в цвет cj. Определим H(i, j) как подграф планарного графа с n вершинами, вершинами которого являются все вершины цвета ci или cj, а рёбрами – все рёбра, соединяющие вершину цвета ci с вершиной цвета cj.

Теперь имеются две возможности:

1) Вершины v1 и v3 не принадлежат одной и той же компоненте графа H(1,3), тогда можно поменять цвета всех вершин той компоненты H(1,3), которая содержит v1 (т. е. цвет c1 заменить на цвет c3 и наоборот). В результате v1 приобретёт цвет c3, что позволит окрасить возвращённую в граф вершину степени пять в цвет c1. Для этого случая доказательство завершено.

2) Вершины v1 и v3 принадлежат одной и той же компоненте графа H(1,3). Это значит, что существует цепь, соединяющая v1 и v3 и лежащая внутри H(1,3), а вместе с возвращённой в граф вершиной степени пять эта цепь образует цикл. Вершина v2 находится внутри этого цикла, а вершина v4 – вне его:

Получаем, что не существует цепи из v2 в v4, целиком лежащей в H(2,4), так как граф планарен. Это значит, что можно поменять цвета всех вершин компоненты подграфа H(2,4), содержащей вершину v2. При этом вершина v2 приобретёт цвет c4, что позволит окрасить возвращенную в граф вершину в цвет c2. Доказательство закончено.

Гипотеза четырёх красок (пока не доказана): всякий планарный граф 4-раскрашиваем. Некоторые относящиеся к этой проблеме результаты:

- всякий планарный граф, имеющий менее 52 вершин, 4-раскрашиваем;

- любой не содержащий треугольников планарный граф 3-раскрашиваем;

- гипотезу четырёх красок достаточно доказать для гамильтоновых планарных графов.

P(k) – это число способов, которыми можно раскрасить граф G так, чтобы все смежные вершины имели разные цвета. Для цепи из трёх вершин P (k) = k (k - 1), существует k способов раскрасить среднюю вершину и (k - 1) – для концевых вершин:

Для дерева с n вершинами P (k) = k (k - 1), k способов раскрасить корень дерева и (k - 1) способов раскрасить все остальные его вершины:

P (k) = k (k - 1) (k - 2) … (k – n + 1) = k! / (k - n)!. Если k < , то P(k) = 0, а при k P(k) > 0. Для планарного графа P(4) > 0.

Теорема: пусть v и w – несмежные вершины в графе G. Граф G1 получен из графа G путём соединения ребром вершин v и w, а граф G2 – путём отождествления вершин v и w. Тогда P(k) = P(k) + P(k). Теорема для этого примера утверждает, что k (k - 1) (k - 2) = k (k - 1) (k - 2) (k - 3) + k (k - 1) (k - 2):

G
G1 G2

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

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

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

Теперь P называем хроматическим многочленом графа G. Степень многочлена P равна n (числу вершин в графе G), так как на каждом шаге не возникает никаких новых вершин. Коэффициент при k равен единице, так как описанная выше конструкция порождает только один полный граф с n вершинами. Можно показать, что коэффициент при k равен (- m) и знаки коэффициентов чередуются (знакопеременная сумма).

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

Таким образом: P (k) = k (k - 1) (k - 2) (k - 3) (k - 4) + 3 k (k - 1) (k - 2) (k - 3) + 2 k (k - 1) (k - 2) = k (k - 1) (k - 2) (k – 4 k + 5) = k – 7 k + 19 k – 23 k + 10 k = k (k - 7 k + 19 k - 23 k + 10). При r = 2 P (2) = 10 – 46 + 76 – 56 + 16 = 0. При k = 3 P (k) > 0 и значит, граф примера является 3-хроматическим графом:

Хроматические многочлены и раскрашиваемость связаны с задачей

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

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

Литература

1.  Андерсон, Дискретная математика и комбинаторика / Андерсон; пер. . – М. : Издательский дом «Вильямс», 2004. – 960 с.

2.  Кофман, А. Введение в прикладную комбинаторику / А. Кофман ; пер. , . – М. : Наука, 1975. – 479 с.

3.  Кузнецов, математика для инженера / , -Вельский. – М. : Энергоатомиздат, 1988. – 480 с.

4.  Липский, В. Комбинаторика для программистов / В. Липский ; пер. , . – М. : Мир, 1988. – 213 с.

5.  Нефедов, дискретной математики / , . – М. : Изд-во МАИ, 1992. – 264 с.

6.  Новиков, математика для программистов / . – СПб. : Питер, 2002. – 304 с.

7.  Уилсон, Р. Введение в теорию графов / Р. Уилсон ; пер. . – М. : Мир, 1977. – 207 с.

Учебное издание

Дискретная математика

Составитель

ЗАХАРОВА Лариса Евгеньевна

Клышинская

Технический редактор

http://www. miem. *****/rio/

*****@

Подписано в печать. .11. Формат 60х84/16

Бумага типографская. Печать – ризография.

Усл. печ. л. , Уч.-изд. л. , Тираж 200 экз.

Заказ . Изд № .

Московский государственный институт электроники и математики

109028 Москва, Б. Трёхсвятительский пер., 3/12.

Отдел оперативной полиграфии Московского государственного

института электроники и математики.

113054 Москва, .