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

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

Некоторые из этих циклов можно рассматривать как комбинации небольших циклов. The 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 может, самое большее, расти линейно с количеством ребер в графике.