Типы графов
Граф (graph) [1] представляет собой структуру данных, состоящую из узлов (называемых также вершинами графа, nodes, vertices) , некоторые из которых соединены рёбрами (связями, edges) .
Рассмотрим основные виды графов и их обобщения, а также описание геометрии графов в виде матриц смежности и матриц степеней.
Ненаправленный граф
В ненаправленном графе (или неориентированном, undirected graph) рёбра не имеют направления.
Пример ненаправленного графа приведён ниже:
В нём 5 вершин и 5 ребер и .
Примеры данных, описываемых ненаправленным графом:
-
молекула, в которой узлами являются атомы, а рёбрами - химические связи;
-
электрические схемы, в которых узлами являются элементы схемы, а рёбрами - провода между ними;
-
социальная сеть, где узлами выступают пользователи, а рёбрами - отношения взаимной дружбы между ними;
-
туристическая карта, в которой узлами выступают локации, а рёбрами - тропинки между ними.
Направленный граф
В направлен ном графе (или ориентированном, directed graph) рёбра имеют направления. Для каждого ребра известно, из какой вершины оно выходит и в какую приходит.
Пример направленного графа приведён ниже:
Примеры данных, описываемых направленным графом:
-
социальная сеть, где узлами выступают пользователи, а рёбрами - их подписки на новости друг друга;
-
система передачи данных, где узлами обозначаются элементы системы, а рёбрами - потоки данных между ними;
-
логистическая сеть, где узлами являются перекрёстки, а рёбрами - направления движения на дорогах.
Смешанный граф
Смешанный граф (mixed graph) содержит как направленные, так и ненаправленные рёбра.
Примеры данных, описываемых смешанным графом:
-
транспортные сети, где узлами выступают перекрёстки, а рёбрами - связи односторонними и двустор онними дорогами;
-
энергетические системы, где узлами выступают станции перераспределения, генераторы и потребители, а связями - линии передачи энергии.
Далее, для простоты, будут рассматриваться только ненаправленные графы, хотя приводимые выводы можно обобщить и для направленных и смешанных графов.
Ассоциированные данные
Каждой вершине графа может быть сопоставлен свой -мерный вектор признаков :
Аналогично каждому ребру может сопоставляться свой вектор данных:
Также всему графу целиком может сопоставляться вектор данных , описывающий весь граф.
Визуально это можно представить следующим образом:
Чаще всего рассматриваются только данные, ассоциированные узлам, которые можно объединить в матрицу , в которой -му столбцу соответствует вектор данных , отвечающий узлу .
Граф рёбер
По исходному графу можно построить сопряжённый граф рёбер (edge graph), в котором
-
каждая связь исходного графа становится узл ом;
-
узлы сопряжённого графа соединяются, если соответствующие им рёбра имеют общий узел в исходном графе.
Пример (a) исходного графа (b) выделения рёбер в узлы и (c) сопряжённого графа рёбер приведён ниже [2]:
По сопряжённому графу рёбер можно обратно восстановить исходный граф.
Мультиграфы
Cуществуют структуры данных, описываемые мультиграфами (multigraph), в которых узлы могут соединяться рёбрами разных типов, обозначенными в примере цветом:
Примеры данных, описываемых мультиграфом:
-
социальная сеть, в которой узлы - пользователи, которые могут вступать в разные виды взаимодействия (ставить лайки, писать комментарии, подписываться друг на друга);
-
логистическ ая сеть, где узлы - локации, по которым можно перемещаться, используя разный вид транспорта (на автобусе, метро или самолёте).
Гетерогенные графы
Гетерогенные графы (heterogeneous graph) - это графы, состоящие из узлов разных типов. Ниже приведён пример гетерогенного мультиграфа, на котором тип узлов и тип связей обозначен цветом:
Примеры данных, описываемых гетерогенным графом:
-
торговая система, в которой узлами выступают пользователи, товары и продавцы, взаимодействующие друг с другом;
-
граф знаний, в котором узлами являются персоны, компании, страны и события, связанные друг с другом.
Матрица смежности
Рёбра графа из вершин описываются матрицей смежности (adjency matrix) .
Ненаправленный граф
Для ненаправленного графа элементы матрицы смежности формируются по правилу:
Рассмотрим граф:
Для него матрица смежности будет
Эта матрица будет симметричной (), поскольку если соединены ребром, то в ненаправленном графе ребром соединены и .
Направленный граф
Для направленного графа элементы матрицы смежности формируются по правилу:
Рассмотрим граф:
Для него матрица смежности будет
Как видим, для направленного графа матрица смежности уже не будет симметричной.
Свойство матрицы смежности
Если - one-hot закодированная вершина , то