5

親ノード、リーフノード、子ノードG=(V,E)の概念がなく、近傍関係のみの一般的なグラフ構造が与えられた場合に、見つけるアルゴリズム（または一連のアルゴリズム）はありますか？

1）Gそれが木であるかどうか（チェックするだけで十分|V| = |E|+1ですか？）

2）グラフが実際に木である場合、葉とその中心は？（つまり、ツリーの深さを最小化するグラフのノード）

ありがとう

4

3 に答える 3

7

ツリーの「中心」が「ツリーの深さを最小化するグラフのノード」として定義されている場合、直径を見つけるよりも簡単に見つける方法があります。

d[] = degrees of all nodes
que = { leaves, i.e  i that d[i]==1}
while len(que) > 1:
  i=que.pop_front
  d[i]--
  for j in neighbors[i]:
    if d[j] > 0:
      d[j]--
      if d[j] == 1 :
        que.push_back(j)

que に最後に残ったものが中心です。

これは、直径の経路について考えることで証明できます。簡単にするために、直径パスの長さが奇数であると仮定し、パスの中間ノードが一意になるようにします。そのノードを M と呼びましょう。

次のことがわかります。

  1. 直径パス上の他のすべてのノードが que にプッシュされるまで、M は que の後ろにプッシュされません。
  2. M が既に que にプッシュされた後にプッシュされる別のノード N がある場合、N は直径パスよりも長いパス上にある必要があります。したがって、N は存在できません。M は、que で最後にプッシュ (および左) されたノードでなければなりません
于 2012-10-29T00:10:15.443 に答える
2

  1. いいえ、それだけでは不十分です。ツリーはn-1エッジを持つ CONNECTED グラフです。接続されていないグラフにはエッジが存在する可能性がありn-1、それはツリーにはなりません。 BFS
    を実行して、グラフが接続されているかどうかを確認してから、エッジの数を数えることができます。これにより、グラフがツリーである場合に十分な情報が得られます。

  2. 葉は、次の式でv表されるノードの次数を持つノードです(それぞれに接続された頂点が 1 つだけあります)。d(v)d(v) = 1

(1) 答えは無向グラフを想定しています
(2) ここで、nは頂点の数を示します。

于 2012-10-28T22:09:46.720 に答える
2

(1) については、|V| を検証するだけです。= |E| + 1 であり、グラフが完全に接続されていること。

(2) の場合、最大直径を見つけてから、直径パスの中央にあるノードを選択する必要があります。木に対してこれを行う簡単な方法があることを漠然と覚えています。

任意のノードから開始し、aから最大距離にあるノードを見つけて、それをaと呼びますb。次に、 から検索して からb最大距離にあるノードを見つけ、それをbと呼びますc。bからへのパスcは最大直径です。

このような、より便利な方法が他にもあります。 Googleもチェックしてください。

于 2012-10-28T22:10:33.140 に答える