测量图复杂度

机器算法验证 图论
2022-04-18 12:11:16

背景：
有 5 种表示数学思想的方法：文字/文本、数字表、绘图/图形、符号表达式、流程图/图形。

当我询问“图表”（下）时，我并不是指 x-vs-y 关系的图片（又名图），而是指节点和边，图论版本。我还假设图是连接的 - 没有任何节点使得通过遍历边不可能从该节点到达图中的任何其他节点。

在单词/文本中存在程序圈复杂度的概念。

在符号表达式中，我们可以查看运算符的数量和参数的数量，以了解表达式的复杂性。

问题：
有哪些方法可以衡量图的复杂性？是由边和节点组成的表达式吗？有单号吗？我认为有无限的变化，但我不知道如何解决这个问题。

随机度量示例：
在随机起始位置的多次试验中，随机图步行者接触每条边和每个节点平均需要多长时间？那是一回事吗？（刚想到这个，果然是个东西。1、2）

后续问题：
有向图或有向加权图的复杂性如何变化？我知道有向图是所有图的子集。

更新：
可能相关的参考资料：

1个回答

常见的图表度量包括：

  1. 连通性：图是连通的——即您可以从任何其他节点到达任何节点，还是可以将图分解为“岛屿”或彼此无法到达的区域？
  2. 树测试：图是否符合树形（即，您可以通过单个唯一路径从任何其他节点到达任何节点吗？）
  3. 二分测试：有些图是二分的，也就是说，它们由两组节点组成，每个组的成员只与另一个组的成员连接。例如，建筑物和连接的公用事业（天然气、电力、水）的图表将是二分的
  4. 平面性：图形是平面的吗？也就是说，它是否可以绘制在二维表面上，这样就不必绘制相互交叉的边？
  5. 哈密​​顿/欧拉测试 - 可以在不使用相同边两次的情况下到达图中的每个节点吗？是否可以在图上追踪一条路径，使得每条边都被访问一次，并且只访问一次？
  6. 团分析：图的最大团数是多少，每个大小到这个数的团有多少个？
  7. 中心、直径、偏心率、外围、周长、扩展和半径度量：描述图表不同方面的其他（非详尽）指标

除此之外还有更多，但这里有一些链接到讨论这些指标的网站：

https://people.hofstra.edu/geotrans/eng/methods/ch1m3en.html

https://www.nas.ewi.tudelft.nl/people/Piet/papers/TUDreport20111111_MetricList.pdf

https://math.stackexchange.com/questions/301778/what-are-some-measures-of-connectedness-in-graphs

http://www.bu.edu/networks/files/2012/08/basics-of-network-analysis.pdf

这是一个相当简洁的列表： http: //mathworld.wolfram.com/topics/GraphProperties.html

另一个资源是 networkx python 库参考： http ://networkx.readthedocs.io/en/stable/reference/index.html

其它你可能感兴趣的问题
上一篇涉及联合累积和边际分布的不平等 下一篇为什么深度学习库强制成本函数输出标量？