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

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

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

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

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

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

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

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

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

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

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Примеры графов:

  1. Примеры жестокости по отношению к другим (эти примеры более всего относятся к семейной жизни):
  2. ПРИМЕР 2
  3. Пример 1.
  4. ПРИМЕР 2
  5. Пример 2.
  6. Пример 2.
  7. Пример 2.
  8. Пример.
  9. ПРИМЕР
  10. Действенность примеров
  11. ПРИМЕР 2
  12. Пример 4.
  13. Заключение по примерам
  14. Пример «чуда».