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

политическая карта

Будем называть две страны соседними, если их границы имеют общие участки линий, а не только отдельные точки.

Такую политическую карту можно рассматривать в виде графа. Рёбра такого графа – это границы соседних стран, вершины – точки пересечения трёх и более стран; сами же территории стран будут являться гранями графа.

Обычно на политических картах принято каждую страну окрашивать в свой цвет. Для удобства моря и океаны можно рассматривать как страны. Чтобы различать соседние страны на карте, достаточно, если они будут раскрашены в разные цвета. Такую раскраску принято называть правильной.

Нетрудно построить карту, для правильной раскраски которой недостаточно трёх цветов.

карта 4-х цветов

Эти три страны пришлось раскрасить в разные цвета, для океана взяли четвёртую краску.

Экспериментально установлено, что для правильной раскраски карты требуется не более 4-х красок. Теоретически это пока не доказано. Но практически никому ещё не удавалось построить такую карту, которую было бы невозможно раскрасить в 4 цвета.

  1. Раскрась правильно карту в два цвета.

раскраска в два цвета

2. Раскрась все грани графа правильно в три цвета.

раскраска в три цвета

3. Граф имеет 9 различных граней. Четыре из них раскрашены. Раскрась остальные грани таким же образом, но при этом соседние грани должны отличаться по раскраске. Пусть при этом голубым будет раскрашено наибольшее число граней.

4 цвета

4. Треугольник разбили на 9 частей. Раскрась его правильно тремя цветами.

треугольник

5. Раскрась граф правильно в 4 цвета.

домик

6. Построй карту, для раскраски которой недостаточно трёх цветов. Пусть твой товарищ раскрасит её в 4 цвета.

7. Раскрась графы наименьшим числом красок.

овал               раскраска

8. Правильная раскраска вершин графа заключается в следующем: две вершины, соединённые одним ребром, должны быть раскрашены в разные цвета.

Раскрась вершины графов в два цвета, если это возможно.

раскраска вершин                       раскраска вершин

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

Попробуй сыграть в эту игру со своим товарищем.

Добавить комментарий


Защитный код
Обновить

Участник Общероссийского рейтинга школьных сайтов

Новости