Карты метро и нейронные сети. Теория графов
Шрифт:
* * *
ОТКРЫТЫЙ ВОПРОС
В теории графов применительно к архитектуре остается открытым вопрос о разбиении квадрата на прямоугольники горизонтальными и вертикальными линиями и определении всех возможных разбиений для каждого конкретного случая. Отметим, что цель задачи — найти не все возможные конечные графы, а только те, которые соответствуют допустимым разбиениям на плоскости.
Обозначим за 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 году психолог Стэнли Милгрэм провел эксперимент, подтвердивший концепцию «маленького мира». Несколько человек попросили передать сообщение (например, письмо) определенным людям по цепочке через своих знакомых. В большинстве случаев сообщение удалось передать получателю за шесть шагов. Этот эксперимент проводился неоднократно, и всякий раз число звеньев в подобных цепочках оказывалось очень малым (пять, шесть, восемь). Эта тема вновь обрела популярность с появлением гиперссылок и электронной почты.