图拓扑分析
Graph Topology Profiling
谁能给我一些可以用来分析图拓扑分类的算法？
输入：带有原始图信息的邻接表。
输出：它是什么样的图？目前我只想关注纯类型 - 菊花链、网状、环状、星状、树状。
算法研究的哪个领域负责这种算法？是计算几何吗？
编辑 - 图的大小不会超过 32 个节点。但是，节点之间会有冗余链接。
编辑 - 我知道我的问题可能过于宽泛，但至少在否决它之前给我一些问题的线索。还是因为我的名声:-(
首先检查您的图是否已完全连接。
然后，检查节点的分布degree:
- 环：所有节点的度数为 2
- 菊花链：除 2 个节点的度数为 1 外，所有节点的度数均为 2（菊花链有其他定义）。
- 星：除一个节点的度数为 n-1 外，每个节点的度数均为 1
- 树：度数之和为2*(节点数-1)。另外，如果最高度为k，则至少有k个度为1的节点。
- Mesh：一切顺利...
我认为没有 'area' 的算法可以处理此类问题，但是术语 'graph classes' 很常见（参见示例 here），尽管它不是正式术语。
要对新实例进行分类，首先需要一个分类系统！
换句话说，你的图（要分类的项目）适合图拓扑（分类系统）的某种数据结构中的某个地方。该系统可以像列表一样简单；在这种情况下，您可以执行 中概述的简单算法，其中拓扑列表按度分布键控。
更复杂的系统可以是分层系统，类似于生物分类系统。这仅对于非常大量的图形拓扑结构才是真正必要的，在这种情况下，它可以更快地根据一系列决策进行分类。本质上是决策树。
可能很难在这个领域（对于纯图形）找到很多研究，因为它有点难以想到应用程序。有蛋白质折叠拓扑的应用程序，但可能没有兴趣。
谁能给我一些可以用来分析图拓扑分类的算法？ 输入：带有原始图信息的邻接表。 输出：它是什么样的图？目前我只想关注纯类型 - 菊花链、网状、环状、星状、树状。
算法研究的哪个领域负责这种算法？是计算几何吗？
编辑 - 图的大小不会超过 32 个节点。但是，节点之间会有冗余链接。
编辑 - 我知道我的问题可能过于宽泛，但至少在否决它之前给我一些问题的线索。还是因为我的名声:-(
首先检查您的图是否已完全连接。
然后，检查节点的分布degree:
- 环：所有节点的度数为 2
- 菊花链：除 2 个节点的度数为 1 外，所有节点的度数均为 2（菊花链有其他定义）。
- 星：除一个节点的度数为 n-1 外，每个节点的度数均为 1
- 树：度数之和为2*(节点数-1)。另外，如果最高度为k，则至少有k个度为1的节点。
- Mesh：一切顺利...
我认为没有 'area' 的算法可以处理此类问题，但是术语 'graph classes' 很常见（参见示例 here），尽管它不是正式术语。
要对新实例进行分类，首先需要一个分类系统！
换句话说，你的图（要分类的项目）适合图拓扑（分类系统）的某种数据结构中的某个地方。该系统可以像列表一样简单；在这种情况下，您可以执行
更复杂的系统可以是分层系统，类似于生物分类系统。这仅对于非常大量的图形拓扑结构才是真正必要的，在这种情况下，它可以更快地根据一系列决策进行分类。本质上是决策树。
可能很难在这个领域（对于纯图形）找到很多研究，因为它有点难以想到应用程序。有蛋白质折叠拓扑的应用程序，但可能没有兴趣。