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

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

Современное генеалогическое древо царской семьи Романовых, составленное на компьютере, и генеалогическое древо семейства Ругон-Маккаровиз произведений писателя Эмиля Золя, составленное в 1878 году.

ГРАФ МАТЕМАТИЧЕСКИХ СВЯЗЕЙ

По адресу http://genealogy.math.ndsu.nodak.eduнаходится страница математического генеалогического проекта (Mathematics Genealogy Project), на которой собраны данные о математиках и их «потомках» — тех ученых, которые защитили докторскую диссертацию под их руководством. Проект непрерывно пополняется данными о все новых и новых диссертациях, и постепенно формируется дерево взаимосвязей между всеми математиками. По состоянию на апрель 2010 года были собраны данные о 140 982 математиках.

Главная страница проекта Mathematics Genealogy Project

* * *

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

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

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

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

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

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

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

* * *

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

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

* * *

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

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

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

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

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