主要内容

cyclebasis

图的基本循环基

在页面中全部折叠

语法

cycles = cyclebasis(G)
[cycles, edgeccycles] = cyclebasis(G)

描述

例子

周期= cyclebasis (G）计算基本周期基准无向图的。输出周期表示哪些节点属于每个基本周期的单元格数组。

例子

［周期，edgecycles= cyclebasis(G）也返回每个循环中的边。输出edgecycles单元格数组在哪里edgecycles {k}给出节点之间的边周期{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 =图(s,t);情节(G)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

计算每个基本循环中有哪些节点。

cycles = cyclebasis(G)
周期=4×1单元格数组{[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 =图(s,t);情节(G);

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

计算图的基本循环基。

[cycles, edgeccycles] = cyclebasis(G)
周期=6×1单元格数组{(1 2 4)} {[1 3 4]} {[2 4 5]} {[3 4 6]} {[4 5 7]} {[4 6 7]}
edgecycles =6×1单元格数组{[1 4 3]} {[2 6 3]} {[4 8 5]} {[6 9 7]} {[8 11 10]} {[9 12 10]}

突出显示每个基本周期，使用tiledlayout而且nexttile构建一组子图。对于每个子图，首先获取对应循环的节点周期，和边缘来自edgecycles．然后绘制图形并突出显示这些节点和边。

tiledlayout流为k = 1:length(cycles) nexttile highlight(plot(G)，cycles{k}，“边缘”, edgecycles {k},“EdgeColor”，“r”，“NodeColor”，“r”)标题(“循环”+ k)结束

图中包含6个轴对象。标题为Cycle 1的axis对象1包含一个graphplot类型的对象。axis对象2包含一个graphplot类型的对象。axis对象3包含一个graphplot类型的对象。axis对象4包含一个graphplot类型的对象。axis对象5包含一个graphplot类型的对象。axis对象6(标题为Cycle 6)包含一个graphplot类型的对象。

你可以在图中构造任何其他的循环，方法是找出两个或多个基本循环之间的对称差setxor函数。例如，取前两个循环之间的对称差，并绘制得到的新循环。

图new_cycle_edges = setxor(edgeccycles {1}， edgeccycles {2});突出(情节(G),“边缘”new_cycle_edges,“EdgeColor”，“r”，“NodeColor”，“r”）

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

虽然每个循环都可以由循环基的循环组合而成，但并不是每个基循环的组合都能形成一个有效的循环。

打开实时脚本

检查的输出如何cyclebasis而且allcycles函数随图中边的数量而缩放。

创建并绘制方格网格图，方格每边有三个节点。

N = 5;A = delsq(numgrid)“年代”, n));G =图(A，“omitselfloops”）;情节(G)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

计算图中的所有循环allcycles．使用tiledlayout函数构造子图数组并突出显示子图中的每个周期。结果表明，图中总共有13个循环。

[cycles, edgeccycles] = allcycles(G);tiledlayout流为k = 1:length(cycles) nexttile highlight(plot(G)，cycles{k}，“边缘”, edgecycles {k},“EdgeColor”，“r”，“NodeColor”，“r”)标题(“循环”+ k)结束

图中包含13个轴对象。标题为Cycle 1的axis对象1包含一个graphplot类型的对象。axis对象2包含一个graphplot类型的对象。axis对象3包含一个graphplot类型的对象。axis对象4包含一个graphplot类型的对象。axis对象5包含一个graphplot类型的对象。axis对象6(标题为Cycle 6)包含一个graphplot类型的对象。axis对象7包含一个graphplot类型的对象。axis对象8包含一个graphplot类型的对象。axis对象9的标题Cycle 9包含一个graphplot类型的对象。 Axes object 10 with title Cycle 10 contains an object of type graphplot. Axes object 11 with title Cycle 11 contains an object of type graphplot. Axes object 12 with title Cycle 12 contains an object of type graphplot. Axes object 13 with title Cycle 13 contains an object of type graphplot.

其中一些循环可以看作是较小的循环的组合。的cyclebasis函数返回构成图中所有其他循环基的循环的子集。使用cyclebasis计算基本周期基并在副图中突出显示每个基本周期。尽管图中有13个循环，但基本循环只有4个。

[cycles, edgeccycles] = cyclebasis(G);tiledlayout流为k = 1:length(cycles) nexttile highlight(plot(G)，cycles{k}，“边缘”, edgecycles {k},“EdgeColor”，“r”，“NodeColor”，“r”)标题(“循环”+ k)结束

图中包含4个轴对象。标题为Cycle 1的axis对象1包含一个graphplot类型的对象。axis对象2包含一个graphplot类型的对象。axis对象3包含一个graphplot类型的对象。axis对象4包含一个graphplot类型的对象。

现在，将正方形图两边的节点数从3增加到4。这表示图形的大小略有增加。

N = 6;A = delsq(numgrid)“年代”, n));G =图(A，“omitselfloops”）;图绘制(G)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

使用allcycles计算新图中所有的循环。对于这张图，有超过200个循环，这太多了，无法绘制。

allcycles (G)
ans =213×1单元格数组{[8 1 2 3 4 5 6 7]} {(1 2 3 4 5 8 7 6 10 9]} {(1 2 3 4 8 7 6 10 11 12 16 15 14 13 9 5]} {(1 2 3 4 5 8 7 6 10 11 15 14 13 9]} {(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 5 8 7 11 10 9]} {(1 2 3 4 5 8 7 11 10 14 13 9]} {(1 2 3 4 8 7 11 12 16 15 14 10 6 5]} {(1 2 3 4 5 8 7 11 12 16 15 14 10 9]} {(1 2 3 4 5 8 7 11 12 16 15 14 13 9]} {(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 5 8 7 11 15 14 10 9]} {(1 2 3 4 8 7 11 15 14 139 5]} {[1 2 3 4 8 7 11 15 14 13 9 10 6 5]}

尽管图中有大量的循环，cyclebasis仍然返回少量的基本周期。图中的每个循环只能用9个基本循环来构造。

[cycles, edgeccycles] = cyclebasis(G);图tiledlayout流为k = 1:length(cycles) nexttile highlight(plot(G)，cycles{k}，“边缘”, edgecycles {k},“EdgeColor”，“r”，“NodeColor”，“r”)标题(“循环”+ k)结束

图中包含9个轴对象。标题为Cycle 1的axis对象1包含一个graphplot类型的对象。axis对象2包含一个graphplot类型的对象。axis对象3包含一个graphplot类型的对象。axis对象4包含一个graphplot类型的对象。axis对象5包含一个graphplot类型的对象。axis对象6(标题为Cycle 6)包含一个graphplot类型的对象。axis对象7包含一个graphplot类型的对象。axis对象8包含一个graphplot类型的对象。axis对象9的标题Cycle 9包含一个graphplot类型的对象。

对于某些图结构来说，循环数的大量增加而图的大小只有很小的变化是典型的。返回的循环数allcycles可以随图中边的数量呈指数增长。然而，返回的循环数cyclebasis最多可以随图中边的数量线性增长。

输入参数

全部折叠

输入图形，指定为图对象。使用图创建一个无向图对象。

例子:G =图(1,2)

输出参数

全部折叠

基本图循环，作为单元格数组返回。每一个细胞周期{k}包含属于的基本循环之一的节点G．每个循环从最小的节点索引开始。如果G不包含任何循环，那么周期是空的。

每个周期G返回的是基本周期的组合吗周期．如果一条边是循环的一部分G，那么它也是至少一个基本周期的一部分周期．

中的单元格的数据类型周期取决于输入图是否包含节点名:

  • 如果图G没有节点名，那么每个单元格呢周期{k}是节点索引的数值向量。

  • 如果图G有节点名，然后是每个单元格周期{k}字符向量节点名称的单元格数组。

每个基本循环中的边，作为单元格数组返回。每一个细胞edgecycles {k}包含循环中边的边索引周期{k}．如果G不包含任何循环，那么edgecycles是空的。

更多关于

全部折叠

图周期

当存在一个非空路径，其中只重复第一个和最后一个节点时，图中就存在循环。也就是说，除了在路径末尾重复第一个节点以关闭循环之外，没有重复其他节点。例如:(Node1 - Node2 - Node3 - Node1)。按照惯例,cyclebasis不返回循环中的最后一个节点，因为它与第一个节点相同。

一个循环不能两次穿过同一条边。例如，无向图中的循环(Node1 - Node2 - Node1)只在Node1和Node2之间有多条边连接的情况下存在。根据这个定义，自循环算作循环，尽管它们不能成为更大循环的一部分。

基本周期基准

在无向图中基本周期基准是构成图的循环空间基的一组简单循环。也就是说，图中的任何循环都可以由基本循环构造出来。示例请参见基本循环中的节点和边．

图的基本循环基由图的最小生成树计算。对于不属于最小生成树的每条边，都存在一个基本循环，这个循环由该边、它的端点节点和连接它们的最小生成树路径组成。

中的最小生成树cyclebasis通常与返回的值不同minspantree．它的选择使其周期较短。然而,cyclebasis不能保证返回最短的基本周期基。

版本历史

在R2021a中引入

另请参阅

|||

Baidu
map