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

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

Графики, созданные с помощью 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.