П. 4. Раскрашенный граф

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

Примеры. b

1. Имеем: c(Kn) = n. В частности, c(K 3) = 3. a g a

2. Граф без ребер называется пустым. Для него всегда c = 1. a a

Упр. 9. Выпишите в виде таблицы все 11 графов порядка 4 и соответствующие им хроматические числа.

2. Двудольные графы. Граф двудольный, если все его вершины можно окрасить в два цвета так, чтобы любое ребро имело разноцветные концы. Если при этом каждая вершина одного цвета соединена ребром с каждой вершиной другого цвета, то граф полный двудольный и обозначается Km, n, где n — число вершин одного цвета, m — другого.

Граф Km, n имеет ровно m + n вершин и mn ребер.

Примеры.

1. Граф K 3,3не планарен. a

2. Граф K 1, n называется звездным. Пример: граф K 1,3. a b a

Упр. 10. Нарисуйте на плоскости граф K 3,3.

Теорема. Любой граф, имеющий подграфом K 5или K 3,3, непланарен. И наоборот: любой непланарный граф содержит подграф K 5или K 3,3.

Замечание. В пространстве этой проблемы нет. Любой граф можно вложить в трехмерное пространство так, чтобы его ребра не пересекались.

3. Гипотеза четырех красок. Впервые сформулировал эту гипотезу студент-дипломник Лондонского университета в 1852 году: любую карту на плоскости можно раскрасить только четырьмя красками так, что никакие две смежные страны не имеют один цвет. История этой гипотезы — самая длительная и волнующая в теории графов.

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

Несложно доказать, что пяти красок достаточно. Но четырех…

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

Упр. 11. Нарисуйте карту Европы и раскрасьте все страны четырьмя красками так, чтобы никакие две смежные страны не имели один цвет.

Цепь Маркова

И решил Браконьер в одиночку рискнуть,

И, влекомый высокою целью,

Он бесстрашно свернул на нехоженый путь

И пошел по глухому ущелью.

Льюис Кэрролл. Охота на Снарка.

П. 1. Орграф

1. Определение. Орграфом, или ориентированным графом, называется пара (V, A), где V — непустое множество элементов, называемых вершинами, а A — множество упорядоченных (не обязательно различных) пар вершин из V, называемых дугами, или ориентированными ребрами. Дуга, у которой 1-й элемент — вершина v, а второй — вершина w, называется дугой из v в w и обозначается (v, w). Заметим, что дуги (v, w) и (w, v) различны!

Граф, полученный из орграфа «удалением стрелок», т.е. заменой всех дуг на ребра, называется основанием орграфа.

Пример. Ниже приведены два орграфа и посередине — их основание.

u z u z u z

v w v w v w

Упр. 1. Выпишите множество V вершин и множество A дуг этих орграфов.

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

Упр. 2. В примере приведены два орграфа. Они изоморфны? Почему?

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

Упр. 3. Выпишите все три орцикла для орграфов из примера.

3. Связность. Орграф связен, или слабо связен, если связно его основание. Другими словами, связный орграф нельзя представить в виде объединения двух различных орграфов.

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

Упр. 4. Оба орграфа из примера связны. Они сильно связны? Почему?

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

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

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

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