Карты метро и нейронные сети. Теория графов
Шрифт:
Голоса, отданные "важными" страницами, имеют больший вес. Благодаря им другие страницы тоже становятся "важными".
Эти ценные и высококачественные страницы получают высокий PageRank и располагаются на верхних строчках в результатах поиска. Таким образом, PageRank является общим индикатором важности, присваиваемым Google, и не зависит от поискового запроса. Речь идет скорее о характеристике страницы, получаемой с помощью сложных алгоритмов, оценивающих структуру ссылок».
Графы представляют особый интерес при изучении
Любой, кто изучал органическую химию, знает, как в ней применяются графы. Они используются для представления различных соединений:
В различных инженерных и физических дисциплинах также используются графы, будь то проектирование электрических цепей или интегральных схем, применение которых хорошо известно.
Графы также присутствуют в современных электрических цепях.
* * *
ГРАФ ВЕСОМ В 2400 ТОНН
Для Всемирной выставки 1958 года, проходившей в Брюсселе, был построен Атомиум — впечатляющее сооружение из стали высотой в 102 метра в виде девяти сфер, каждая из которых имеет 18 метров в диаметре, и 20 соединительных трубок. Его архитектора Андре Ватеркейна вдохновил граф, изображающий кристаллическую решетку железа.
* * *
Теория графов играет ключевую роль в различных этапах архитектурных проектов. После того как определены части проекта и перед тем как перейти от эскизов к чертежам, будет крайне полезно построить граф взаимосвязей предварительно определенных элементов проекта. Разумеется, подобные взаимосвязи могут быть самыми разнообразными. Они могут представлять физический доступ (двери), визуальный доступ (окна, стекла), общие стены. Таким образом, для одного и того же множества элементов можно построить различные графы, которые будут отражать различные связи. Рассмотрим несколько простых примеров.
На первом этаже дома на одну семью (дом имеет прямоугольную форму) нужно расположить следующие элементы: кухню (К), столовую (С), зал, или жилую комнату (3), коридор (Ко) и гараж для автомобиля (Г). Между этими помещениями должны существовать проходы из гаража в кухню, из кухни в столовую, из столовой в зал, из зала в коридор и из коридора в гараж.
Если обозначить точками элементы К, С, 3, Ко и Г и соединить некоторые точки ребрами, обозначающими отношение «доступ к», получится граф, в котором четко виден цикл: при таком расположении комнат можно провести путь из любой комнаты в любую. На основе этого графа можно сделать различные эскизы.
Точками также можно обозначить наружное пространство или лестницу. Если речь идет о многоэтажных домах, то каждому этажу можно поставить в соответствие
Анализ графов в общественных зданиях поможет определить степень доступности различных отделов, расположение помещений — буфета, библиотеки, кинозала, а также пожарных лестниц.
После того как построен граф смежности и нарисован эскиз с нанесенными размерами, эскиз можно сопоставить с графом, где оцениваются размеры помещений согласно критерию, который объясняется ниже.
Обратите внимание, что все наши примеры очень просты. Графы особенно интересны при рассмотрении сложных ситуаций: в этом случае они позволяют существенно упростить анализ.
Нужно отметить вершины по числу стен, расположенных на чертеже горизонтально, а также две особые вершины — начальную и конечную. Все дуги графа должны быть направлены сверху вниз. Из каждой вершины выходят дуги, направленные вниз, на которых указываются размеры стен, расположенных на чертеже горизонтально.
На каждой вершине внутри круга указывается расстояние между стеной, соответствующей этой вершине, и следующей стеной, расположенной на чертеже горизонтально. В начальной вершине, точнее на входящем ребре, указывается общая ширина помещений, а внутри круга — их общая длина. В конечной вершине длина должна быть равна нулю, а на исходящем ребре должна быть нанесена общая ширина помещений. Заметим, что граф будет составлен неверно, если сумма значений для ребер, исходящих из данной вершины, будет не равна сумме значений для входящих ребер. Такие графы позволяют проверить правильность внутренних размеров помещений.
Еще один пример графов смежности представлен на следующих иллюстрациях.
Интерес в архитектуре также представляют графы, позволяющие оценить оптимальное расстояние между сообщающимися элементами. Это направление, особый вклад в развитие которого внес Т. Тейбор, описывает в общем виде оптимальное распределение архитектурных элементов, позволяющее сократить пути их обхода.
В небольшом масштабе эта задача не представляет интереса, но в ситуации, когда, например, на одном этаже офисного здания требуется разместить помещения, принадлежащие банку, министерству, администрации города и другим структурам, с помощью анализа стандартных маршрутов можно найти оптимальное расположение помещений, которое поможет упростить взаимодействия между организациями. Например, офисы одинаковой площади можно расположить на этаже в соответствии с одной из следующих пяти схем и эквивалентных им графов смежности.
Изучив расстояния между офисами (здесь мы имеем в виду реальное расстояние, которое нужно пройти, а не евклидово), можно определить, при каком из пяти расположений суммарный путь, который проходят сотрудники всех офисов, минимален. В экспериментах Тейбора использовалась скорость 1,5 м/с при перемещении по этажу и 0,3 м/с при перемещении по лестницам. Подобный принцип используется в урбанистике при проектировании крупных торговых центров и пешеходных зон, регулировании плотности транспортных потоков и для решения других подобных задач.