9

以下に説明する特定の状況を理解したと思いますが、証明を行うための理論的知識が不足しており、それについて言及しているソースを見つけることができませんでした。私の理解が正しければ、隣接行列の半分のスペースを節約できます。そうでなければ、かなり奇妙なバグが発生する可能性があります。ですから、私は確信したいと思います。より堅実な背景を持つ誰かが私の推論を見直していただければ幸いです.

n * n 隣接行列で n 個の頂点の DAG を表し、頂点から頂点へのエッジがある場合はエントリi,jが、そうでない場合はエントリがあるとします。グラフは有向で非巡回であるため、if 、thenに従います。i nのノードのトポロジー レベルがi n-1のノード以上になるようにマトリックス内のノードを並べ替えると、隣接マトリックスの半分には常にsのみが含まれるように思えます。、次の例のように:1ij0i,j = 1j,i = 00

      V 1 V 2 から V 1 2 3 4 5 6 7 8
      / \ / \
     / \ / \ から 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 0 0 0 0 0 0
  / \ / \ 4 1 1 0 0 0 0 0 0
V 3 V 4 V 5 5 0 1 0 0 0 0 0 0
             /|\ / 6 0 0 0 1 0 0 0 0
            / | \ / 7 0 0 0 1 0 0 0 0
           / | \ / 8 0 0 0 1 1 0 0 0
        e5/ e6| e7\ e8/
         / | \ /
       V 6 V 7 V 8

たぶん私は正しいのですが、これを確認する正式な方法はありますか?

4

2 に答える 2

7

ノードからノードへadj[i][j]の隣接エントリとし、すべてのノードで、ノードがノードよりもトポロジ階層の上位になるように並べ替えました。iji < jij

少しの間、あなたの仮定が間違っていたと仮定しましょう。反例がありますadj[i][j] == 1（i > jつまり、行列表現の右上半分にある反例）。iこれは、とを含むサイクルが必要であることを意味します。これは、並べ替えによってノードがノードよりも上位にあることがj保証されているにもかかわらず、階層を「登る」ことができることを意味します。DAGがあることがわかっているので、これは矛盾です。したがって、私たちはあなたの仮定が正しいことを証明しました。jiadj[i][j] == 1

于 2009-04-22T15:33:28.850 に答える
-1

これは、グラフラベルが並べ替えられた順序で隣接行列が構築されている場合にのみ正しいです。反例として、B->C->A の隣接行列を作成します。

真のノードのハッシュをそのトポロジカルソート位置に保持し、そこから隣接行列を作成すると、O(n) を使用して行列内の O(n²) スペースを節約しているため、大きな行列のスペースを節約できます。サイズハッシュテーブル。

于 2009-04-22T15:17:20.090 に答える