密なグラフ

数学において、密グラフとは、辺の数が最大辺数に近いグラフ（すべての頂点のペアが1つの辺で結ばれているグラフ）のことである。その反対に、辺の数が少ないグラフは疎グラフと呼ばれる。密グラフと疎グラフの区別は明確に定義されておらず、「おおよそ等しい」といった表現で表されることが多い。そのため、密度の定義方法は問題の文脈によって異なる場合が多い。

グラフ密度

単純なグラフを考えてみましょう $(V,E)$ どこ $V$ は頂点の集合であり、 $E$ は辺の集合です。 $|V|$ 頂点の数を表すために、 $|E|$ エッジの数を表す。単純グラフのグラフ密度 $(V,E)$ $は、エッジの数| 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)}}

無向グラフのエッジの最大数は ${\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}$ したがって、最大密度は 1 (完全グラフの場合) であり、最小密度は 0 です。^{[ 1 ]}

サイズが大きくなるグラフの族は、次のような場合に疎であると言われることが多い。 $D\rightarrow 0$ として $|V|\rightarrow \infty$ コンピュータサイエンスでは、スパースの定義をより厳密に定義することもあります。 $|E|=O(|V|\log |V|)$ あるいは $|E|=O(|V|)$ 同じ文脈で、密なグラフは、 $| E |$ が「近い」グラフとして定義できます。 $\displaystyle |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)は $、$ $n$ 個の頂点を持つすべての空でない部分グラフが最大で $kn$ $-$ $l 個$ のエッジを持つ場合、グラフを ( k , l ) -スパースであると定義 $し、 (k,$ $l$ $)$ $-$ $スパース$ $で$ あり、かつちょうど $kn$ $-$ $l$ 個のエッジを持つ場合、グラフを $($ $k$ $,$ $l$ $)$ -タイトであると定義している。したがって、木はまさに(1,1) -タイトグラフであり、森はまさに $(1,1)$ -スパースグラフであり、樹木度 $k$ のグラフはまさに $($ $k$ $,$ $k$ $)$ -スパースグラフである。擬似森はまさに $(1,0)$ -スパースグラフであり、剛性理論で現れるラマングラフはまさに $(2,3)$ -タイトグラフである。^[⁵^]

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

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

グラフ族において、その族のグラフがすべて $($ $k$ $,$ $l$ $) -スパースとなるような$ $k$ と $l$ の存在は、その族のグラフが有界退化または有界有木性を持つことと同値である。より正確には、 Nash-Williams (1964)の結果から、有木性が $a$ 以下のグラフはまさに $($ $a$ $,$ $a$ $)$ -スパースグラフであることが導かれる。^[⁷^] $同様に、退化がd$ 以下のグラフは $\left(d,{\binom {d+1}{2}}\right)$ -疎グラフ。^{[ 8 ]}

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

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

限定された退化を持つグラフのクラスと、どこにも密でないグラフのクラスは、いずれも、完全二部グラフを部分グラフとして除外するグラフ族である、二部グラフを含まないグラフに含まれます。^[¹⁰^]

注記

↑コールマン＆モレ 1983。
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022), Introduction to Algorithms (4th ed.), Cambridge, Massachusetts: The MIT Press, ISBN 978-0262046305
↑ Roughgarden, Tim (2018), Algorithms Illuminated, Part 2: Graph Algorithms and Data Structures (1st ed.), San Francisco, CA: Soundlikeyourself Publishing, LLC, p. 5, ISBN 978-0999282922
↑例として、 Diestel 2005、第 5 版、p. 4 を参照。 189.
↑リーとストレイヌ 2008およびストレイヌとテラン 2009
↑ Streinu & Theran 2009。
↑ナッシュ＝ウィリアムズ 1964 .
↑リック＆ホワイト 1970 .
↑ネシェツィル&オッソナ・デ・メンデス 2010。どこにも密集しない場所とどこか密集する場所の二項対立の性質については、 Nešetřil & Ossona de Mendez 2012で議論されています。
↑ Telle & Villanger 2012。

参考文献

Coleman, Thomas F. ; Moré, Jorge J. (1983)、「疎なヤコビ行列の推定とグラフ彩色問題」、SIAM Journal on Numerical Analysis、20 (1): 187–209、Bibcode : 1983SJNA...20..187C、doi : 10.1137/0720013
Diestel, Reinhard (2005),グラフ理論,大学院数学テキスト, Springer-Verlag, ISBN 3-540-26183-4OCLC 181535575
Lee, Audrey; Streinu, Ileana (2008)、「ペブルゲームアルゴリズムとスパースグラフ」、Discrete Mathematics、308 (8): 1425–1437、arXiv : math/0702129、doi : 10.1016/j.disc.2007.07.104、MR 2392060
Nash-Williams, C. St. JA (1964)、「有限グラフの森への分解」、Journal of the London Mathematical Society、39 (1): 12、doi : 10.1112/jlms/s1-39.1.12、MR 0161333
Lick, Don R; White, Arthur T (1970)、「 $k-$ 退化グラフ」、Canadian Journal of Mathematics、22 (5): 1082–1096、doi : 10.4153/CJM-1970-125-1
Preiss、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, Heidelberg: Springer, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7MR 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

さらに読む

Black, Paul E.、「疎グラフ」、アルゴリズムとデータ構造の辞書、NIST 、 2005年9月29日取得

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

[Cormen-2] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022), Introduction to Algorithms (4th ed.), Cambridge, Massachusetts: The MIT Press, ISBN 978-0262046305

[Roughgarden-3] Roughgarden, Tim (2018), Algorithms Illuminated, Part 2: Graph Algorithms and Data Structures (1st ed.), San Francisco, CA: Soundlikeyourself Publishing, LLC, p. 5, ISBN 978-0999282922

[4] 例として、 Diestel 2005、第 5 版、p. 4 を参照。 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] Telle & Villanger 2012。

[ 1 ]

2

[

粒子

[

[

[

[ 8 ]

[

[

密なグラフ

グラフ密度

上部密度

疎なグラフと密なグラフ

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

関連項目

注記

参考文献

さらに読む

関連するトピック

二部グラフ

数学

グラフ（すべての

頂点