グラフのシャノン容量

グラフ理論において、グラフのシャノン容量は、強いグラフ積の独立した集合の数から定義されるグラフ不変量である。アメリカの数学者クロード・シャノンにちなんで名付けられた。これは、グラフから定義される通信チャネルのシャノン容量を測定し、多項式時間で計算できるロヴァース数によって上限が制限される。しかし、シャノン容量自体の 計算複雑性は不明のままである。

シャノン容量は、特定の信号値が互いに混同される可能性があるノイズの多い通信チャネルを介して送信できる情報量をモデル化します。このアプリケーションでは、混同グラフ^[1]または混同可能性グラフが、混同される可能性のある値のペアを表します。たとえば、通信チャネルに 5 つの離散信号値があり、そのいずれも 1 つの時間ステップで送信できるとします。これらの値は、5 を法とするモジュラー演算で 0、1、2、3、または 4 の 5 つの数値として数学的にモデル化できます。ただし、値がチャネルを介して送信されるときに、受信される値が(mod 5) であるとします。ここで、はチャネル上のノイズを表し、-1 から 1 までの開区間内の任意の実数になります。したがって、受信者が 3.6 などの値を受信した場合、それが元々 3 として送信されたのか、4 として送信されたのかを判別することは不可能です。つまり、2 つの値 3 と 4 が混同される可能性があります。この状況は、長さ 5 のサイクルであるグラフによってモデル化できます。グラフの頂点は、送信できる 5 つの値に対応し、グラフのエッジは、互いに混同される可能性のある値を表します。 ${\displaystyle i}$${\displaystyle i+\xi }$${\displaystyle \xi}$ ${\displaystyle C_{5}}$

この例では、各タイム ステップで明確に送信できる 2 つの値 (たとえば、値 1 と 3) を選択できます。これらの値は十分に離れているため、混同されることはありません。受信者が0 から 2 の間の値を受信すると、送信された値は 1 であると推測でき、受信者が2 から 4 の間の値を受信すると、送信された値は 3 であると推測できます。このように、通信のステップで、送信者は最大で異なるメッセージを送信できます。受信者が区別できる値の最大数は 2 つです。値 0、1、2、3、4 の 3 つ以上のサブセットには、混同される可能性のあるペアが少なくとも 1 つ含まれます。チャネルにはタイム ステップごとに送信できる値が 5 つありますが、このコーディング スキームで使用できるのは実質的にそのうちの 2 つだけです。 ${\displaystyle x}$${\displaystyle x}$${\displaystyle n}$${\displaystyle 2^{n}}$

ただし、より複雑なコーディング方式では、長さが 1 より大きいコードワードを使用することで、同じチャネルを介してより多くの情報を送信できます。たとえば、送信者が 2 つの連続したステップで 5 つのコードワード「11」、「23」、「35」、「54」、または「42」のいずれかを送信するとします。(ここで、引用符は、これらのワードを10 進数ではなく記号の文字列として解釈する必要があることを示しています。) これらのコードワードの各ペアには、値が 5 を法として 2 以上異なる位置が少なくとも 1 つ含まれています。たとえば、「11」と「23」は 2 番目の位置で 2 異なり、「23」と「42」は 1 番目の位置で 2 異なります。したがって、これらのコードワードのいずれかを受け取った受信者は、送信されたコードワードを常に明確に判断できます。これらのコードワードの 2 つが互いに混同されることはありません。この方法を使用すると、送信者は通信のステップで最大 のメッセージを通信できます。これは、より単純な 1 桁のコードで送信できるメッセージよりもはるかに多いものです。単位時間ステップあたりに送信できる有効な値の数は です。グラフ理論的に言えば、これは 5 サイクルのシャノン容量が少なくとも であることを意味します。Lovász (1979) が示したように、この制限は厳密です。同じ時間内にさらに多くの異なるメッセージを送信できる、より複雑なコード ワード システムを見つけるのは不可能であるため、5 サイクルのシャノン容量は正確にです。${\displaystyle n}$${\displaystyle 5^{n/2}}$${\displaystyle 2^{n}}$${\textstyle (5^{n/2})^{1/n}={\sqrt {5}}}$${\displaystyle {\sqrt {5}}}$${\displaystyle {\sqrt {5}}}$

