2. Раскраска карт. Бихроматичность карт.

Связный плоский мультиграф без мостов называется картой. Грани карты, имеющие общее ребро, называются смежными. Функция f, ставящая в соответствие каждой грани  карты натуральное число f(){1, 2, …, k} — цвет грани  — называется k-раскраской, если цвета смежных граней различны. Карта называется k-раскрашиваемой, если для нее существует k-раскраска.

Гипотеза четырех красок: всякая карта 4-раскрашиваема.

Часто пользуются другой формулировкой гипотезы четырех красок: всякий планарный граф 4-раскрашиваем.

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

Теорема 15.7. Карта G является k-раскрашиваемой тогда и только тогда, когда геометрически двойственный граф G^* вершинно k-раскрашиваем.

Согласно теореме Кёнига (G) = 2 для непустого графа G тогда и только тогда, когда он не содержит циклов нечетной длины, откуда несложно получить следующее утверждение.

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

 Достаточно доказать, что плоский двусвязный граф, граница каждой грани которого состоит из четного числа ребер, является двудольным. Рассмотрим произвольный простой цикл C такого графа. Этот цикл делит плоскость на две части — внутреннюю (по отношению к циклу) и внешнюю. Считаем, что сам цикл принадлежит каждой из частей. Пусть внутренняя часть плоскости содержит грани ₁, ₂,…, _k с числом ребер в их границах l₁, l₂,…, l_k соответственно. Так как любое из чисел l_i четное, то их сумма также четная. Но каждое ребро, не принадлежащее циклу C, входит в эту сумму дважды, откуда следует, что длина цикла C четная. Из теоремы 9.1 следует, что рассматриваемый граф является двудольным.

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

Утверждение 15.9. Карта G является 2-раскрашиваемой тогда и только тогда, когда граф G эйлеров.

БИЛЕТ 20

1. Числа Стирлинга второго рода. Первый способ рекуррентного вычисления чисел Стирлинга второго рода.

Число разбиений m-элементного множества на k непустых подмножеств обозначим через S(m, k) и будем называть его числом Стирлинга второго рода. Утверждение 8.1. А. S(m, m) = 1 при m  0. Б. S(m, 0) = 0 при m > 0. В. S(m, k) = S(m –1, k – 1) + kS(m –1, k) при 0 < k < m.

 Пункты «А» и «Б» очевидны. Для доказательства пункта «В» заметим, что множество R всех разбиений X = {x₁, x₂,…, x_m} на n частей распадается на множества R₁ = { R | одноэлементное множество {x_m} является элементом разбиения } и R₂ = R \ R₁. Очевидно, | R₁ | = S(m – 1, k – 1). Поставим в соответствие каждому разбиению R₂ разбиение ’ множества X \ {x_m}, полученное из  удалением элемента x_m из той части, которой он принадлежал. Поскольку каждое разбиение ’ множества X \ {x_m} будет поставлено в соответствие ровно k разбиениям множества X (образованным из ’ путем добавления x_m к какой-нибудь из k частей), то | R₂ | = kS(m – 1, k). 