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

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

Сегодня с помощью поискового механизма, например Google , можно получить доступ к невиданным ранее объемам информации. Чтобы избежать путаницы, Google использует поискового робота ( Googlebot ) и сложные алгоритмы упорядочивания результатов поиска. Следующее описание, которое приводится самим Google , помогает в подробностях представить, как взвешиваются и упорядочиваются результаты поиска, которые вы видите на своем мониторе, с помощью алгоритма PageRank : «Алгоритм PageRank использует в высшей степени демократичную характеристику сети, применяя для организации страниц обширную структуру гиперссылок. По сути, Google считает ссылку со страницы Ана страницу Вкак голос страницы А, отданный за страницу В. Google оценивает важность страницы по числу полученных ею голосов. Но Google учитывает не только число голосов или ссылок. Также анализируется страница, которая "отдает" свой голос.

Голоса, отданные "важными" страницами, имеют больший вес. Благодаря им другие страницы тоже становятся "важными".

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

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

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

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

Графы также присутствуют в современных электрических цепях.

* * *

ГРАФ ВЕСОМ В 2400 ТОНН

Для Всемирной выставки 1958 года, проходившей в Брюсселе, был построен Атомиум — впечатляющее сооружение из стали высотой в 102 метра в виде девяти сфер, каждая из которых имеет 18 метров в диаметре, и 20 соединительных трубок. Его архитектора Андре Ватеркейна вдохновил граф, изображающий кристаллическую решетку железа.

* * *

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

На первом этаже дома на одну семью (дом имеет прямоугольную форму) нужно расположить следующие элементы: кухню ( К ), столовую ( С ), зал, или жилую комнату ( 3 ), коридор ( Ко ) и гараж для автомобиля ( Г ). Между этими помещениями должны существовать проходы из гаража в кухню, из кухни в столовую, из столовой в зал, из зала в коридор и из коридора в гараж.

Если обозначить точками элементы К, С, 3, Ко и Г и соединить некоторые точки ребрами, обозначающими отношение «доступ к», получится граф, в котором четко виден цикл: при таком расположении комнат можно провести путь из любой комнаты в любую. На основе этого графа можно сделать различные эскизы.