Хотя узлы и ребра могут иметь любое количество интересных свойств и меток, некоторые свойства встречаются чаще, чем другие. В частности, есть два свойства ребер, которые настолько выделяются, что, как говорят, меняют тип графа. Эти два свойства - вес и направленность кромки.
Если рёбра вашего графа имеют направленность, то ваш граф называется направленным графом (иногда его сокращают до орграфа). В ориентированном графе все ребра представляют одностороннее отношение, это отношение от одного узла к другому узлу, но не в обратном направлении . В неориентированном графе все ребра двунаправлены. По-прежнему возможно (даже часто) иметь двунаправленные отношения в ориентированном графе, но эти отношения включают в себя два ребра вместо одного, ребро от A до B и другое ребро от B до A.
Направленные ребра оказывают незначительное влияние на использование термина соседи. Если ребро идет от A к B, то B считается соседом A; но обратное не правда. A не является соседом B, если не существует ребра от B до A. Другими словами, соседи узла - это набор узлов. к которому можно добраться из этого узла.
В качестве примера возьмем две социальные сети. На Facebook граф друзей неориентированный. Если вы чей-то друг на Facebook, он тоже ваш друг - дружба на Facebook всегда двунаправленная, что означает, что графическое представление ненаправленное. В Твиттере, однако, «следовать» за кем-то - это односторонние отношения. Если вы подписаны на Бейонсе, это не значит, что она следует за вами. График пользователей Twitter и их подписчиков - это направленный график.
Если ребра в вашем графе имеют веса, то ваш граф называется взвешенным графом, если ребра не имеют весов, граф называется невзвешенным. . Вес - это числовое значение, присваиваемое каждому отдельному краю. В взвешенном графе отношения между узлами имеют величину, и эта величина важна для отношений, которые мы изучаем. В невзвешенном графике существование отношений является предметом нашего интереса.
В качестве примера взвешенного графика представьте, что вы управляете авиакомпанией и вам нужна модель, которая поможет вам оценить расходы на топливо на основе маршрутов, по которым вы летите. В этом примере узлами будут аэропорты, ребра будут представлять рейсы между аэропортами, а вес ребра будет оценочной стоимостью полета между этими аэропортами. Такую модель можно использовать для определения самого дешевого маршрута между двумя городами или для моделирования различных потенциальных предложений полетов.
Невзвешенный график может использоваться, потому что не существует взаимосвязи по величине. Например, граф, представляющий курсы колледжа и их предпосылки, обладает этим свойством: узлы - это курсы, а ребра - обязательные отношения между двумя классами. Если конкретный курс имеет два предварительных условия, неправильно говорить, что один курс больше предварительных требований, чем другой, вам просто нужно пройти оба предварительных курса, прежде чем проходить этот курс.
Иногда график будет невзвешенным, даже если отношения явно имеют связанную величину. Возможно, это потому, что трудно получить данные о масштабах отношений; возможно, это потому, что само существование отношений достаточно интересно; возможно, есть какая-то другая причина. Например, исследователь может сначала построить более простую (невзвешенную) модель, прежде чем принять решение о добавлении сложности (весов). Снова рассмотрим социальные сети. В целом верно, что человек ближе к одним друзьям, чем к другим. Веса краев можно использовать для представления этой относительной близости, но близость является субъективной и трудно получить данные.
Можете ли вы представить, если бы Facebook спросил вас: «По шкале от 1 до 10, насколько вы близки с этим человеком?» каждый раз, когда вы добавляли нового друга? Для большинства людей это было бы жутко, агрессивно и неудобно. Кроме того, шкала от 1 до 10 у всех будет разной. Эти данные было бы трудно получить, так как они противоречивы; более того, существование дружбы интересно само по себе. Оценка этого социального графика, вероятно, не стоит усилий.
Другая причина использовать или не использовать веса зависит от типа вопроса, на который вы хотите ответить. Например, рассмотрим граф, в котором ребра представляют собой дороги, а узлы - перекрестки. Далее рассмотрите эти два вопроса:
- «Есть ли дороги на перекрестках A и B?» а также,
- «Какой самый короткий маршрут между перекрестками A и B?»
Если мне нужно ответить только на первый вопрос, я могу сэкономить время и силы, используя невзвешенный график. Если мне нужно ответить на второй вопрос, мне нужно будет найти способ утяжелить края - возможно, используя длину каждой дороги или длину дороги, деленную на ограничение скорости на этой дороге.
Когда вы начинаете любой проект, использующий теорию графов, вы должны определить, какой тип графа вы собираетесь использовать. Используя две категории, которые мы здесь обсуждали, у нас остается 4 основных типа графиков:
- Ненаправленные и невзвешенные: отношения не имеют величины и являются двунаправленными.
- Ненаправленные и взвешенные: отношения имеют величину и двунаправлены.
- Направленные и невзвешенные: отношения не имеют значения и являются односторонними.
- Направленные и взвешенные: отношения имеют значение и односторонние.
У каждого типа графа есть свои сильные и слабые стороны. Иногда эти недостатки делают один тип графа плохим выбором - например, существование дорог с односторонним движением и разделенных автомагистралей делает неориентированный граф плохим выбором для изучения схем движения. В других случаях выбор будет более неоднозначным, например, ранее обсуждавшееся решение взвесить края социальных сетей с помощью показателя «близости» или нет.
Выбор подходящего типа графика для моделирования вашей проблемы не всегда зависит от того, какая модель верна или неверна. Любимая шутка статистиков относится и к теории графов: все модели неверны, но некоторые полезны. При принятии решения о том, как использовать график для моделирования ваших проблем, рассмотрите возможность поэкспериментировать с различными типами и взвесить компромиссы, связанные как со сбором данных для построения модели, так и с различиями, которые могут появиться при анализе этих различных моделей.
Следующая статья из серии: Моделирование задач в виде графиков
