BFSで生成されたツリーの解析

Question

Mathexchangeでこの質問をすることを考えましたが、計算やはい/いいえではありませんが、コンピュータサイエンス関連のアルゴリズムの詳細についてはここでお尋ねします。

BFSアルゴリズムでは、各レベルのトラバーサルをレイヤーとしてマークすることができます。たとえば、sが開始頂点である場合、任意の単一レイヤの頂点はすべてsまでの同じ距離を持つ必要があります。これは、BFS検索アルゴリズムの最も基本的な特性の1つです。

i層と、Tと呼ばれるBFSアルゴリズムで生成されたツリーと、Gと呼ばれるグラフがあるとします。これは、Tの任意の2つのノード間の最大距離がiであることを意味します。 （おそらく開始層から1、及び下層から1）

そのプロパティを使用して、はどのように私は頂点aはその程度がせいぜい6*|V|/iになるようGに存在することを証明することができますか？レイヤL_jの任意の頂点uはせいぜい6|V|/i頂点の合計3つの後件層の存在を示し、層L_j-1とL_j+1の頂点に接続されたエッジを有するので

私は考えました。役立つだろう。

しかし、私は目標を知っていることですが、私はそれにアプローチする方法はわかりません。

Answer 1

アプローチはおそらく次のようなものでなければなりません。レイヤーの3つ組（例：[1,2,3]、[4,5,6] ...）を取ります。そのうちのi/3があり、それらは互いに素である。一緒に、それらはVの頂点を持っています。つまり、<= V/(i/3)のトリプレットがなければなりません（そうでなければ...カウント）。しかしながら、このアプローチは多くとも3V/i度につながる。

たぶんiは（私は2つの頂点間の最大距離としてmそれを呼び出します。私はあなたの文で混乱している

Tにおける任意の2つのノード間の最大距離は私なりの直径でなければなりません

これは真実ではありません - いくつかの頂点については、上に移動しなければなりません）。次に、mは<= 2*iとなり、度が最大で6V/mの頂点になります。