Том 11. Карты метро и нейронные сети. Теория графов - Клауди Альсина

Эта карта автомобильных дорог 1929 года — прекрасный пример графа.

Иногда подобные графы выглядят еще проще. На следующих рисунках представлены еще две схемы.

Графы на схеме проезда от аэропорта до одной из гостиниц Токио.

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

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

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

* * *

ГРАФ ЛОНДОНСКОГО МЕТРО

В 1909 году управляющий лондонским метрополитеном Фрэнк Пик, который курировал вопросы дизайна, поручил дизайнерам разработку схем метро, которые помогли бы пассажирам перемещаться по сложной сети линий и станций. Многие дизайнеры потерпели неудачу, так как на их схемах не соединенные друг с другом станции изображались поверх карты города, из-за чего пассажирам было непонятно, какую линию метро нужно выбрать. Задачу решил инженер и дизайнер Генри Бек (1903–1974). Гениальность идеи Бека состояла в том, что он упростил схему, сохранив лишь основу графа линий и станций метро. Он расположил линии и станции так, что линии пересекались под углом в 45 или 90°, за счет чего схема становилась очень наглядной. В качестве единственной привязки к местности на схеме осталась только река Темза.

* * *

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

Органиграммы проясняют зависимость, возможные маршруты, альтернативы, которым стоит уделить внимание, алгоритмы, которым нужно следовать. Порядок и четкость — таковы их главные принципы.

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

Если вы хотите спланировать путешествие, то также можете использовать граф, отобразив на нем сроки, затраты, переезды, время ожидания и многое другое. Даже если вы поудобнее устроились на диване и решили прочитать «Остров сокровищ», то и там вам встретится граф, который будет указывать, где лежит заветный клад.

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

* * *

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

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

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

Глава 2

Графы и цвета

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

Марк Твен

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

Карты и цвета

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

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

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

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

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

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

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

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

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

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

При n = 1 (а) доказательство тривиально. Допустим, что это утверждение верно для n прямых (b), и рассмотрим карту, на которой изображена n + 1 прямая (с). Если мы удалим одну из линий, то получим карту из n прямых, которую можно раскрасить двумя цветами (верно по индукции). Следовательно, при добавлении (n + 1)-й прямой вверху (или справа) от добавленной прямой все цвета останутся без изменений, а с другой стороны от этой прямой все области изменят цвет на противоположный. Таким образом, карту из n + 1 прямой можно раскрасить всего двумя красками. С учетом соответствующих различий можно заметить, что любую карту из n окружностей, случайным образом распределенных на плоскости, также можно раскрасить двумя красками. И в случае с прямыми, и в случае с окружностями все вершины полученного графа будут иметь четную степень. В любом графе, вершины которого имеют четную степень, бóльшую двух, при удалении цикла получится граф, вершины которого по-прежнему будут иметь четную степень. Как и все графы такого типа, его можно будет представить в виде прямых или окружностей. Теорема о двух красках доказана.