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

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

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