0

n ノード、m エッジの無向グラフ G = (V; E) があり、s と t という 2 つの異なるノードがあるとします。s と t の間の距離が厳密に n/2 より大きいとします。s から t へのすべてのパスが v を通過するような s および t とは異なるノード v があることを示します。そのような頂点 nd の実行時間 O(n + m) のアルゴリズムを与えてください。アルゴリズムが正しいことを証明する必要はありませんが、v のような頂点が存在することを証明する必要があります。

この過去の紙の質問に対する正確な答えがわかりません。助けてください!

4

1 に答える 1

1

s と t の間にノードを共有しない 2 つのパスがあるとします。s と t の間の距離が > n/2 であるため、各パスには s と t の間に >= n/2 のノードがあります。これは、グラフに >= n+2 個のノードがあることを意味します。これは矛盾です。

アルゴリズムの場合、パスを見つけて、パスノードを使用せずに片側に接続されているサブグラフがどこで終了するかを確認するだけで十分です。詳細は次のとおりです。

  • s が探しているノード以外の 1 つのノードにのみ接続されている場合。
  • そうでない場合は、s から BFS を作成します。
  • パス st を見つける
  • パス st のノードからのエッジを使用せずに s に接続されたノードを見つける
  • 接続部分にあるパス st の最後のノードは、探しているノードです。
于 2013-10-04T16:08:52.793 に答える