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

Графы и интернет

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

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

Компьютерные сети могут быть организованы множеством способов. Каждому из них соответствует определенный тип графа: цикл (вверху слева), звезда (вверху справа) или дерево (внизу).

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

Конфигурация сети влияет на ее производительность и функциональные возможности. Необходимо различать графы, соответствующие физическому расположению компьютеров и кабелей, и графы, представляющие собой схему обмена данными между компьютерами (Ethernet, Token Ring и другие), узлы и соединения. Мы находимся на первом этапе эволюции компьютерных систем, и невозможно предугадать, что ждет нас впереди.

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

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

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

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