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

Question

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

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

编辑:

例如， for this undirected graph,

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

Answer 1

您正在查看的是comparability graph .这类图也称为“可传递的可定向图”，但这不是最常见的名称。要识别此类，请查看 graphclasses website .