Основной базис цикла графика
вычисляет основной базис цикла неориентированного графа. Выход 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)
Вычислите, какие узлы находятся в каждом основном цикле.
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
может, самое большее, вырасти линейно с количеством ребер в графике.
G
— Введите графикgraph
объектВведите график в виде graph
объект. Используйте graph
создать объект неориентированного графа.
Пример: G = graph(1,2)
cycles
— Основные циклы графикаОсновные циклы графика, возвращенные как массив ячеек. Каждая ячейка cycles{k}
содержит узлы, которые принадлежат одному из основных циклов G
. Каждый цикл начинается с самого маленького индекса узла. Если G
не содержит циклов, затем cycles
isempty.
Каждый цикл в G
комбинация основных циклов, возвращенных в cycles
. Если ребро является частью цикла в G
, затем это - также часть по крайней мере одного основного цикла в cycles
.
Тип данных ячеек в cycles
зависит от того, содержит ли входной график имена узла:
Если график G
не имеет имен узла, затем каждая ячейка cycles{k}
числовой вектор из индексов узла.
Если график G
имеет имена узла, затем каждая ячейка cycles{k}
массив ячеек имен узла вектора символов.
edgecycles
— Ребра в каждом основном циклеРебра в каждом основном цикле, возвращенном как массив ячеек. Каждая ячейка edgecycles{k}
содержит индексы ребра для ребер в цикле cycles{k}
. Если G
не содержит циклов, затем edgecycles
isempty.
В неориентированных графах fundamental cycle basis является набором простых циклов, который формирует базис для пробела цикла графика. Таким образом, любой цикл в графике может быть создан из основных циклов. Для примера смотрите Узлы и Ребра в Основных Циклах.
Основной базис цикла графика вычисляется от минимального дерева охвата графика. Для каждого ребра, которое не находится в минимальном дереве охвата, там существует один основной цикл, который состоит из того ребра, его конечных узлов и пути в минимальном дереве охвата, которое соединяет их.
Минимальное дерево охвата, используемое в cyclebasis
обычно отличается от того, возвращенного minspantree
. Это выбрано таким образом, что циклы коротки. Однако cyclebasis
как гарантируют, не возвратит самый короткий основной базис цикла.
У вас есть модифицированная версия этого примера. Вы хотите открыть этот пример со своими редактированиями?
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста - например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.