Том 11. Карты метро и нейронные сети. Теория графов

ГРАФЫ И ИСКУССТВО

С рождением абстрактного искусства художники и скульпторы начали постепенно переходить от изображения людей, предметов и пейзажей к анализу форм и цветов, представляющих формальные абстрактные связи между вещами и явлениями. Произошла смена парадигмы: идеал эпохи Возрождения, где картина являла собой окно в реальный мир, сменился сюрреалистичным представлением: «картину создает зритель». Начиная с работ, например, Василия Кандинского (1866–1944) и Тео ван Дусбурга (1883–1931), имевших большое влияние, основные цвета и базовые геометрические фигуры начали набирать силу в искусстве, пробуждая эмоции, изображая красоту, при этом не отражая реальность. Точки и линии (и снова графы!) стали основными элементами искусства.

«Диссонансная контркомпозиция № 16» Тео ван Дусбурга.

Глава 2 Графы и цвета

Иллинойс зеленый, а Индиана розовая… Я сам видел на карте, что она розовая.

Марк Твен

В этой главе мы приглашаем читателя подумать над одной задачей теории графов, которая кажется очень простой. Это задача о раскраске карт. Вы увидите, как одна занимательная задача иногда может вызвать подлинный прорыв в науке.

Карты и цвета

Большинство географических карт можно интерпретировать как графы, вершинами которых являются точки, где сходятся три линии и более, а ребрами — границы стран и территорий. Составители карт пытались раскрасить их так, чтобы разные страны и территории были окрашены в разные цвета. Учитывая число стран и ограниченное количество цветов, которые использовались при цветной печати, требовалось раскрасить карты так, чтобы в разные цвета были окрашены только страны с общими границами. Естественно, возник вопрос: какое минимальное число цветов необходимо, чтобы все страны с общими границами были окрашены в разные цвета? (Подразумевается, что точка не является границей.) Так как существует множество различных карт (карты стран, регионов, промышленных районов и так далее), то очевидно, что задачу нужно сформулировать в общем виде с помощью графов. Иными словами, нужно рассматривать карты, описывающие произвольный плоский граф.

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

Заметим, что если мы также захотим раскрасить и внешнюю область, то нам понадобится соответственно 2, 3, 4 и… снова 4 цвета.

Следующие фигуры более сложны.

Сразу же становится понятно, что для их раскраски достаточно четырех цветов.

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

Раскраска графа в два или три цвета

Как выглядят карты (плоские графы), для раскраски которых достаточно всего двух цветов? А трех цветов? Ответ на эти вопросы нетруден, и его можно найти довольно быстро. Обратимся к теореме о двух красках, которая гласит: «Карту можно раскрасить двумя цветами тогда и только тогда, когда в соответствующем ей графе все вершины имеют четную степень».

Любопытно, что если карту можно раскрасить двумя цветами, то все вершины соответствующего графа будут иметь четную степень. Если в нем будет хотя бы одна вершина с нечетной степенью, то как минимум одна грань графа будет граничить с двумя гранями и для раскраски понадобится уже три цвета. Чтобы доказать обратное утверждение, нужно выполнить несколько действий. Сначала докажем, что если мы проведем на плоскости n линий случайным образом, то полученную карту можно будет раскрасить всего двумя красками (вспомните, например, шахматную доску).

Используем метод доказательства по индукции, который заключается в том, что мы докажем это утверждение для n = 1 и посмотрим, будет ли верным это утверждение для n + 1, если оно верно для n.