allcycles
找到所有周期图
描述
例子
有向图中所有的周期
与九节点创建一个有向图。画出图。
s = [1 2 3 5 6 5 4 6 8 9 8 7];t = [2 3 5 6 5 4 2 1 9 8 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
返回包含在每个周期的边缘。这对于油印尤其有用,因为所需的边缘指数唯一地标识边缘在每个周期。
创建一个导演油印有八个节点和18边缘。指定节点的名称。绘制图形是贴有标签的节点和边。
s = [1 1 2 2 3 3 2 2 4 6 8 6 5 6 7 3 3 3];t = [2 3 1 2 3 1 4 4 5 6 2 6 7 8 8 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节点。创建一个无向图的邻接矩阵,省略self-loops。
一个= 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]}
现在计算的前10个周期的周期长度小于或等于3。
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]}
最后,计算一个周期的前10个周期长度大于或等于4。
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:长度(周期)nexttile突出(情节(G)、周期{k},“边缘”,edgecycles {k},“EdgeColor”,“r”,“NodeColor”,“r”)标题(“循环”+ k)结束
这些周期可以被看作是组合的小周期。的cyclebasis
函数返回循环形成的一个子集中的所有其他周期的基础图。使用cyclebasis
计算的基本周期基础和突出每个基本周期在一个次要情节。即使有13个周期图中,只有四种基本周期。
[周期,edgecycles] = cyclebasis (G);tiledlayout流为k = 1:长度(周期)nexttile突出(情节(G)、周期{k},“边缘”,edgecycles {k},“EdgeColor”,“r”,“NodeColor”,“r”)标题(“循环”+ k)结束
现在,增加节点的数量在每一侧的从三、四方图。这是一个小图形的大小。
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 5 8 7 11 15 14 13 9]}{(1 2 3 4 8 7 11 15 14 13 9 10 6 5]}⋮
尽管大量的周期图中,cyclebasis
还返回一个小数量的基本周期。每个周期图中可以使用只有9个基本构造周期。
[周期,edgecycles] = cyclebasis (G);图tiledlayout流为k = 1:长度(周期)nexttile突出(情节(G)、周期{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。根据这个定义,self-loops算作周期,尽管他们不能循环的一部分。
提示
周期图的数量在很大程度上依赖于图的结构。对于一些图结构,周期可以用节点的数量呈现指数级增长。例如,一个完全图12节点给出的
图G = ((12))
包含近6000万个周期。使用MaxNumCycles
,MaxCycleLength
,MinCycleLength
选择控制的输出allcycles
在这些情况下。
版本历史
介绍了R2021a
另请参阅
MATLAB命令
你点击一个链接对应MATLAB命令:
运行该命令通过输入MATLAB命令窗口。Web浏览器不支持MATLAB命令。万博1manbetx
你也可以从下面的列表中选择一个网站:
表现最好的网站怎么走吗
选择中国网站(中文或英文)最佳站点的性能。其他MathWorks国家网站不优化的访问你的位置。