Примеры графов

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

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

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

1. Транспортные сети. Карта маршрутов компании-авиаперевозчика естественным образом образует граф: узлы соответствуют аэропортам, а ребро из узла u в v существует при наличии беспосадочного перелета с вылетом из u и посадкой в v.

При таком описании граф является направленным; тем не менее на практике при существовании ребра (u, v) почти всегда существует ребро (v, u), поэтому мы практически ничего не потеряем, если будем рассматривать карту маршрутов как ненаправленный граф с ребрами, которые соединяют пары аэропортов, связанные беспосадочными перелетами.

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

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

2. Коммуникационные сети. Граф может рассматриваться как естественная модель компьютеров, объединенных в сеть передачи данных. Существуют разные способы такого моделирования. Во-первых, каждый узел может представлять компьютер, а ребро, соединяющее узлы u и v, — прямой физический канал, связывающий эти компьютеры.

Кроме того, для описания крупномасштабных структур в Интернете узел часто определяется как группа машин, обслуживаемых одним интернет-провайдером; узлы u и v соединяются ребром, если между ними существует прямая одноранговая связь — проще говоря, соглашение о передаче данных по стандартному протоколу BGP, управляющему глобальной маршрутизацией в Интернете.

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

При анализе беспроводных сетей обычно определяется граф, узлы которого представляют собой устройства, расположенные в разных местах физического пространства, а ребро из u в v существует в том случае, если узел v находится достаточно близко к u для приема сигнала.

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

3. Информационные сети. Всемирная паутина может естественным образом рассматриваться как направленный граф, в котором узлы соответствуют вебстраницам, а ребро из u в v существует в том случае, если в u присутствует гиперссылка на v.

Направленность графа здесь принципиальна; например, многие страницы содержат ссылки на популярные сайты новостей, тогда как на этих сайтах, естественно, обратных ссылок нет. Структура, сформированная всеми гиперссылками, может использоваться алгоритмами для определения самых важных страниц — эта методика применяется многими современными поисковыми системами.

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

4. Социальные сети. Для любой группы людей, общающихся друг с другом (работники одной компании, студенты, жители небольшого городка), можно определить сеть, узлы которой представляют людей, а ребро между u и v существует в том случае, если они являются друзьями.

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

Также легко представить двудольную социальную сеть, основанную на концепции принадлежности: для множества X людей и множества Y организаций ребро между u Ѯ X и v Ѯ Y определяется в том случае, если u принадлежит организации v.

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

Сети зависимостей. Модель направленного графа естественно подходит для отражения взаимозависимостей в группах объектов. Например, для учебного плана в колледже или университете каждый узел может представлять учебный курс, а ребро из u в v существует в том случае, если u является предпосылкой для v.

Для списка функций или модулей крупной программной системы узел может представлять функцию, а ребро из u в v существует в том случае, если u вызывает v. Или для множества видов в экосистеме можно определить граф (пищевую сеть), в которой узлы представляют разные виды, а ребро из u в v означает, что вид u питается представителями вида v.

Этот список далеко не полон — даже для простой классификации его задач. Он просто дает примеры, о которых полезно помнить, когда мы займемся рассмотрением графов в алгоритмическом контексте.