Примеры графов
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.
Этот список далеко не полон — даже для простой классификации его задач. Он просто дает примеры, о которых полезно помнить, когда мы займемся рассмо- трением графов в алгоритмическом контексте.
Еще по теме Примеры графов:
- Примеры жестокости по отношению к другим (эти примеры более всего относятся к семейной жизни):
- ПРИМЕР 2
- Пример 1.
- ПРИМЕР 2
- Пример 2.
- Пример 2.
- Пример 2.
- Пример.
- ПРИМЕР
- Действенность примеров
- ПРИМЕР 2
- Пример 4.
- Заключение по примерам
- Пример «чуда».