Документация

Самокольцы и мультиграфы

Графики, созданные с помощью graph и digraph может иметь один или несколько самокольцов, которые являются ребрами, соединяющими узел с самим собой. Кроме того, графы могут иметь несколько рёбер с одними и теми же исходными и целевыми узлами, и тогда граф известен как мультиграф. Мультиграф может содержать или не содержать самокольцы.

Для целей функций алгоритма графов в MATLAB граф, содержащий узел с одним самокольцом, не является мультиграфом. Однако если граф содержит узел с несколькими самокольцами, он является мультиграфом.

Например, на следующем рисунке показан неориентированный мультиграф с самокольцами. Узел A имеет три самокольца, в то время как узел C имеет один. Граф содержит эти три условия, любое из которых делает его мультиграфом.

Чтобы определить, является ли данный граф мультиграфом, используйте ismultigraph функция.

Матрица смежности

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

Например, рассмотрим этот неориентированный график.

График можно представить с помощью этой матрицы смежности:

Чтобы построить график в MATLAB, введите:

A = [0 1 2; 1 0 3; 2 3 0];
node_names = {'A','B','C'};
G = graph(A,node_names)

G = 

  graph with properties:

    Edges: [3×2 table]
    Nodes: [3×1 table]

Вы можете использовать graph или digraph для создания графика с помощью матрицы смежности, или можно использовать adjacency для поиска взвешенной или невзвешенной разреженной матрицы смежности ранее существовавшего графа.

Пограничный список

Другим способом представления информации на графике является перечисление всех рёбер.

Например, рассмотрим тот же неориентированный граф.

Теперь представляем график по списку ребер

Из списка рёбер легко сделать вывод, что граф имеет три уникальных узла, A, B, и C, которые соединены тремя перечисленными ребрами. Если граф имеет отсоединенные узлы, они не будут найдены в списке рёбер и должны быть указаны отдельно.

В MATLAB список ребер разделен столбцами на исходные и целевые узлы. Для направленных графов направление рёбер (от источника к цели) важно, но для неориентированных графов источник и целевой узел взаимозаменяемы. Один из способов построения этого графика с использованием списка ребер состоит в использовании отдельных входных данных для исходных узлов, целевых узлов и весов ребер:

source_nodes = {'A','A','B'};
target_nodes = {'B','C','C'};
edge_weights = [1 2 3];
G = graph(source_nodes, target_nodes, edge_weights);

Оба graph и digraph обеспечение возможности построения простого графа или мультиграфа из списка рёбер. После построения графа G, вы можете посмотреть на края (и их свойства) с помощью команды G.Edges. Порядок ребер в G.Edges сортируется по исходному узлу (первый столбец) и вторично по целевому узлу (второй столбец). Для неориентированных графиков узел с меньшим индексом перечисляется как исходный узел, а узел с большим индексом - как целевой узел.

С момента основополагающего осуществления graph и digraph зависит от разреженных матриц, применяется много одинаковых затрат на индексирование. Использование одного из предыдущих методов для построения графика из трех пар (source,target,weight) быстрее, чем создать пустой граф и итеративно добавить больше узлов и рёбер. Для достижения максимальной производительности сократите число вызовов graph, digraph, addedge, addnode, rmedge, и rmnode.