Замечательно то, что из доказанной нами формулы Эйлера, вернее из следствия формулы Эйлера, которое мы доказали, вытекает не только то, что k5 не планарен, вытекает еще и результат раскраски карты. Вот когда мы с Вами говорим о планарности, у нас ведь раскраска карты — это тоже одна из важнейших задач, которая с этой планарностью связана. Давайте еще раз скажем, о чём идёт речь. Значит вот у нас есть какая-то карта мира, расположенная на плоскости или на сфере, это как удобно можно интерпретировать, неважно. И в этой карте есть какие-то страны, может быть, достаточно сложноустроенные, которые граничат между собою по сплошным линиям, и при этом очень важное условие состоит в том, я вот здесь, конечно, не аккуратно нарисовал, но понятно, при этом очень важное условие состоит в том, что каждая страна — это такая односвязная область, кусок карты. То есть не бывает таких ситуаций, какие случаются в нашей реальной жизни, когда вот Россия, например, является разорванной страной: есть кусочек, который от неё отстоит и к ней не примыкает, вот Калининградская область. Я не имею ввиду, конечно, острова. Острова-то, они граничат с общей частью страны. Вот такие ситуации запрещены. Вот у нас есть на плоскости карта. Мы с Вами уже знаем, что с этой картой естественным образом ассоциирован плоский граф. Ну мы можем условно выделить в каждой из этих стран какую-то столицу и понятно, что всегда можно так соединить эти столицы линиями, образующими рёбра графа, чтобы получился плоский граф. Значит если у нас есть карта, то ей естественным образом отвечает плоский граф, именно плоский, то есть уже расположенный на плоскости таким образом, что его рёбра если и пересекаются, то только по вершинам. То есть он планарный и уже нарисован на плоскости. Значит есть плоский граф, который естественным образом отвечает этой карте. Ну и классическая проблема, проблема 4 красок, она, как я уже рассказывал, состоит в том, чтобы покрасить вот такую карту, любую абсолютно такую карту в неболее чем 4 цвета. То есть каждой стране присвоить 1 из 4 цветов таким образом, чтобы, естественно, граничащие страны получали разные цвета, иначе они на карте сольются и будут неотличимы друг от друга. Вот. В терминах теории графов давайте я введу важнейший такой объект, важнейшую характеристику, то что называется хроматическое число графа. В терминах теории графов напомню, речь идёт вот о чём. Вот есть какой-то граф, пускай плоский, например, или вообще какой-то абстрактный граф. Есть такая его характеристика, которую принято обозначать греческой буквой X (xи). х(G) — это то, что называется хроматическое число графа, то есть цветовое число. Число графа. Ну, давайте я его произнесу сначала словами, а потом как-то запишу в виде формулы, чтоб было удобно. Значит, в принципе я уже об этом говорил, конечно, но я все-таки сейчас это аккуратно напомню, потому что мне нужно с помощью формулы Эйлера и следствия из нее получить какие-то результаты раскраски карты, и для этого мне важно определение хроматического числа. Так вот словами, хроматическое число графа — это наименьшее количество цветов, в которое можно так покрасить вершины графа (каждой вершине графа присвоить некоторый цвет, и хочется, чтобы этих цветов было как можно меньше), так вот можно так покрасить вершины графа, чтобы вершины, которые соединены ребром, обязательно получали разные цвета. Концы любого ребра имели бы разные цвета. Вот хочется минимальное количество цветов, в которые можно так покрасить вершины графа. Это вообще очень важное, в том числе прикладное значение, имеющее характеристика графа. Она действительно, по большому счету, появилась в связи с вот этой классической проблематикой о раскрасках карт, но тем не менее за прошедшие уже больше 150–170 лет эта характеристика зарекомендовала себя очень и очень полезной. На самом деле, речь идёт о такой своего рода кластеризации вершин на отдельные цвета, при которой внутри каждого кластера ребер нет, и все ребра идут между разными кластерами. Ну я уж не буду говорить сейчас о конкретных прикладных задачах, которые с этим связаны, а поговорю все-таки о классической проблеме раскраски карты. Так вот давайте я формулу ещё напишу, что такое хроматическое число, чтобы можно было как-то следить на доске, а не только за моей речью. Это минимальное, как я уже сказал, такое число X, что множество вершин нашего графа, который, ну естественно, обозначается V можно покрасить в X-цветов. Вот как это записать в виде формулы? Ну давайте просто разобъём это множество на X-частей. И каждую часть покрасим в свой цвет, что минимальное такое число X, что существует разбиение множества вершин на X-частей, каждая из которых покрашена в свой отдельный цвет, такое разбиение, что для любого i, то есть для любого номера этого цвета, для любого цвета, и для любых 2 вершин покрашенных в этот цвет, располагающихся в этом множестве — Vi, пара xy не принадлежит множеству ребер Е. Вот такое вот замечательное определение хроматического числа. Мы хотим, чтобы каждое ребро нашего графа, если и появлялось, то между вершинами разных множеств, то есть между вершинами покрашенными в разные цвета. И вот минимальное количество цветов, при котором такое разбиение, такая раскраска возможна, называется хроматическим числом графа. Повторяю, это очень важная классическая характеристика. Ну, касательно вот этой плоской карты и проблемы 4 красок, совершенно понятно, что проблема звучит так: хроматическое число любого плоского графа плоского графа не превосходит 4. Ну я уже рассказывал о том, насколько это сложная проблема, что она в каком-то смысле решена, в каком-то — нет. То есть лишь компьютерный перебор огромного числа случаев позволяет утверждать, что действительно любая карта красится в 4 цвета. Но это как-то некрасиво. Такая была замечательная проблема и вот нате, гора родила мышь. Вот. Замечательно то, что та простенькая, в общем-то, наука, которую мы уже с Вами изучали и продолжаем изучать, в принципе, позволяет очень близко подобраться к этой границе. То есть совсем, почти за 3 копейки, доказать что-то очень похожее на вот это неравенство, а именно теорема, которую мы сейчас с Вами, собственно, и установим, повторяю с помощью банального следствия из формулы Эйлера. Эта теорема утверждает, что хроматическое число, хроматическое число любого плоского графа не больше 6. Вот 4 — это недосягаемая проблема, 5 тоже мог бы доказать. На самом деле, 5 мог бы вполне доказать в рамках этого курса, но это заняло бы больше времени, потребовался бы какой-то перебор, а 6 — это вообще почти за три копейки. Поэтому давайте вот 6 докажем, катарсис получим, возрадуемся и перейдём к каким-то новым темам.
