有向无环图中“菱形”的正确术语是什么?

问题描述 投票:0回答:1

我想讨论有向无环图中从一个节点到另一个节点有不止一条路径的地方。这不是一个“循环”,我该怎么称呼它呢?我使用术语“钻石”,但这意味着只有四个节点,这是不正确的。

graph-theory directed-acyclic-graphs
1个回答
5
投票

正如您所说,正确的术语不太可能是菱形图,它已经具有类似但略有不同的含义

它很丑陋,但你所指的图是偶极图同胚。也就是说,您可以通过收缩入度和出度为 1 的任意边来简化图。

根据过去的经验,图论术语可能很难。如果你有数学家的朋友或同事,在这种情况下他们应该永远是你的第一站。如果您有足够的时间,您可以使用有关图论的良好参考资料。我推荐 Bondy 和 Murty 的《图论》或 Diestel 的《图论》。如果两者都不可用,您可以随时尝试wikipedia,或数学相关的 stackexchange 站点之一。

© www.soinside.com 2019 - 2024. All rights reserved.