allcycles
找出图中所有的循环
描述
例子
有向图中的所有周期
创建一个具有9个节点的有向图。画出图。
S = [1 2 3 6 5 5 4 6 9 8 8 7];T = [2 3 6 5 2 4 1 9 8 5 7 4];G =有向图(s, t);情节(G)
计算图中所有的循环。
周期= allcycles (G)
周期=5×1单元阵列{[1 2 3 6 5 4]} {[1 2 3 6 9 8 5 4]} {[1 2 3 6 9 8 7 4]} {[2 3 6 5]} {[2 3 6 9 8 5]}
循环中包含的边
的第二个输出参数allcycles
返回每个循环中包含的边。这对于多图尤其有用,因为需要边缘索引来唯一地标识每个循环中的边缘。
创建具有8个节点和18条边的有向多图。为节点指定名称。用标记的节点和边绘制图。
S = [1 1 2 2 3 3 2 2 4 6 8 6 6 7 3 3 5 3];T = [2 3 1 3 2 1 4 4 6 2 6 7 8 8 5 5 7 7];名称= {“一个”,“B”,“C”,' D ',“E”,“F”,‘G’,“H”};G =有向图(s t[],名称);p =情节(G,“EdgeLabel”1: numedges (G));
计算图中所有的循环。指定两个输出参数,也返回每个循环中的边的边索引。
[周期,edgecycles] = allcycles (G);
查看第五个循环中的节点和边。
周期{5}
ans =1 x7单元格{' a '} {' c '} {' e '} {' g '} {' h '} {' f '} {' b '}
edgecycles {5}
ans =1×72 9 13 17 18 14 3
在第五个循环中突出显示节点和边缘。
突出(p,“边缘”, edgecycles {5},“EdgeColor”,“r”,“线宽”, 1.5,“NodeColor”,“r”,“MarkerSize”6)
限制返回的循环数
使用“MaxNumCycles”
,“MaxCycleLength”
,“MinCycleLength”
选项来限制返回的循环数allcycles
.
为20个节点的完整图创建邻接矩阵。从邻接矩阵创建一个无向图,忽略自循环。
一个= 1 (20);图G = (,“omitselfloops”);
由于图中的所有节点都连接到所有其他节点,所以图中有大量的循环(超过1.7 e17
).因此,计算所有的周期是不可行的,因为结果将不适合内存。相反,计算前10个周期。
cycles1 = allcycles (G,“MaxNumCycles”, 10)
cycles1 =10×1单元阵列{(1 2 3)} {(1 2 3 4)} {(1 2 3 4 5)} {(1 2 3 4 5 6)} {(1 2 3 4 5 6 7)} {(1 2 3 4 5 6 7 8]} {(1 2 3 4 5 6 7 8 9]} {(1 2 3 4 5 6 7 8 9 10]} {(1 2 3 4 5 6 7 8 9 10 11]} {(1 2 3 4 5 6 7 8 9 10 11 12]}
现在计算周期长度小于等于3的前10个周期。
cycles2 = allcycles (G,“MaxNumCycles”10“MaxCycleLength”3)
cycles2 =10×1单元阵列{(1 2 3)} {[1 2 4]} {[1 2 5]} {[1 2 6]} {[1 2 7]} {[1 2 8]} {[1 2 9]} {[1 2 10]} {[1 2 11]} {[1 2 12]}
最后,计算周期长度大于或等于4的前10个周期。
cycles3 = allcycles (G,“MaxNumCycles”10“MinCycleLength”4)
cycles3 =10×1单元阵列{(1 2 3 4)} {(1 2 3 4 5)} {(1 2 3 4 5 6)} {(1 2 3 4 5 6 7)} {(1 2 3 4 5 6 7 8]} {(1 2 3 4 5 6 7 8 9]} {(1 2 3 4 5 6 7 8 9 10]} {(1 2 3 4 5 6 7 8 9 10 11]} {(1 2 3 4 5 6 7 8 9 10 11 12]} {(1 2 3 4 5 6 7 8 9 10 11 12 13]}
比较基本周期基与所有周期集
检查的输出如何cyclebasis
而且allcycles
函数随图中边的数量而缩放。
创建并绘制方格网格图,方格每边有三个节点。
n = 5;一个= delsq (numgrid (“年代”, n));图G = (,“omitselfloops”);情节(G)
计算图中的所有循环allcycles
.使用tiledlayout
函数构造子图数组并突出显示子图中的每个周期。结果表明,图中总共有13个循环。
[周期,edgecycles] = allcycles (G);tiledlayout流为k = 1:length(cycles) nexttile highlight(plot(G),cycles{k},“边缘”, edgecycles {k},“EdgeColor”,“r”,“NodeColor”,“r”)标题(“循环”+ k)结束
其中一些循环可以看作是较小的循环的组合。的cyclebasis
函数返回构成图中所有其他循环基的循环的子集。使用cyclebasis
计算基本周期基并在副图中突出显示每个基本周期。尽管图中有13个循环,但基本循环只有4个。
[周期,edgecycles] = cyclebasis (G);tiledlayout流为k = 1:length(cycles) nexttile highlight(plot(G),cycles{k},“边缘”, edgecycles {k},“EdgeColor”,“r”,“NodeColor”,“r”)标题(“循环”+ k)结束
现在,将正方形图两边的节点数从3增加到4。这表示图形的大小略有增加。
n = 6;一个= delsq (numgrid (“年代”, n));图G = (,“omitselfloops”);图绘制(G)
使用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个基本循环来构造。
[周期,edgecycles] = cyclebasis (G);图tiledlayout流为k = 1:length(cycles) nexttile highlight(plot(G),cycles{k},“边缘”, edgecycles {k},“EdgeColor”,“r”,“NodeColor”,“r”)标题(“循环”+ k)结束
对于某些图结构来说,循环数的大量增加而图的大小只有很小的变化是典型的。返回的循环数allcycles
可以随图中边的数量呈指数增长。然而,返回的循环数cyclebasis
最多可以随图中边的数量线性增长。
输入参数
名称-值参数
指定可选参数对为Name1 = Value1,…,以=家
,在那里的名字
参数名称和价值
对应的值。名-值参数必须出现在其他参数之后,但对的顺序并不重要。
在R2021a之前,名称和值之间用逗号隔开,并括起来的名字
在报价。
例子:allcycles (G, MaxNumCycles, 100)
只返回图中的前100个循环。
MaxNumCycles
- - - - - -最大循环数
非负整数标量
最大循环数,指定为逗号分隔的对,由“MaxNumCycles”
和一个非负整数标量。当图中的循环数增长到足以达到内存限制时,此选项非常有用。您可以指定MaxNumCycles
来限制返回的循环数allcycles
这样就能在可用的内存内得到结果。
例子:allcycles (G, MaxNumCycles, 100)
MaxCycleLength
- - - - - -最大周期长度
正整数标量
最大循环长度,用逗号分隔的对指定“MaxCycleLength”
和一个正整数标量。的返回的结果allcycles
这样就不会返回长度大于指定限制的循环。循环的长度是由其中的边的数量来衡量的,忽略了边的权重。
要查找具有长度范围的循环,请指定两者“MaxCycleLength”
而且“MinCycleLength”
.要查找具有精确指定长度的循环,请为两者指定相同的值“MaxCycleLength”
而且“MinCycleLength”
.
例子:allcycles (G, MaxCycleLength, 4)
返回长度小于或等于4的循环。
例子:allcycles (G, MinCycleLength 3 MaxCycleLength, 5)
返回长度为3、4或5的循环。
MinCycleLength
- - - - - -最小周期长度
正整数标量
最小周期长度,指定为逗号分隔的对“MinCycleLength”
和一个正整数标量。的返回的结果allcycles
这样就不会返回长度小于指定限制的循环。循环的长度是由其中的边的数量来衡量的,忽略了边的权重。
要查找具有长度范围的循环,请指定两者“MaxCycleLength”
而且“MinCycleLength”
.要查找具有精确指定长度的循环,请为两者指定相同的值“MaxCycleLength”
而且“MinCycleLength”
.
例子:allcycles (G, MinCycleLength, 2)
返回长度大于或等于2的循环。
例子:allcycles (G, MinCycleLength 3 MaxCycleLength, 5)
返回长度为3、4或5的循环。
输出参数
周期
——图周期
单元阵列
图周期,作为单元格数组返回。每个元素周期{k}
包含属于其中一个循环的节点G
.每个周期都从节点索引最小的节点开始,并按字典顺序返回周期。无向图中的循环仅按单一方向返回一次。如果G
不包含任何循环,那么周期
是空的。
中的单元格的数据类型周期
取决于输入图是否包含节点名:
如果图
G
没有节点名,那么每个元素呢周期{k}
是节点索引的数值向量。如果图
G
有节点名,然后是每个元素周期{k}
字符向量节点名称的单元格数组。
edgecycles
-每个循环中的边
单元阵列
每个循环中的边,作为单元格数组返回。每个元素edgecycles {k}
包含对应循环中边的边索引,周期{k}
.如果G
不包含任何循环,那么edgecycles
是空的。
更多关于
图周期
当存在一个非空路径,其中只重复第一个和最后一个节点时,图中就存在循环。也就是说,除了在路径末尾重复第一个节点以关闭循环之外,没有重复其他节点。例如:(Node1 - Node2 - Node3 - Node1)。按照惯例,allcycles
不返回循环中的最后一个节点,因为它与第一个节点相同。
一个循环不能两次穿过同一条边。例如,无向图中的循环(Node1 - Node2 - Node1)只在Node1和Node2之间有多条边连接的情况下存在。根据这个定义,自循环算作循环,尽管它们不能成为更大循环的一部分。
提示
图中的循环数很大程度上取决于图的结构。对于某些图结构,循环的数量可以随着节点的数量呈指数增长。例如,一个包含12个节点的完整图由
图G = ((12))
包含近6000万个循环。使用MaxNumCycles
,MaxCycleLength
,MinCycleLength
选项来控制的输出allcycles
在这些情况下。
版本历史
介绍了R2021a
另请参阅
MATLAB命令
你点击了一个对应于这个MATLAB命令的链接:
在MATLAB命令窗口中输入命令来运行该命令。Web浏览器不支持MATLAB命令。
您也可以从以下列表中选择网站:
如何获得最佳的网站性能
选择中国网站(中文或英文)以获得最佳的网站表现。其他MathWorks国家网站没有针对从您的位置访问进行优化。