ГОЛОВОЛОМКИ И ИГРЫ

6.8. Задача соединения раскрашенных кубов [7]

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

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

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

Для любой раскраски кубов определим следующий граф, имеющий 4 вершины и 12 ребер. Вершины соответствуют цветам Для каждого куба существуют три ребра, обозначенные числом Эти ребра соответствуют трем парам противоположных гранен и соединяют соответствующие вершины (цвета).

Раскраска кубов иллюстрируется рис. 6.18 (заметим, что петля соответствует окраске противоположных граней в один цвет). В общем случае, такой граф соответствует допустимой раскраске, если каждая вершина инцидентна, по крайней мере, одному ребру, помеченному любым из чисел 1,2,3 и 4.

Рис. 6.18.

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

Рис. 6.19.

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

(см. скан)