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

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

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

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. 

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