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

Обозначим за n число прямоугольников, на которые мы хотим разбить квадрат. Было подсчитано, что для n = 1, 2, 3, 4, 5 и 6 существует соответственно 1, 1, 2, 7, 22 и 117 различных способов разбиения, которые не являются топологически эквивалентными.

Для n >= 7 эта задача до сих пор не решена. По некоторым оценкам,

для n = 7 существует около 700 решений, для n = 8 — примерно 10000, для n = 9 — порядка 250000 решений, но корректность подобной экстраполяции пока не подтверждена). Сегодня ученые занимаются поиском компьютерных алгоритмов решения этой задачи.

* * *

Графы в урбанистике

Кристофер Александер — известный американский архитектор и преподаватель, который в 70-е годы XX века развил идею о том, как графы, компьютерные программы и вычислительные мощности помогут рационализировать урбанистику и анализ архитектурных проектов. В его книге «Заметки о синтезе формы», которая приобрела огромную популярность, при анализе форм использовались графы. Особенно важной стала его статья «Город — не дерево», в которой, используя деревья из теории графов в качестве метафоры, Александер рассуждает на тему роста городов и озвучивает следующую гипотезу:

«Думаю, что естественно развивающийся город имеет структуру полурешетки… Искусственно спланированные города по структуре напоминают дерево».

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

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

Классические примеры древовидных городов — это Большой Лондон Лесли Патрика Аберкромби и Джона Форшоу, план Токио авторства Кэндзо Тангэ, план города Бразилиа архитектора Лусио Косты, план Чандигарха, созданный Ле Корбюзье, и другие.

План Токийского залива авторства японского архитектора Кэндзо Тангэ (1960).

Александер пришел к выводу, что структура города должна быть сложнее, чем древовидная:

«В представлении человека дерево — это самое простое средство представления сложных планов. Но город не является, не может и не должен быть деревом. Город — это вместилище жизни».

Графы в социальных сетях

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

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

Изучение социальных сетей восходит к XIX веку. Здесь можно вспомнить Эмиля Дюркгейма и Фердинанда Тенниса. В начале XX века это направление интенсивно развивалось усилиями Георга Зиммеля. В первых исследованиях на эту тему рассматривались такие темы, как трудовые отношения между группами и отдельными работниками, отношения между культурными сообществами и так далее. Во второй половине XX столетия эти исследования охватили все сферы общества. Этой темой занимались группы ученых из Гарвардского (Харрисон Уайт, Толкотт Парсонс), Калифорнийского (Линтон Фриман), Чикагского, Торонтского и других университетов.

Анализ социальных сетей использовался при изучении распространения болезней (СПИДа, малярии, туберкулеза), инноваций, анализе воздействия политических решений и даже при изучении распространения слухов.

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

* * *

ДРУЗЬЯ ПОЛИТИКА

В математическом фольклоре эта задача известна уже много лет. Допустим, что в группе людей, состоящей как минимум из трех человек, у любых двух ее членов есть ровно один общий друг. Следовательно, всегда существует человек (так называемый политик), который будет другом всех членов группы. Пол Эрдёш и Альфред Реньи формализовали и решили эту задачу с помощью графов: если граф имеет n вершин (n >= 3) и для любой пары вершин существует вершина, смежная им обеим, то должна существовать вершина, смежная всем вершинам графа.

* * *

«Маленький мир» Стэнли Милгрэма

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

Графы и расписания

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

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

Рассмотрим последовательность повседневных действий, например покупку продуктов в нескольких магазинах и приготовление ужина. При выполнении этих действий можно следовать такому алгоритму.

1. Пронумеровать все задачи и оценить сроки их выполнения.

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

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

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