単純な有向グラフを単純な無向グラフに変換するにはどうすればよいですか?
これは可能ですか？
質問する
8186 次
3 に答える
2
仮定：（ここから）
単純な digraph ループでは許可されません。(ループは、頂点とそれ自体をペアにする円弧です。)
そして：（ここから）
単純な [無向] グラフは、ループ (両端で同じ頂点に接続されたエッジ) がなく、2 つの異なる頂点間にエッジが 1 つしかない無向グラフです。
エッジは重み付けされていないと想定しています。そうでない場合、これを行う方法を指定しないと実行できません。
AM = 隣接行列
AL = 隣接リスト
すべてのエッジの方向を削除します。
AM: 各エッジ A->B に対して、行 A、列 B は既に設定されています。B行A列も設定します。
AL: 各エッジ A->B について、エッジは既に A の AL に表示されており、エッジを B の AL にも追加します。
すべてのエッジを通過し、そのエッジの端点である 2 つの頂点間のエッジが既に見つかったすべてのエッジを削除します (したがって、AB が既に処理されている場合、別の AB (または同等の BA) が見つかった場合は、そのエッジを削除します)。単純な有向グラフでは頂点間に複数のエッジが存在する可能性があるため、これを行う必要がありますが、単純な無向グラフでは発生しません。
AM: AM は頂点間にエッジを 1 つだけ存在させるため、特に何もする必要はありません。したがって、エッジを上書きするだけです。
AL: 各頂点 A について、その隣接リスト内の各エッジ AB または BA について、リスト内の他のすべてのエッジ AB または BA を削除します。
于 2013-05-04T02:07:46.767 に答える
1
各有向辺 e=(x,y) について、新しい頂点 ve1,…,ve5 を追加し、e を辺 xve1, ve1ve2, ve1ve3, ve3ve4, ve4ve5, ve3y に置き換えます。
デコードするには、隣接する次数が 2 であるすべての葉 (次数 1 の頂点) は、いくつかのエッジ e=(x,y) に対して ve5 でなければなりません。そのネイバーは ve4 で、ve4 のもう一方のネイバーは ve3 です。ve3 には、次数 3 の両方を持ち、葉に隣接する一意の隣接があります。隣接は ve1 であり、その葉は ve2 です (ve1 に 2 つの葉の隣接がある場合、任意に 1 つを選択して ve2 にします)。ve1 のもう一方の隣接は x であり、ve3 のもう一方の隣接は y です。有向辺 (x,y) を復元し、頂点 ve1,…,ve5 を削除します。
于 2017-01-15T22:02:38.570 に答える