Примеры графов
Определить граф проще простого: возьмите набор объектов и соедините их ре- брами. Но на таком уровне абстракции трудно представить типичные ситуации, в которых встречается работа с графами. По этой причине мы предлагаем список распространенных контекстов, в которых графы играют важную роль как модель.
Список получился достаточно обширным, не пытайтесь запомнить все его пункты; скорее это перечень полезных примеров для проверки базовых определений и ал- горитмических задач, которые встретятся нам позднее в этой главе.
- Транспортные сети. Карта маршрутов компании-авиаперевозчика естествен- ным образом образует граф: узлы соответствуют аэропортам, а ребро из узла u в v существует при наличии беспосадочного перелета с вылетом из u и посадкой в v.
При таком описании граф является направленным; тем не менее на практике при существовании ребра (u, v) почти всегда существует ребро (v, u), поэтому мы практически ничего не потеряем, если будем рассматривать карту марш- рутов как ненаправленный граф с ребрами, которые соединяют пары аэропор- тов, связанные беспосадочными перелетами.
При рассмотрении такого графа (который обычно изображается на задней обложке журналов для пассажиров) можно быстро заметить несколько подробностей: часто в графе присутствует небольшое количество «центров» с очень большим количеством инцидентных ребер; и от одного узла графа можно перейти к любому другому узлу за очень небольшое количество промежуточных пересадок.
Другие транспортные сети тоже могут моделироваться подобным образом. На- пример, в железнодорожной сети каждый узел может представлять станцию, а ребро, соединяющее узлы u и v, — железнодорожный путь, соединяющий эти станции без промежуточных остановок. Стандартная схема метро в крупном городе представляет собой изображение такого графа.
- Коммуникационные сети. Граф может рассматриваться как естественная мо- дель компьютеров, объединенных в сеть передачи данных. Существуют разные способы такого моделирования. Во-первых, каждый узел может представлять компьютер, а ребро, соединяющее узлы u и v, — прямой физический канал, связывающий эти компьютеры.
Кроме того, для описания крупномасштабных структур в Интернете узел часто определяется как группа машин, обслуживае- мых одним интернет-провайдером; узлы u и v соединяются ребром, если между ними существует прямая одноранговая связь — проще говоря, соглашение о передаче данных по стандартному протоколу BGP, управляющему глобальной маршрутизацией в Интернете.
Следует заметить, что вторая модель «виртуаль- нее» первой, потому что связи представляют собой формальное соглашение наряду с физической линией связи.
При анализе беспроводных сетей обычно определяется граф, узлы которого представляют собой устройства, расположенные в разных местах физического пространства, а ребро из u в v существует в том случае, если узел v находится достаточно близко к u для приема сигнала.
Такие графы часто удобно рас- сматривать как направленные, потому что может оказаться, что v может вос- принимать сигнал u, а u не может воспринимать сигнал v (например, потому что на u установлен более мощный передатчик). Эти графы также интересны с геометрической точки зрения, потому что они приблизительно соответ- ствуют размещению точек на плоскости с последующим соединением близко расположенных пар.
- Информационные сети. Всемирная паутина может естественным образом рассматриваться как направленный граф, в котором узлы соответствуют веб- страницам, а ребро из u в v существует в том случае, если в u присутствует гипер- ссылка на v.
Направленность графа здесь принципиальна; например, многие страницы содержат ссылки на популярные сайты новостей, тогда как на этих сайтах, естественно, обратных ссылок нет. Структура, сформированная всеми гиперссылками, может использоваться алгоритмами для определения самых важных страниц — эта методика применяется многими современными поис- ковыми системами.
Гипертекстовой структуре Всемирной паутины предшествовали информацион- ные сети, появившиеся за много десятков лет до Интернета, такие как сети пере- крестных ссылок между статьями в энциклопедиях или других справочниках или сети библиографических ссылок в научных статьях.
- Социальные сети. Для любой группы людей, общающихся друг с другом (ра- ботники одной компании, студенты, жители небольшого городка), можно опре- делить сеть, узлы которой представляют людей, а ребро между 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.
Этот список далеко не полон — даже для простой классификации его задач. Он просто дает примеры, о которых полезно помнить, когда мы займемся рассмо- трением графов в алгоритмическом контексте.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу