チーガー定数（グラフ理論）

数学において、グラフのチーガー定数（チーガー数または等周数とも呼ばれる）は、グラフに「ボトルネック」があるかどうかを数値的に表す尺度である。「ボトルネック」の尺度としてのチーガー定数は、多くの分野で大きな関心を集めている。たとえば、よく接続されたコンピュータ ネットワークの構築、カード シャッフルなどである。グラフ理論の概念は、コンパクトなリーマン多様体のチーガー等周定数に由来する。

チーガー定数は数学者 ジェフ・チーガーにちなんで名付けられました。

G を頂点集合V ( G )と辺集合E ( G )を持つ無向有限グラフとします。頂点の集合A ⊆ V ( G )に対して、∂ AはA内の頂点からA外の頂点 ( Aの辺境界と呼ばれることもあります)に向かうすべての辺の集合を表します。

${\displaystyle \partial A:=\{\{x,y\}\in E(G)\ :\ x\in A,y\in V(G)\setminus A\}.}$

辺は順序付けられていない、すなわち、であることに注意する。G のチーガー定数h ( G )は[ 1 ]で定義さ^れる。${\displaystyle \{x,y\}=\{y,x\}}$

${\displaystyle h(G):=\min \left\{{\frac {|\partial A|}{|A|}}\ :\ A\subseteq V(G),0<|A|\leq {\tfrac {1}{2}}|V(G)|\right\}.}$

Cheeger 定数は、G が連結グラフである場合に限り、 厳密に正になります。直感的に、Cheeger 定数が小さいが正である場合、2 つの「大きな」頂点セットがあり、それらの頂点セットの間に「少数の」リンク (エッジ) があるという意味で、「ボトルネック」が存在します。頂点セットを 2 つのサブセットに分割した場合に、その 2 つのサブセット間に「多数の」リンクがある場合、Cheeger 定数は「大きい」です。

理論計算機科学への応用では、 | V ( G )| (ネットワーク内のコンピュータの数) が大きい場合でも、Cheeger 定数が高い (少なくとも、ゼロから離れた範囲にある) ネットワーク構成を考案することが望まれます。

たとえば、グラフG _{Nとして考えられる}N ≥ 3 台のコンピュータのリング ネットワークを考えます。リングの周りを時計回りにコンピュータに1、2、...、N の番号を付けます。数学的には、頂点セットと辺セットは次のように表されます。

${\displaystyle {\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&={\big \{}\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}{\big \}}\end{aligned}}}$

A を、接続されたチェーン内の次のコンピュータ の集合とします。${\displaystyle \left\lfloor {\tfrac {N}{2}}\right\rfloor }$

${\displaystyle A=\left\{1,2,\cdots ,\left\lfloor {\tfrac {N}{2}}\right\rfloor \right\}.}$

それで、

${\displaystyle \partial A=\left\{\left\{\left\lfloor {\tfrac {N}{2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},}$

そして

${\displaystyle {\frac {|\partial A|}{|A|}}={\frac {2}{\left\lfloor {\tfrac {N}{2}}\right\rfloor }}\to 0{\mbox{ as }}N\to \infty .}$

この例は Cheeger 定数h ( G _N )の上限を示していますが、これもN → ∞のときに 0 に近づきます。したがって、リング ネットワークはN が大きい場合に非常に「ボトルネック」になっているとみなされますが、これは実用上非常に望ましくありません。リング上のコンピューターの 1 つに障害が発生するだけで、ネットワークのパフォーマンスが大幅に低下します。隣接していない 2 台のコンピューターに障害が発生すると、ネットワークは 2 つの切断されたコンポーネントに分割されます。

チーガー定数は、グラフのエッジ拡張を測定する方法であるため、エクスパンダーグラフのコンテキストでは特に重要です。いわゆるチーガー不等式は、グラフの固有値ギャップとチーガー定数を関連付けます。より具体的には、

${\displaystyle 2h(G)\geq \lambda \geq {\frac {h^{2}(G)}{2\Delta (G)}}}$

ここで、はグラフのノードの最大次数であり、はグラフのラプラシアン行列のスペクトルギャップである。 ^{[2]チーガー不等式は}スペクトルグラフ理論の基本的な結果であり、その動機である。 ${\displaystyle \Delta (G)}$${\displaystyle G}$${\displaystyle \lambda }$

• スペクトルグラフ理論
• 代数的接続性
• チーガー行き
• コンダクタンス
• 接続性
• エキスパンダーグラフ