グラフが記号の集合と、互いに混同される可能性のある記号のペアを表す場合、記号のサブセットは、グラフ内の独立集合、つまり、どのエッジの両端も含まない頂点のサブセットである場合に限り、混同される可能性のあるペアをすべて回避します。互いに区別できる記号のサブセットの最大可能サイズは、グラフの独立数、つまり最大独立集合のサイズです。たとえば、' : 5 サイクルには、2 つの頂点の独立集合がありますが、それより大きくはありません。 ${\displaystyle G}$${\displaystyle S}$${\displaystyle S}$ ${\displaystyle \alpha (G)}$${\displaystyle \alpha (C_{5})=2}$

より長いコードワードの場合、より大きなグラフの独立セットを使用して、混乱なく送信できるコードワードのセットを記述できます。たとえば、混乱グラフが である 5 つのシンボルの同じ例の場合、長さ 2 のコード方式で使用できる長さ 2 の文字列が 25 個あります。これらの文字列は、25 の頂点を持つグラフの頂点で表すことができます。このグラフでは、各頂点には 8 つの隣接点、つまり混乱する可能性のある 8 つの文字列があります。長さ 2 の文字列のサブセットは、このグラフの独立セットに対応する場合にのみ、混乱の可能性のないコードを形成します。コードワードのセット {"11", "23", "35", "54", "42"} は、最大サイズのこれらの独立セットの 1 つを形成します。 ${\displaystyle C_{5}}$

がチャネルの信号と混同しやすいペアを表すグラフである場合、長さ 2 のコードワードとそれらの混同しやすいペアを表すグラフは であり、記号はグラフ の強積を表します。これは、積の最初の引数の頂点と積の 2 番目の引数の頂点の各ペアに対して頂点を持つグラフです。2 つの異なるペアとが強積で隣接するのは、およびが同一または隣接している場合で、およびが同一または隣接している場合に限ります。より一般的には、長さのコードワードは 、とそれ自体の - 倍の強積であるグラフ で表すことができ、混同せずに送信できるこの長さのコードワードの最大数は、独立数 で与えられます。単位時間ステップあたりに送信される信号の有効数は、この数の 番目の根です。 ${\displaystyle G}$${\displaystyle G\boxtimes G}$${\displaystyle \boxtimes}$${\displaystyle (u,v)}$${\displaystyle (u_{1},v_{1})}$${\displaystyle (u_{2},v_{2})}$${\displaystyle u_{1}}$${\displaystyle u_{2}}$${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle k}$${\displaystyle G_{k}}$${\displaystyle k}$${\displaystyle G}$${\displaystyle \alpha (G_{k})}$${\displaystyle k}$${\displaystyle \alpha (G_{k})^{1/k}}$

これらの概念を用いると、シャノン容量は次のように定義される。

${\displaystyle \Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G_{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G_{k})}},}$

任意の長さの混乱のないコードの時間ステップあたりの有効な信号数の 限界（ が任意に大きくなる場合）。${\displaystyle k}$

シャノン容量の計算量は不明であり、 （ 7頂点のサイクルグラフ）などの特定の小さなグラフのシャノン容量の値さえ不明のままです。^{[2] [3]}${\displaystyle C_{7}}$

この問題に対する自然なアプローチは、与えられたグラフの有限個のべき乗を計算し、それらの独立数を見つけ、これらの数からシャノン容量が定義されるシーケンスの極限動作に関する情報を推測することです。しかし、（これらのグラフの独立数を計算する計算上の困難さ、つまりNP困難問題を無視しても）のべき乗の独立数のシーケンスの予測不可能な動作は、このアプローチを使用してシャノン容量を正確に近似することはできないことを意味しています。^[4]${\displaystyle G}$${\displaystyle G}$

シャノン容量の計算が難しいという理由もあり、研究者たちは計算が容易でシャノン容量の上限を示す他のグラフ不変量を探してきました。

ロヴァース数ϑ( G ) は別のグラフ不変量であり、楕円体法に基づくアルゴリズムによって多項式時間で高精度に数値計算できる。グラフGのシャノン容量は、下からは α( G ) によって、上からは ϑ( G ) によって制限される。^[5]場合によっては、 ϑ( G ) とシャノン容量は一致する。たとえば、五角形のグラフでは、どちらも√ 5に等しい。ただし、シャノン容量とロヴァース数が異なるグラフも存在する。^[6]

ヘーマーズはシャノン容量のもう一つの上限を提示したが、これはロヴァース限界よりも優れている場合がある: ^[7]

${\displaystyle \Theta (G)\leq R(G)=\min _{B}\operatorname {rank} (B),}$

ここで、B はある体上のn  ×  n行列であり、 頂点iとjが隣接していない 場合はb _ii  ≠ 0 かつb _{ij = 0 となります。}