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

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