密なグラフ

数学において、密なグラフとは、辺の数が最大辺数に近いグラフ（すべての頂点のペアが 1 つの辺で接続されているグラフ）です。その反対で、辺の数が少ないグラフは疎なグラフです。密なグラフと疎なグラフの区別は明確に定義されておらず、多くの場合、「ほぼ等しい」という表現で表されます。このため、密度の定義方法は多くの場合、問題のコンテキストによって異なります。

単純グラフのグラフ密度は、最大可能エッジ数に対するエッジ数 $| E |の比として定義されます。$

無向単純グラフの場合、グラフ密度は次のようになります。

D={\frac {|E|}{\binom {|V|}{2}}}={\frac {2|E|}{|V|(|V|-1)}}

有向グラフの場合、可能な最大辺数は無向グラフの 2 倍になります (辺には 2 つの方向があるため)。そのため、密度は次のようになります。

D={\frac {|E|}{2{\binom {|V|}{2}}}}={\frac {|E|}{|V|(|V|-1)} }

ここで、 $E$ はグラフの辺の数、 $V は$ グラフの頂点の数です。無向グラフの最大辺数はなので、最大密度は 1 (完全グラフの場合)、最小密度は 0 です。^[1] ${\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}$

増加するサイズのグラフの族については、の場合、しばしばそのグラフをスパースと呼びます。コンピュータサイエンスでは、やのように、より限定的なスパースの定義が使用されることもあります。 $D\rightarrow 0$ $|V|\rightarrow \infty$ $|E|=O(|V|\log |V|)$ $|E|=O(|V|)$

上限密度

上密度は、上で定義したグラフ密度の概念を有限グラフから無限グラフに拡張したものです。直感的には、無限グラフには、その上密度より小さい密度を持つ任意の大きさの有限部分グラフがあり、その上密度より大きい密度を持つ任意の大きさの有限部分グラフはありません。正式には、グラフ G の上密度は、密度 α を持つ G の有限部分グラフが頂点の数に制限があるような値 α の下限 $です$ $。$ エルデシュ-ストーン定理を使用して、上密度は 1 または超特異比 $0、$ $⁠$ のいずれかにしかならないことが示されます。 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2⁠、⁠2/3⁠、⁠3/4⁠、⁠4/5⁠、… ⁠ん/1 + 1です⁠$ ^[2]

疎で密なグラフ

Lee & Streinu (2008) および Streinu & Theran (2009) は、グラフが $(k, l) -スパースであるとは、$ $n$ 頂点を持つすべての空でない部分グラフが最大で $kn - l 個$ の辺を持つ場合であり、 $(k, l)$ -タイトであるとは、 $(k, l) -スパースでちょうど$ $kn - l 個$ の辺を持つ場合であると定義しています。したがって、木はまさに $(1,1)$ -タイトグラフであり、森はまさに ( $1,1)$ -スパースグラフであり、樹木度 $kのグラフはまさに$ $(k, k)$ -スパースグラフです。擬似森はまさに $(1,0)$ -スパースグラフであり、剛性理論で生じるラマングラフはまさに $(2,3)$ -タイトグラフです。^[3]

疎性によって特徴付けられない他のグラフ族も、この方法で記述できます。たとえば、 $n$ 頂点を持つ任意の平面グラフは最大で $3$ $n$ $- 6$ 辺を持ち (3 頂点未満のグラフを除く)、平面グラフの任意のサブグラフは平面であるという事実は、平面グラフが $(3,6)$ -疎であることを意味します。ただし、すべての $(3,6)$ -疎グラフが平面であるわけではありません。同様に、外平面グラフは $(2,3)$ -疎であり、平面二部グラフは $(2,4)$ -疎です。

$StreinuとTheranは、 k$ と $l$ が整数で $0 \leq$ $l$ $< 2$ $k$ $のとき、 (k, l)$ -スパース性のテストは多項式時間で実行できることを示している。^[4]

グラフ族について、族内のグラフがすべて $($ $k$ $,$ $l$ $) -スパースであるような$ $k$ と $l$ の存在は、族内のグラフが有界退化を持つか、有界樹状性を持つことと同値である。より正確には、ナッシュ・ウィリアムズ (1964) の結果から、樹状性が最大で $a$ のグラフはまさに $($ $a$ $,$ $a$ $)$ -スパースグラフであることがわかる。^{[5]同様に、退化が最大で} $d$ のグラフは-スパースグラフである。^[6] $\left(d,{\binom {d+1}{2}}\right)$

グラフの疎クラスと密クラス

