Карты метро и нейронные сети. Теория графов
Шрифт:
Конечные геометрии
Представьте себе плантацию, где в несколько рядов высажены деревья или другие растения. Очевидно, что их можно представить в виде графа, имеющего множество изолированных вершин, не соединенных ребрами. Предположим, что мы хотим составить схему полетов небольшого самолета, который будет опрыскивать посадки, или же возможный маршрут сбора плодов. Такой маршрут укажут ребра графа.
Множество задач подстегнули интерес к конечным геометриям — геометрическим системам, имеющим конечное количество точек и линий, которые представляют собой некие совокупности этих точек.
На
Подобно тому как в традиционной геометрии с бесконечным множеством точек и линий можно сформулировать ряд аксиом, подобных аксиомам Евклида, так и в конечной геометрии можно ввести различные аксиомы и говорить о пересечениях (общих точках) и параллельных линиях (линиях без общих точек).
Рассмотрим пример системы аксиом конечной геометрии.
I. Существует пять точек и две линии.
II. Каждая линия содержит минимум две точки.
III. Каждая линия содержит не более трех точек.
В соответствии с этими правилами можно описать возможные расположения точек и линий. Вместо того чтобы описывать полученные множества символами и словами, их можно представить намного проще. Для этого нужно построить все возможные графы с пятью вершинами и соответствующими ребрами. На следующем рисунке представлены все возможные варианты.
Чтобы оценить практическое значение этого примера, представьте, что точки — члены дирекции объединения, линии — комитеты, образованные двумя или тремя членами дирекции. Переформулируем вышеприведенные аксиомы в категориях директоров и комитетов.
I. Существует пять человек и два комитета.
II. Каждый комитет содержит минимум двух членов.
III. Каждый комитет содержит не более трех членов.
Очевидно, что этот пример можно усложнить, добавив новые точки и линии.
* * *
КЛАССИФИКАЦИИ И ИЕРАРХИИ
В классической геометрии особое внимание уделяется классификации фигур (например, по количеству сторон в них). Задачи о классификации становятся все более важными в самых разных областях: можно говорить о классификации фигур с помощью компьютерного зрения, классификации генов, симптомов болезней и так далее. Задачи о классификации появляются в сфере информационной безопасности (цифровые отпечатки пальцев, радужной оболочки глаза, распознавание голоса), на производстве, где при контроле качества бракованные детали автоматически определяются и исключаются из производственной цепочки, и в других областях.
Если речь идет о конечных множествах, то отношение всегда задается множеством пар элементов. Отношения можно изображать в виде диаграмм или графов, вершины которых будут соответствовать элементам множества, ребра — отношениям между ними. Отношения, на основе которых можно сформировать классификацию, называются отношениями эквивалентности. Они обладают следующими свойствами:
— рефлексивностью (каждый элемент эквивалентен сам себе);
— симметричностью (если а связано с b, то b связано с а);
— транзитивностью (если а связано с b и b связано с с, то а связано с с).
Граф, включающий подобные отношения, должен наглядно отражать эти свойства.
Еще один тип отношений — это отношения порядка, которые используются для упорядочивания элементов и обладают свойствами рефлексивности, транзитивности и антисимметричности (если а связано с b и b связано с а, то а = Ь). Графы, соответствующие отношениям порядка на конечных множествах, могут быть ориентированными (дуги будут указывать, какой из двух соединенных ими элементов меньше) или неориентированными (в этом случае элементы будут расположены по порядку снизу вверх). Интерес также представляют иерархические процессы, в которых необходимо определять приоритеты и порядок выполнения определенных работ (инвестиции, строительство, предоставление коммунальных услуг и так далее).
Глава 5
Живительные способы применения графов
Если люди отказываются верить в простоту математики, то это только потому, что они не понимают всей сложности жизни.
Джон фон Нейман
В этой книге мы уже рассказали о многих способах применения графов. В этой последней главе мы вкратце расскажем о том, где еще используются графы. Вы увидите, что они применяются не только в картах, маршрутах и генеалогических деревьях. Надеемся, что после прочтения этой главы в вас пробудится интерес к теории графов и вы продолжите изучать этот раздел математики самостоятельно.
Неоднократно говорилось, что название «каменный век» не совсем точно: было бы точнее говорить о «веревочном веке». Важно не то, что древние люди использовали камни в качестве инструментов, а то, что они догадались привязать камень к палке веревкой. В наше время благодаря интернету — «сети сетей», связывающей компьютеры и серверы по всему миру, стала возможной цифровая революция. Мощность компьютеров неуклонно возрастала (одновременно с уменьшением их размеров), но совершить гигантский скачок к цифровому миру удалось именно благодаря сетям. Графы и телекоммуникации всегда шли рука об руку.
Несмотря на то что человеческий гений создал первые абаки и легендарные счетные машины, нельзя было и предположить, что такие сложные дисциплины, как кибернетика и информатика, столь быстро ворвутся в сложный и запутанный мир коммуникаций. Этот огромный скачок был совершен очень быстро.
Компьютерные сети могут быть организованы множеством способов. Каждому из них соответствует определенный тип графа: цикл (вверху слева), звезда (вверху справа) или дерево (внизу).
На рисунке выше изображены различные схемы соединения компьютеров между собой. Каждый схеме соответствует граф (цикл, дерево, звезда и другие), поэтому применяется термин «сетевая топология».
Конфигурация сети влияет на ее производительность и функциональные возможности. Необходимо различать графы, соответствующие физическому расположению компьютеров и кабелей, и графы, представляющие собой схему обмена данными между компьютерами (Ethernet, Token Ring и другие), узлы и соединения. Мы находимся на первом этапе эволюции компьютерных систем, и невозможно предугадать, что ждет нас впереди.
Технология, которая изначально предназначалась для отправки электронной почты в военных целях, вышла на уровень университетов, а затем охватила всю планету. Появление глобальной сети и поисковых механизмов позволило проникнуть в этот сложный информационный мир, путь в котором нам указывают гиперссылки. Граф, образуемый гиперссылками, имеет невероятные размеры и постоянно увеличивается.
Сегодня с помощью поискового механизма, например Google, можно получить доступ к невиданным ранее объемам информации. Чтобы избежать путаницы, Google использует поискового робота (Googlebot) и сложные алгоритмы упорядочивания результатов поиска. Следующее описание, которое приводится самим Google, помогает в подробностях представить, как взвешиваются и упорядочиваются результаты поиска, которые вы видите на своем мониторе, с помощью алгоритма PageRank: «Алгоритм PageRank использует в высшей степени демократичную характеристику сети, применяя для организации страниц обширную структуру гиперссылок. По сути, Google считает ссылку со страницы А на страницу В как голос страницы А, отданный за страницу В. Google оценивает важность страницы по числу полученных ею голосов. Но Google учитывает не только число голосов или ссылок. Также анализируется страница, которая "отдает" свой голос.