グラフのシャノン容量 - 百科事典

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

通信チャネルのグラフモデル

シャノン容量は、ある信号値が他の信号値と混同される可能性があるノイズのある通信チャネルを通して送信できる情報量をモデル化します。このアプリケーションでは、混同グラフまたは混同グラフが混同される可能性のある値の対を説明します。たとえば、通信チャネルが5つの異なる信号値を持つと仮定します。これらの値は、5の模範数における数0、1、2、3、または4として数学的にモデル化されます。しかし、値


i


がチャネルを通じて送信された場合、受信される値は


i
+
ξ


（mod 5）となります。ここで、


ξ


はチャネルのノイズを表し、-1から1の開区間の任意の実数です。したがって、受信者が3.6のような値を受信した場合、元々送信された値が3か4かを特定することができません。3と4の2つの値は混同される可能性があります。この状況は、送信できる5つの値に対応する頂点を持つ長さ5のサイクル



C

5




でモデル化できます。このグラフの辺は、混同される可能性のある値を表します。

この例では、混同が生じないように各時間ステップで送信できる2つの値を選択することができます。たとえば、値1と3です。これらの値は遠く離れており、混同される可能性がありません：受信者が0から2の間の値を受け取った場合、送信された値が1であったと推測できます。そして、受信者が2から4の間の値を受け取った場合、送信された値が3であったと推測できます。このように、通信のnステップで、送信者は最大


2
n


つの異なるメッセージを通信できます。2は受信者が区別できる最大の値の数です：0、1、2、3、4の値の任意の3つ以上の部分集合には、混同される可能性のある少なくとも1つの対があります。チャネルが各時間ステップごとに5つの値を送信できるにもかかわらず、実際にはこの符号化方式では2つしか使用できません。

しかし、より複雑な符号化方式を使用することで、同じチャネルを通じてより多くの情報を送信することができます。たとえば、2つの連続したステップで、送信者が「11」、「23」、「35」、「54」、「42」の5つの符号のうちの1つを送信すると仮定します。（ここでは、クォート記号はこれらの文字列がシンボルの文字列として、10進数として解釈されるべきであることを示しています。）これらの符号の各対には、5の模範数における値が2以上異なる少なくとも1つの位置があります；たとえば、「11」と「23」は第2位置で2が異なります。そして、「23」と「42」は第1位置で2が異なります。したがって、これらの符号のうちの1つを受け取った受信者は常に明確にどれが送信されたかを特定できます：これらの符号の2つは混同されることはありません。この方法を使用して、通信のnステップで、送信者は最大


5
n
/
2


つのメッセージを通信できます。これはシンプルな1桁のコードで送信できる


2
n


つのメッセージよりもはるかに多いです。各時間ステップごとに送信できる実際の値の数は


(
5
n
/
2
)
1
/
n


=
5


です。

図論的には、これは5サイクルのシャノン容量が少なくとも


5


であることを意味します。ラヴァス（1979年）が示したように、この界は厳密です：同じ時間内にさらに多くの異なるメッセージを送信できるより複雑な符号システムを見つけることはできませんので、5サイクルのシャノン容量は正確に


5


です。

独立集合との関係

グラフ


G


がシンボルの集合と、混同される可能性のあるシンボルの対を表す場合、シンボルの集合


S


が混同される可能性のあるすべての対を避けるのは、Sがグラフの独立集合である場合と同義です。つまり、どの辺の両端も含まない頂点の集合です。シンボルの集合が区別できる最大の可能なサイズは、グラフの独立性数


α
(
G
)


であり、これは最大の独立集合のサイズです。たとえば、


α
(

C

5


)
=
2


：5サイクルには2つの頂点の独立集合がありますが、もっと大きなものはありません。

長い長さの符号のために、長い長さの符号の集合を混同せずに送信できる符号の集合を説明するために、もっと大きなグラフの独立集合を使用することができます。たとえば、同じ例の5つのシンボルの混同グラフ



C

5




に対して、長さ2の符号化方式で使用できる長さ2の文字列が25本あります。これらの文字列は、25つの頂点を持つグラフの頂点として表現できます。このグラフでは、各頂点は8つの隣接頂点を持っており、それが混同される可能性のある8つの文字列です。長さ2の文字列の集合が混同が発生しないコードを形成するのは、それがこのグラフの独立集合に対応する場合のみです。コードワードの集合{"11"、"23"、"35"、"54"、"42"}は最大サイズの1つの独立集合です。

グラフ


G


がチャネルのシグナルと混同される可能性のある対を表す場合、長さ2のコードワードとその混同される可能性のある対を表すグラフは


G
⊠
G


です。ここで、記号


⊠


はグラフの強積を表します。これは、積の第1引数の第1の頂点と第2引数の第1の頂点のペア


(
u
,
v
)


が各々の頂点を持つグラフです。強積の2つの異なるペア


(

u

1


,

v

1


)


と


(

u

2


,

v

2


)


は、


u

1




と


u

2




が同一または隣接しており、


v

1




と


v

2




が同一または隣接している場合に隣接します。より一般に、長さ


k


のコードワードは、


G


とその自己の


k


倍の強積


G
k


で表現できます。この長さのコードワードが混同せずに送信できる最大の数は、独立性数


α
(

G

k


)


で与えられます。各時間ステップごとに送信できる実際のシグナルの数は、この数の


k


倍の根号で与えられます。


α
(

G

k


)
1
/
k


。

これらの概念を使用して、シャノン容量は以下のように定義できます。



Θ
(
G
)
=

sup
k

α
(

G

k


)
k

=

lim
k
→
∞
α
(

G

k


)
k


、


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


これは任意に長い混同が発生しないコードの各時間ステップごとに送信できる実際のシグナルの数の（任意に大きくなる）限界です。

計算複雑性

シャノン容量の計算複雑性は未知で、特定の小さなグラフ（たとえば、7つの頂点を持つサイクルグラフ


C
7


）のシャノン容量の値も未知です。

この問題に対する自然なアプローチは、与えられたグラフ


G


の有限個の冪を計算し、その独立性数を検出し、これらの数からシャノン容量が定義される数列の限界行動に関する情報を推測することですが、これらのグラフの独立性数の計算の計算複雑性を無視しても、Gの冪の独立性数の数列の予測不能な行動により、このアプローチはシャノン容量を正確に近似するためには使用できません。

上限

シャノン容量の計算が難しいことから、研究者たちは、計算が簡単でシャノン容量の制限を提供する他のグラフの不変量を探しています。

= ラヴァス数 =

ラヴァス数 ϑ(G)は、エリプソイド法に基づくアルゴリズムで多項式時間で高精度に計算可能な別のグラフの不変量です。グラフGのシャノン容量は、以下のように下からα(G)で制限され、上からρ(G)で制限されます。

ρ(G)とシャノン容量が一致する場合があります；たとえば、五角形のグラフの場合、両方とも√5です。しかし、シャノン容量とラヴァス数が異なるグラフもあります。

= ヘイマースの界 =

ヘイマースは、ラヴァス界よりも時には良いシャノン容量の上限を提供しました。

ρ(G) ≤ R(G) = min_B rank(B)，

ここでBはあるフィールド上のn × n行列であり、bii ≠ 0であり、iとjが隣接していない場合にはbij = 0です。

参考文献