Nešetřil & Ossona de Mendez (2010) は、スパース性と密度性の二分法では、単一のグラフインスタンスではなく、無限のグラフクラスを考慮する必要があると考えた。彼らは、どこか稠密なグラフクラスを、すべての完全グラフがそのクラス内のグラフのサブグラフのtサブディビジョンとして現れるような閾値tが存在するグラフのクラスと定義した。逆に、そのような閾値が存在しない場合、そのクラスはどこにも稠密ではない。^[7]

有界退化グラフとどこにも稠密でないグラフのクラスは両方とも、完全な二部グラフをサブグラフとして除外するグラフ族である二部グラフフリーグラフに含まれます。 ^[8]

参照

注記

^ コールマン＆モレ 1983年。
^ 例えば、Diestel 2005、第 5 版、p. 4 を参照。 189.
^ リーとストレイヌ 2008 およびストレイヌとテラン 2009
^ Streinu & Theran 2009年。
^ ナッシュウィリアムズ 1964年。
^ リック＆ホワイト 1970年。
^ Nešetřil & Ossona de Mendez 2010。どこにも密集しない場所とどこか密集する場所の二項対立の性質については、Nešetřil & Ossona de Mendez 2012 で議論されています。
^ テル＆ヴィランジェ 2012年。

参考文献

コールマン、トーマス F. ; モレ、ホルヘ J. (1983)、「スパースヤコビ行列の推定とグラフ着色問題」、SIAM Journal on Numerical Analysis、20 (1): 187– 209、doi :10.1137/0720013
ディーステル、ラインハルト（2005）、グラフ理論、Graduate Texts in Mathematics、Springer-Verlag、ISBN 3-540-26183-4、OCLC 181535575
Lee, Audrey; Streinu, Ileana (2008)、「小石ゲームアルゴリズムとスパースグラフ」、離散数学、308 (8): 1425– 1437、arXiv : math/0702129、doi :10.1016/j.disc.2007.07.104、MR 2392060
ナッシュ・ウィリアムズ、C. St. JA (1964)、「有限グラフのフォレストへの分解」、ロンドン数学会誌、39 (1): 12、doi :10.1112/jlms/s1-39.1.12、MR 0161333
リック、ドン R; ホワイト、アーサー T (1970)、「k-縮退グラフ」、カナダ数学ジャーナル、22 (5): 1082– 1096
Preiss, first (1998)、C++ におけるオブジェクト指向設計パターンによるデータ構造とアルゴリズム、John Wiley & Sons、ISBN 0-471-24134-2
Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2010)、「スパースグラフからどこにも密でない構造へ: 分解、独立性、双対性、限界」、ヨーロッパ数学会議、ヨーロッパ数学会、pp. 135– 165
Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、ハイデルベルク: Springer、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058
Streinu, I. ; Theran, L. (2009)、「スパースハイパーグラフとペブルゲームアルゴリズム」、European Journal of Combinatorics、30 (8): 1944– 1964、arXiv : math/0703921、doi :10.1016/j.ejc.2008.12.018
Telle, Jan Arne; Villanger, Yngve (2012)、「バイクリークフリーグラフにおける支配のための FPT アルゴリズム」、Epstein, Leah、Ferragina, Paolo (編)、アルゴリズム – ESA 2012: 第 20 回欧州シンポジウム、スロベニア、リュブリャナ、2012 年 9 月 10 ～ 12 日、議事録、Lecture Notes in Computer Science、vol. 7501、Springer、pp. 802 ～ 812、doi :10.1007/978-3-642-33090-2_69

さらに読む

ブラック、ポール E.、「スパースグラフ」、アルゴリズムとデータ構造の辞書、NIST 、 2005 年9 月 29 日取得

[FOOTNOTEColemanMoré1983-1] コールマン＆モレ 1983年。

[2] 例えば、Diestel 2005、第 5 版、p. 4 を参照。 189.

[3] リーとストレイヌ 2008 およびストレイヌとテラン 2009

[FOOTNOTEStreinuTheran2009-4] Streinu & Theran 2009年。

[FOOTNOTENash-Williams1964-5] ナッシュウィリアムズ 1964年。

[FOOTNOTELickWhite1970-6] リック＆ホワイト 1970年。

[7] Nešetřil & Ossona de Mendez 2010。どこにも密集しない場所とどこか密集する場所の二項対立の性質については、Nešetřil & Ossona de Mendez 2012 で議論されています。

[FOOTNOTETelleVillanger2012-8] テル＆ヴィランジェ 2012年。