0

私は面接のために勉強していて、解決に苦労しているこの質問に出くわしました。こんなふうになります：

無向グラフ G に対して次の 2 つのタスクを実行する効率的なアルゴリズムを作成します。 edge (u,w) ここで、v は次数 2 のエッジです。次数 2 の頂点を削除するとエッジの複数のコピーが作成される可能性があり、エッジの複数のコピーを削除すると次数 2 の頂点が作成される可能性があることに注意してください。

次数2の頂点を削除するとエッジの複数のコピーが作成される方法と、エッジの複数のコピーを削除すると次数2の頂点が作成される方法がよくわかりません。誰かが明確にするのを助けることができますか?

4

2 に答える 2

0

4 つの頂点 w、x、y、z のグラフで

  w *-----  x  -----* y ------- z 
    |               |
    *---------------*

置換規則を使用して (w, x) と (x, y) を (w, y) に置き換えると、見た目よりも w から y に 2 つの平行なエッジがあります。重複したエッジを削除すると、グラフは次のようになります。

  w --------------- y ------- z

したがって、(w, y) と (y, z) を (w, z) に置き換えると、(w, z) になります。

  w ------------------------- z

正確には意図したものではありません

于 2013-11-13T07:13:40.210 に答える