Создайте направленный граф с девятью узлами. Постройте график.

s = [1 2 3 6 5 5 4 6 9 8 8 7];
t = [2 3 6 5 2 4 1 9 8 5 7 4];
G = digraph(s,t);
plot(G)

Вычислите все циклы на графике.

cycles = allcycles(G)

cycles=5×1 cell array
    {[    1 2 3 6 5 4]}
    {[1 2 3 6 9 8 5 4]}
    {[1 2 3 6 9 8 7 4]}
    {[        2 3 6 5]}
    {[    2 3 6 9 8 5]}

Второй выходной аргумент allcycles возвращает ребра, содержащиеся в каждом цикле. Это особенно полезно для мультиграфов, где индекс края необходим для однозначной идентификации краев в каждом цикле.

Создайте направленный мультиграф с восемью узлами и 18 ребрами. Укажите имена узлов. Постройте график с помеченными узлами и рёбрами.

s = [1 1 2 2 3 3 2 2 4 6 8 6 6 7 3 3 5 3];
t = [2 3 1 3 2 1 4 4 6 2 6 7 8 8 5 5 7 7];
names = {'A','B','C','D','E','F','G','H'};
G = digraph(s,t,[],names);
p = plot(G,'EdgeLabel',1:numedges(G));

Вычислите все циклы на графике. Укажите два выходных аргумента, чтобы вернуть индексы кромок в каждом цикле.

[cycles,edgecycles] = allcycles(G);

Просмотр узлов и кромок в пятом цикле.

cycles{5}

ans = 1x7 cell
    {'A'}    {'C'}    {'E'}    {'G'}    {'H'}    {'F'}    {'B'}

edgecycles{5}

ans = 1×7

     2     9    13    17    18    14     3

Выделите узлы и кромки в пятом цикле.

highlight(p,'Edges',edgecycles{5},'EdgeColor','r','LineWidth',1.5,'NodeColor','r','MarkerSize',6)

Используйте 'MaxNumCycles', 'MaxCycleLength', и 'MinCycleLength' для ограничения количества циклов, возвращаемых allcycles.

Создайте матрицу смежности для полного графика с 20 узлами. Создайте неориентированный граф из матрицы смежности, пропустив автоциклы.

A = ones(20);
G = graph(A,'omitselfloops');

Поскольку все узлы в графе связаны со всеми остальными узлами, в графе имеется большое количество циклов (более чем 1.7e17). Следовательно, невозможно вычислить все циклы, так как результаты не умещаются в памяти. Вместо этого вычислите первые 10 циклов.

cycles1 = allcycles(G,'MaxNumCycles',10)

cycles1=10×1 cell array
    {[                     1 2 3]}
    {[                   1 2 3 4]}
    {[                 1 2 3 4 5]}
    {[               1 2 3 4 5 6]}
    {[             1 2 3 4 5 6 7]}
    {[           1 2 3 4 5 6 7 8]}
    {[         1 2 3 4 5 6 7 8 9]}
    {[      1 2 3 4 5 6 7 8 9 10]}
    {[   1 2 3 4 5 6 7 8 9 10 11]}
    {[1 2 3 4 5 6 7 8 9 10 11 12]}

Теперь рассчитайте первые 10 циклов, длина которых меньше или равна 3.

cycles2 = allcycles(G,'MaxNumCycles',10,'MaxCycleLength',3)

cycles2=10×1 cell array
    {[ 1 2 3]}
    {[ 1 2 4]}
    {[ 1 2 5]}
    {[ 1 2 6]}
    {[ 1 2 7]}
    {[ 1 2 8]}
    {[ 1 2 9]}
    {[1 2 10]}
    {[1 2 11]}
    {[1 2 12]}

Наконец, вычислите первые 10 циклов, длина которых больше или равна 4.

cycles3 = allcycles(G,'MaxNumCycles',10,'MinCycleLength',4)

cycles3=10×1 cell array
    {[                      1 2 3 4]}
    {[                    1 2 3 4 5]}
    {[                  1 2 3 4 5 6]}
    {[                1 2 3 4 5 6 7]}
    {[              1 2 3 4 5 6 7 8]}
    {[            1 2 3 4 5 6 7 8 9]}
    {[         1 2 3 4 5 6 7 8 9 10]}
    {[      1 2 3 4 5 6 7 8 9 10 11]}
    {[   1 2 3 4 5 6 7 8 9 10 11 12]}
    {[1 2 3 4 5 6 7 8 9 10 11 12 13]}

