サイクルを作成せずに有向非循環グラフにエッジを追加する方法

Question

私は有向枝と無向枝のグラフを持っていますが、無向枝を有向枝で置き換えたい（各無向枝は有向枝になります） 。無方向の各エッジには2つの可能性があります（ある方向または他の方向の有向​​エッジで置き換えます）。

グラフが非周期的になるように、無向エッジの方向を決定する方法はありますか？

私のアプローチ：

のみ有向エッジを持つグラフを作成し、後に1（有向エッジなど）によって無向エッジ1を加えます。今私はDAGを持っている、私の問題は、DAGプロパティ（有向枝、サイクルなし）を維持しながらグラフに有向エッジを追加することに削減されます。

エッジをDAGに追加する方法と、結果のグラフもDAGであることを確認する方法はありますか。

Answer 1

これは私のために働いた：

は無向辺を一つずつ（彼らは小さなに大きなTOPO-vlalueから指すよう）を追加し、無向辺ずにグラフ上のトポロジカルソートを行います。

このようにして、エッジを追加した後にDAGがDAGを維持することが保証されます。

@ user58697のように、グラフをトポロジカルにソートした後に合計順序が存在するため、部分的な順序を拡張する必要はありません。各ノードのトポ - 値は他のトポ - 値に匹敵します。

Answer 2

はのは、例を見ることで、この問題を解決してみましょう： - ：

(1,2) 
(2,3) 
(4,5) 
(5,6) 
(7,3) 

そして、我々は無向ものと頂点の集合を以下 -

は、私は監督のものと頂点の次のセットを持っていると仮定します： - 私たちは紙の上に私たちのグラフを作成する場合

(3,4) 
(6,7) 

だから今、それはこの

のようになるはずです

1 -> 2 -> 3 
     /\ 
     /4 -> 5 -> 6 
    /   /\ 
    -----------------7 

ですから、はっきりだから我々は、（3,4）として最初無向のペアを選んで、頂点3を配置することができます

、私たちは監督のものと交換したい存在する二つの無向エッジがあります見ることができます - > 4とそれ以降はdfs（1）を呼び出し、サイクルが見つかると（3,4）が有効ではない場合、4→3としますが、3→4は発生しません任意のサイクル。

次の（6,7）ペアに移動し、6 - > 7を配置するとサイクルが発生するため、7 - > 6となり、DAGが得られます。

これは強力な解決策のようなものです。私はそれをもっと考えさせてください、この問題に対するよりよいアプローチがありますか？

Answer 3

あなたが持っているすべての有向枝で最初のDAGを構築します。それをトポソートする。ソートによって課された部分的順序を全体の順序に拡張する（例えば、レベル格子の頂点を整列し、レベルごとにそれらを列挙する）。すべての辺が小さな頂点から大きな頂点に向かうことに注目してください。

ここでは、無秩序なエッジを全体の順序（小さな頂点から大きい方へ）に向けます。結果グラフにサイクルがないことが容易に分かります（サイクルが存在するには反対方向にエッジがなければなりません）。