2

很抱歉这个简单的问题，但有没有办法确定一个完全连接的图？我读过一些论文，表明图的总连通性是图分析的先决条件。我通过 Matlab 的一些图形分析工具箱搜索确定连通性的此类函数，但这些工具箱中似乎至少没有提供任何功能。你能给我任何建议吗？非常感谢！

4

3 回答 3

5

您可以执行以下操作：

  • 假设 G 是图的邻接矩阵

  • 构建D，它是一个与G相同大小的对角矩阵，将第N个节点的度放在第N个对角元素中

  • 通过减法制作拉普拉斯矩阵：L = D - G

  • 计算 L 的特征值（eig函数 inmatlab会为你做）

  • 等于零的特征值的数量是图中连通分量的数量

  • 如果您的组件数为 1，则您的图是完全连接的，否则它具有您想要的组件数

此方法适用于有向图和无向图

希望你觉得它有帮助

于 2015-03-15T22:06:16.887 回答
1

我不是图论专家，但看起来graphconncomp可以完成这项工作。

此函数查找图中所有连接的组件，因此如果图是完全连接的，它将返回 S=1 组件，并且 C 将为每个节点包含一个 1。

例如

[S,C] = graphconncomp(G)
if all(C==ones(size(C)))
  disp "G is fully connected";
end
于 2013-04-01T13:59:37.433 回答
0

Another option would be to use the FEX function isconnected, see here.

This will determine if your graph is connected and has 1 as output if connected and 0 otherwise. Only works on undirected graphs though.

于 2014-09-15T08:23:52.273 回答