Изучение того, каким образом осуществляется вывод cyclebasis и allcycles функции масштабируются с числом рёбер в графе.

Создайте и постройте график квадратной сетки с тремя узлами на каждой стороне квадрата.

n = 5;
A = delsq(numgrid('S',n));
G = graph(A,'omitselfloops');
plot(G)

Вычислить все циклы на графике с помощью allcycles. Используйте tiledlayout функция для построения массива вложенных графиков и выделения каждого цикла в вложенном графике. Результаты показывают, что всего на графике 13 циклов.

[cycles,edgecycles] = allcycles(G);
tiledlayout flow
for k = 1:length(cycles)
    nexttile
    highlight(plot(G),cycles{k},'Edges',edgecycles{k},'EdgeColor','r','NodeColor','r')
    title("Cycle " + k)
end

Некоторые из этих циклов можно рассматривать как комбинации меньших циклов. cyclebasis функция возвращает подмножество циклов, которые образуют базис для всех остальных циклов графа. Использовать cyclebasis вычислить базис фундаментального цикла и выделить каждый фундаментальный цикл в вложенном графике. Хотя в графе 13 циклов, существует только четыре фундаментальных цикла.

[cycles,edgecycles] = cyclebasis(G);
tiledlayout flow
for k = 1:length(cycles)
    nexttile
    highlight(plot(G),cycles{k},'Edges',edgecycles{k},'EdgeColor','r','NodeColor','r')
    title("Cycle " + k)
end

Теперь увеличьте число узлов на каждой стороне квадратного графа с трёх до четырёх. Это представляет небольшое увеличение размера графа.

n = 6;
A = delsq(numgrid('S',n));
G = graph(A,'omitselfloops');
figure
plot(G)

Использовать allcycles для вычисления всех циклов в новом графике. Для этого графа существует более 200 циклов, что слишком много для построения графика.

allcycles(G)

ans=213×1 cell array
    {[                       1 2 3 4 8 7 6 5]}
    {[                  1 2 3 4 8 7 6 10 9 5]}
    {[1 2 3 4 8 7 6 10 11 12 16 15 14 13 9 5]}
    {[      1 2 3 4 8 7 6 10 11 15 14 13 9 5]}
    {[            1 2 3 4 8 7 6 10 14 13 9 5]}
    {[                 1 2 3 4 8 7 11 10 6 5]}
    {[                 1 2 3 4 8 7 11 10 9 5]}
    {[           1 2 3 4 8 7 11 10 14 13 9 5]}
    {[     1 2 3 4 8 7 11 12 16 15 14 10 6 5]}
    {[     1 2 3 4 8 7 11 12 16 15 14 10 9 5]}
    {[     1 2 3 4 8 7 11 12 16 15 14 13 9 5]}
    {[1 2 3 4 8 7 11 12 16 15 14 13 9 10 6 5]}
    {[           1 2 3 4 8 7 11 15 14 10 6 5]}
    {[           1 2 3 4 8 7 11 15 14 10 9 5]}
    {[           1 2 3 4 8 7 11 15 14 13 9 5]}
    {[      1 2 3 4 8 7 11 15 14 13 9 10 6 5]}
      ⋮

Несмотря на большое количество циклов в графе, cyclebasis по-прежнему возвращает небольшое число фундаментальных циклов. Каждый из циклов в графе может быть построен с использованием только девяти фундаментальных циклов.

[cycles,edgecycles] = cyclebasis(G);
figure
tiledlayout flow
for k = 1:length(cycles)
    nexttile
    highlight(plot(G),cycles{k},'Edges',edgecycles{k},'EdgeColor','r','NodeColor','r')
    title("Cycle " + k)
end

Большое увеличение числа циклов с лишь небольшим изменением размера графа характерно для некоторых структур графа. Количество циклов, возвращаемых allcycles может расти экспоненциально с числом рёбер в графе. Однако количество циклов, возвращаемых cyclebasis может, самое большее, вырасти линейно с числом рёбер в графе.