ランダムグラフの直径が重要なのはなぜですか?
最長最短経路の長さとして定義されるグラフの直径は、ランダムグラフ(ランダムグラフなど)では自明ではない量であることがわかります。$G(n,p)$ 間にエッジを追加することによって形成されます $n$ 確率で独立してポイント $p$。
しかし、何がそれを数学的に重要なものにしているのでしょうか?他の基本的なグラフのアイデアとどのような関係がありますか?さらに、次数分布や頂点の空間的制約(ランダムな幾何学的グラフ)など、グラフに何らかの制約を追加すると、グラフの直径の重要性にどのような影響がありますか?
回答
グラフの直径は、彩色数や最大次数と同じように、それ自体が重要です。グラフでネットワークをモデル化する場合は、あるノードから別のノードに移動するために必要な「ホップ」の最大数がわかります。グラフが、たとえば、各エッジが長さ1の直線であるグラフのように幾何学的に埋め込まれている場合、(抽象的な)グラフの直径は、埋め込まれたグラフの直径の上限であり、のサブセットと見なされます。$\mathbb{R}^n$。
しましょう $D$ グラフの直径であり、 $n$ その順序、 $\Delta$ その最大度と $\kappa$その接続性。直径がどのように動作するかに関するいくつかの一般的なヒューリスティック(これらは傾向であり、定理ではありません):
- グラフの直径が小さく、頂点が多い場合は、多くのエッジが必要です。これらのエッジは、2つの頂点が遠く離れないように、ある程度「均一」に分布している必要があります。
- グラフの直径が頂点の数に比べて非常に大きい場合、グラフのエッジは少なくなります。
- 上記の点と同様に、直径と最大次数は、グラフが持つことができる頂点の総数を制限します。ヒューリスティックに、深さのツリーを作成する場合よりも多くの頂点をグラフから取得することはできません。$D$ 大まかに分岐します $\Delta-1$各レイヤーで、物事を閉じるためのいくつかの余分なエッジがあります。この限界を研究することは、次数直径問題のトピックです。
- 直径と最大次数が制限されている間 $n$上から、直径と接続性が下からそれをバインドしました。境界はおおよそのように見えます$n \geq \kappa \cdot (D-1)$。
- 直径もグラフの周囲を制約します。つまり、直径が小さく、グラフに任意のサイクルが含まれている場合は、短い長さのサイクルが含まれている必要があります。
最後に、直径は優れた複雑さの制約として機能します。一般的なグラフの構造や特徴を研究しようとしていて、絶望的に失われている場合は、直径2のグラフで何が起こるかを検討すると便利です(特に、それに伴う他の制約や制限されたグラフクラスが与えられます)。これは、ほとんどすべてのグラフの直径が2であることを非常に偶然にしています!