我想我已经理解了如下所述的特定情况,但我缺乏进行证据的理论知识,我找不到任何提及它的来源.如果我的理解是正确的,我可以在我的邻接矩阵上节省一半的空间,如果不是,我可能会有非常奇怪的错误.所以我想确定一下,如果有更坚实背景的人能够回顾我的推理,我会很感激.
假设我在n*n邻接矩阵中表示n个顶点的DAG,使得条目i,j是1从顶点i到顶点存在边缘j,0否则.因为图是有针对性的和非循环的,所以,如果i,j = 1,那么j,i = 0.如果我现在对矩阵中的节点进行排序,使得i n处的节点的拓扑级别等于或大于i n-1处的节点,那么在我看来,邻接矩阵的一半将始终仅包含0s ,就像以下示例中的情况一样:
V 1 V 2 from V 1 2 3 4 5 6 7 8
/ \ / \
/ \ / \ to V 1 0 0 0 0 0 0 0 0
/ \ / \ 2 0 0 0 0 0 0 0 0
e1/ e2\ e3/ e4\ 3 1 0 … graph-theory ×1