Создайте и постройте неориентированного графа.

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

Вычислите, какие узлы находятся в каждом основном цикле.

cycles = cyclebasis(G)

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

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

Создайте и постройте неориентированного графа.

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

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

[cycles,edgecycles] = cyclebasis(G)

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

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

Подсветите каждый из основных циклов, с помощью tiledlayout и nexttile создать массив подграфиков. Для каждого подграфика сначала получите узлы соответствующего цикла от cycles, и ребра от edgecycles. Затем постройте график и подсветите те узлы и ребра.

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

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

figure
new_cycle_edges = setxor(edgecycles{1},edgecycles{2});
highlight(plot(G),'Edges',new_cycle_edges,'EdgeColor','r','NodeColor','r')

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

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