О Ёлках, графах и юных математиках

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

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

К сожалению, у Миши не очень хорошо получается определять «гармоничность» внешнего вида елки, но Миша – юный математик, а значит, любая задача ему по плечу. В коробке оказалось множество красных и синих шариков, а вот украшений других цветов было значительно меньше. Миша задумался: получится ли у него использовать только красные и синие шарики? Разместить их на елке… А что такое елка в этой задаче? И какие шарики на ней будут считаться соседними?

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

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

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

Миша задумчиво посмотрел на елку еще раз. С математической точки зрения она представляла собой граф-дерево – без циклов. Получалось, что устроена елка довольно просто, а значит, и раскрасить – то есть, украсить – ее должно было быть просто. Почему бы и не попробовать обойтись всего двумя цветами? Начнем с простейшего – будем чередовать цвета и раскрашивать узлы по принципу «красный-синий-красный-синий». Если это удастся, то задача решена. Но почему это должно работать?

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

Разумеется, Миша строго придерживался инструкций. Задача была решена, и у него получилась вот такая елочка – обязательно проверьте, как он справился:

Теперь Миша уверен: всего двух цветов достаточно, чтобы раскрасить елку так, как хотела мама. А вот и она – возвращается в гостиную! Как думаете, ей понравится такое цветовое решение?