matrix - 如何构建 DAG 的双邻接矩阵？

Question

对于 bipartite graph ，您可以替换 adjacency matrix与所谓的biadjacency matrix :

The adjacency matrix A of a bipartite graph whose parts have r and s vertices has the form

A = O B
英国电信

where B is an r × s matrix and O is an all-zero matrix. Clearly, the matrix B uniquely represents the bipartite graphs, and it is commonly called its biadjacency matrix.

现在，DAG 是一个二部图，例如，您可以 topologically sort它使集合 U 和 V 分别是奇数或偶数拓扑级别上的节点。

这意味着，对于具有 n 个节点的 DAG，我只需要一个 (n/2)2 矩阵(平均而言)而不是 n2 矩阵。问题是，我不知道如何构建它。任何提示？

Answer 1

我相信您无法为 DAG 构建双邻接矩阵，因为并非每个 DAG 都是二部图。

这是一个简单的例子:考虑一个有 3 个顶点的有向图，并将它们表示为 A、B 和 C。边连接 A 到 B、B 到 C、A 到 C。该图显然是一个 DAG，因为它是有向的并且没有循环(A->B->C<-A 不是循环)。但是，该图不是二部图:无法将 A、B 和 C 划分为两个不相交的集合，其中同一集合中的顶点之间没有边。

结论是有图是 DAG 但不是二部图，所以不是每个 DAG 都是二部图。

请注意，您可以对 DAG 进行拓扑排序并将顶点划分为两个不相交的集合，这并不意味着同一集合的顶点之间没有边。