cyclebasis

图的基本循环基

折叠页面

语法

cycles =循环基(G)

[cycles, edgcycles] = cyclebasis(G)

描述

例子

周期= cyclebasis (G）计算基本周期基础一个无向图。输出周期是一个单元格数组，它指示哪些节点属于每个基本循环。

例子

［周期，edgecycles] =循环基础(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 = graph(s,t);情节(G)

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

计算每个基本循环中的节点。

cycles =循环基(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 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);情节(G);

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

计算图的基本循环基。

[cycles, edgcycles] = 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的轴对象1包含一个graphplot类型的对象。标题为Cycle 2的坐标轴对象2包含一个graphplot类型的对象。标题为Cycle 3的坐标轴对象3包含一个graphplot类型的对象。标题为Cycle 4的坐标轴对象4包含一个graphplot类型的对象。标题为Cycle 5的坐标轴对象5包含一个graphplot类型的对象。标题为Cycle 6的坐标轴对象6包含一个graphplot类型的对象。

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

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

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

虽然每个循环都可以通过从循环基组合循环来构造，但不是每个基循环的组合都形成一个有效的循环。

比较基本循环基础和所有循环的集合

打开实时脚本

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

创建并绘制一个正方形网格图，在正方形的每边都有三个节点。

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

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

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

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

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

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

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

现在，将方形图每边的节点数量从3个增加到4个。这表示图的大小有一个小的增加。

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

图包含一个轴对象。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 13{[1 2 3 4 8 7 11 15 14 13 9 10 6 5]}

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

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

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