如何检查给定的无向图是否存在传递方向？

Question

如果无向图的边可以这样定向，即如果 (x, y) 和 (y, z) 是生成的有向图中的两条边，则还存在一条边 ( x, z) 在生成的有向图中。

我正在处理真实的食物网络，我需要检查密集无向图（模拟食物网络中的竞争）是否具有传递方向。无向图表示为Java.

中的邻接矩阵

编辑：

例如， for this undirected graph,

我们可以在 this way 中定位边缘。因此，此图具有传递方向。

Answer 1

您正在查看的是comparability graph。这个 class 的图也被称为 "transitively orientable graphs"，但这不是最常见的名称。 要识别此 class，请查看 graphclasses website。