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

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

Графики, созданные с помощью 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 функционируйте, чтобы найти взвешенную или невзвешенную разреженную матрицу смежности существующего ранее графика.

Список краев

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

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

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

Из списка ребер легко прийти к заключению, что график имеет три уникальных узла, AB, и 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диграфaddedgeaddnodermedge, и rmnode.