密グラフ

数学において、稠密グラフとは、辺の数が最大辺数に近いグラフ（すべての頂点ペアが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です。^[¹^] ${\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}$

グラフのサイズが増加する場合、そのグラフ族はしばしば疎グラフと呼ばれます。コンピュータサイエンスでは、疎グラフのより限定的な定義、例えばやなどが用いられることがあります。この文脈において、稠密グラフは、 $|$ $E$ $|$ がに「近い」グラフとして定義されることもあります。^[²^]^[³^] $D\rightarrow 0$ $|V|\rightarrow \infty$ $|E|=O(|V|\log |V|)$ $|E|=O(|V|)$ $|V|^{2}$

上層密度

上密度は、上で定義したグラフ密度の概念を有限グラフから無限グラフへと拡張したものである。直感的には、無限グラフには、その上密度より小さい任意の密度を持つ任意の大きさの有限部分グラフがあり、その上密度より大きい密度を持つ任意の大きさの有限部分グラフは存在しない。正式には、グラフ $Gの上密度は、密度αを持つ$ $G$ の有限部分グラフが有界数の頂点を持つようなαの値の下限である。エルデシュ・ストーン定理を用いて、上密度は1または超特異比 $0,$ $⁠$ のいずれかにしかならないことが示される。 $1 / 2 ⁠ 、 ⁠ 2 / 3 ⁠ 、 ⁠ 3 / 4 ⁠ 、 ⁠ 4 / 5 ⁠ 、\dots ⁠ n / n + 1 ⁠$ ^{[ 4 ]}

疎グラフと密グラフ

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)$ -タイトグラフである。^[⁵^]

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

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

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

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

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

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

参照

注記

^コールマン＆モレ 1983 .
^コーメン、トーマス・H.、レイサーソン、チャールズ・E.、リベスト、ロナルド・L.、スタイン、クリフォード（2022年）、アルゴリズム入門（第4版）、マサチューセッツ州ケンブリッジ：MITプレス、ISBN 978-0262046305
^ Roughgarden, Tim (2018), Algorithms Illuminated, Part 2: Graph Algorithms and Data Structures (1st ed.), サンフランシスコ, CA: Soundlikeyourself Publishing, LLC, p. 5, ISBN 978-0999282922
^例として、 Diestel 2005、第 5 版、p.10 を参照。 189.
^リーとストレイヌ 2008およびストレイヌとテラン 2009
^ Streinu & Theran 2009 .
^ナッシュウィリアムズ 1964 .
^リック＆ホワイト 1970年。
^ネシェトジル & オッソナ・デ・メンデス 2010。どこにも密集しない場所とどこか密集する場所の二項対立の性質については、 Nešetřil & Ossona de Mendez 2012で議論されています。
^テッレ＆ヴィランジェ 2012 .

参考文献

コールマン、トーマス F. ; モレ、ホルヘ J. (1983)、「疎ヤコビ行列の推定とグラフ彩色問題」、SIAM Journal on Numerical Analysis、20 (1): 187– 209、Bibcode : 1983SJNA...20..187C、doi : 10.1137/0720013
Diestel, Reinhard (2005), Graph Theory , 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、doi : 10.4153/CJM-1970-125-1
Preiss, first (1998), Data Structures and Algorithms with Object-Oriented Design Patterns in 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, Heidelberg: 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 (編)、Algorithms – ESA 2012: 20th Annual European Symposium、リュブリャナ、スロベニア、2012年9月10～12日、Proceedings、Lecture Notes in Computer Science、vol. 7501、Springer、pp. 802– 812、doi : 10.1007/978-3-642-33090-2_69、ISBN 978-3-642-33089-6

さらに読む

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

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

[Cormen-2] コーメン、トーマス・H.、レイサーソン、チャールズ・E.、リベスト、ロナルド・L.、スタイン、クリフォード（2022年）、アルゴリズム入門（第4版）、マサチューセッツ州ケンブリッジ：MITプレス、ISBN 978-0262046305

[Roughgarden-3] Roughgarden, Tim (2018), Algorithms Illuminated, Part 2: Graph Algorithms and Data Structures (1st ed.), サンフランシスコ, CA: Soundlikeyourself Publishing, LLC, p. 5, ISBN 978-0999282922

[4] 例として、 Diestel 2005、第 5 版、p.10 を参照。 189.

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

[FOOTNOTEStreinuTheran2009-6] Streinu & Theran 2009 .

[FOOTNOTENash-Williams1964-7] ナッシュウィリアムズ 1964 .

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

[9] ネシェトジル & オッソナ・デ・メンデス 2010。どこにも密集しない場所とどこか密集する場所の二項対立の性質については、 Nešetřil & Ossona de Mendez 2012で議論されています。

[FOOTNOTETelleVillanger2012-10] テッレ＆ヴィランジェ 2012 .

[

[

[

[ 4 ]

[

[

[

[

[ 9 ]

[