読者です 読者をやめる 読者になる 読者になる

グラフと補グラフの関係

kousuke.hatenablog.com

n頂点の完全グラフをK_n、独立グラフ(頂点のみで辺がないグラフ)を I_nとする。

n頂点のグラフ G_nがある。
このとき K_nから I_nへひとつづつ辺を消していく順序集合のうち、 G_nを含む順序の集合 F_{G_n}を定めることができる。

このとき F_{G_n}のどの順序を通っても G_nの補グラフ G_n^\astはない。
そのため K_n \rightarrow G_n \rightarrow I_n \rightarrow G_n^\ast \rightarrow K_nのような構造を考えることができる。

 K_nの辺の数は \frac{n(n-1)}{2} I_nと位相が \piずれていて、 2\pi K_nに戻るので、上の構造は e^{i\frac{4\pi\,m}{n(n-1)}}と同相と考えることができそう。
同様に G_n,G_n^\astも位相が \pi離れているとみることができそう。

また最大クリーク問題を考えると頂点がなくなる方向K_0への順序集合(こちらは頂点集合)もある。
最大クリーク問題の解は K_n \rightarrow I_n G_n \rightarrow G_n^\astの方向が一致することができる最大のnとみることができる。
なんとなくグラフを複素数多項式として表せるんじゃないかとおもっていて、上の式を頂点方向と辺方向で全微分とかすると、その極大値が最大クリークにならないだろうかとかおもっていたりする。

またイメージとしては K_0, K_n, I_nに対し、 K_0 -> K_0への自己ループの輪( e_{loop})と K_n, I_nを結ぶ輪が通っており、 e_{loop}が縮もうとするときの緊張関係のように考えることができそう。