graph-theory - "diamond"有向无环图的正确术语是什么？

Question

我想谈谈有向无环图中从节点节点到另一个节点有多条路径的地方。这不是“循环”，我应该怎么称呼它？我正在使用术语“钻石”，但这意味着只有四个节点，这是不对的。

Answer 1

正如你所说，正确的术语不太可能是菱形图，它已经有一个相似但略有不同的 meaning .

这很丑陋，但您所指的图表是 homeomorphism的dipole graph .也就是说，您可以通过收缩任何入度和出度为 1 的边来简化图形。

根据过去的经验，图论术语可能很难掌握。如果您有数学家的 friend 或同事，在这种情况下，他们应该始终是您的首选。如果您有空闲时间，可以使用有关图论的很好的引用资料。我推荐 Graph Theory通过邦迪和穆尔蒂或 Graph Theory迪斯特尔。如果两者都不可用，您可以随时尝试 wikipedia ，或与数学相关的 stackexchange 站点之一。