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

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

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