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

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