cyclebasis

Основной базис цикла графика

Описание

пример

cycles = cyclebasis(G) вычисляет основной базис цикла неориентированного графа. Выход cycles массив ячеек, который указывает, какие узлы принадлежат каждому основному циклу.

пример

[cycles,edgecycles] = cyclebasis(G) также возвращает ребра в каждом цикле. Выход edgecycles массив ячеек где edgecycles{k} дает ребра между узлами в cycles{k}.

Примеры

свернуть все

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

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)

Figure contains an axes. The axes contains an object of type graphplot.

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

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);

Figure contains an axes. The axes contains an object of type graphplot.

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

[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

Figure contains 6 axes. Axes 1 with title Cycle 1 contains an object of type graphplot. Axes 2 with title Cycle 2 contains an object of type graphplot. Axes 3 with title Cycle 3 contains an object of type graphplot. Axes 4 with title Cycle 4 contains an object of type graphplot. Axes 5 with title Cycle 5 contains an object of type graphplot. Axes 6 with title Cycle 6 contains an object of type graphplot.

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

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

Figure contains an axes. The axes contains an object of type graphplot.

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

Исследуйте как выходные параметры cyclebasis и allcycles функции масштабируются с количеством ребер в графике.

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

n = 5;
A = delsq(numgrid('S',n));
G = graph(A,'omitselfloops');
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Вычислите все циклы в графике с помощью 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

Figure contains 13 axes. Axes 1 with title Cycle 1 contains an object of type graphplot. Axes 2 with title Cycle 2 contains an object of type graphplot. Axes 3 with title Cycle 3 contains an object of type graphplot. Axes 4 with title Cycle 4 contains an object of type graphplot. Axes 5 with title Cycle 5 contains an object of type graphplot. Axes 6 with title Cycle 6 contains an object of type graphplot. Axes 7 with title Cycle 7 contains an object of type graphplot. Axes 8 with title Cycle 8 contains an object of type graphplot. Axes 9 with title Cycle 9 contains an object of type graphplot. Axes 10 with title Cycle 10 contains an object of type graphplot. Axes 11 with title Cycle 11 contains an object of type graphplot. Axes 12 with title Cycle 12 contains an object of type graphplot. Axes 13 with title Cycle 13 contains an object of type graphplot.

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

Figure contains 4 axes. Axes 1 with title Cycle 1 contains an object of type graphplot. Axes 2 with title Cycle 2 contains an object of type graphplot. Axes 3 with title Cycle 3 contains an object of type graphplot. Axes 4 with title Cycle 4 contains an object of type graphplot.

Теперь увеличьте число узлов на каждой стороне квадратного графика от три до четыре. Это представляет маленькое увеличение размера графика.

n = 6;
A = delsq(numgrid('S',n));
G = graph(A,'omitselfloops');
figure
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Используйте 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

Figure contains 9 axes. Axes 1 with title Cycle 1 contains an object of type graphplot. Axes 2 with title Cycle 2 contains an object of type graphplot. Axes 3 with title Cycle 3 contains an object of type graphplot. Axes 4 with title Cycle 4 contains an object of type graphplot. Axes 5 with title Cycle 5 contains an object of type graphplot. Axes 6 with title Cycle 6 contains an object of type graphplot. Axes 7 with title Cycle 7 contains an object of type graphplot. Axes 8 with title Cycle 8 contains an object of type graphplot. Axes 9 with title Cycle 9 contains an object of type graphplot.

Значительное увеличение количества циклов только с небольшим изменением в размере графика типично для некоторых структур графика. Количество циклов возвращено allcycles может вырасти экспоненциально с количеством ребер в графике. Однако количество циклов, возвращенных cyclebasis может, самое большее, вырасти линейно с количеством ребер в графике.

Входные параметры

свернуть все

Введите график в виде graph объект. Используйте graph создать объект неориентированного графа.

Пример: G = graph(1,2)

Выходные аргументы

свернуть все

Основные циклы графика, возвращенные как массив ячеек. Каждая ячейка cycles{k} содержит узлы, которые принадлежат одному из основных циклов G. Каждый цикл начинается с самого маленького индекса узла. Если G не содержит циклов, затем cycles isempty.

Каждый цикл в G комбинация основных циклов, возвращенных в cycles. Если ребро является частью цикла в G, затем это - также часть по крайней мере одного основного цикла в cycles.

Тип данных ячеек в cycles зависит от того, содержит ли входной график имена узла:

  • Если график G не имеет имен узла, затем каждая ячейка cycles{k} числовой вектор из индексов узла.

  • Если график G имеет имена узла, затем каждая ячейка cycles{k} массив ячеек имен узла вектора символов.

Ребра в каждом основном цикле, возвращенном как массив ячеек. Каждая ячейка edgecycles{k} содержит индексы ребра для ребер в цикле cycles{k}. Если G не содержит циклов, затем edgecycles isempty.

Больше о

свернуть все

Основной базис цикла

В неориентированных графах fundamental cycle basis является набором простых циклов, который формирует базис для пробела цикла графика. Таким образом, любой цикл в графике может быть создан из основных циклов. Для примера смотрите Узлы и Ребра в Основных Циклах.

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

Минимальное дерево охвата, используемое в cyclebasis обычно отличается от того, возвращенного minspantree. Это выбрано таким образом, что циклы коротки. Однако cyclebasis как гарантируют, не возвратит самый короткий основной базис цикла.

Смотрите также

| | |

Введенный в R2021a
Для просмотра документации необходимо авторизоваться на сайте