ジグザグ積

グラフ理論における二項演算

K ₆とC ₅のジグザグ積 ${\displaystyle G\circ H}$

グラフ理論において、正則グラフのジグザグ積は、大きなグラフ ( ) と小さなグラフ ( ) を取り、大きなグラフのサイズを近似的に継承し、小さなグラフの次数を継承するグラフを生成する二項演算です。ジグザグ積の重要な特性は、 が良い拡張子である場合、結果のグラフの拡張は の拡張よりもわずかに劣るだけであるということです ${\displaystyle G,H}$ ${\displaystyle G\circ H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$

大まかに言えば、ジグザグ積は、の各頂点をのコピー（クラウド）に置き換え、クラウド内で小さなステップ（ジグ）を移動することで頂点を接続し、続いて2つのクラウド間で大きなステップ（ザグ）を移動し、最後に目的のクラウド内で別の小さなステップを実行します。より具体的には、各辺の始点と終点は、 2つのグラフの置換積の点から始まるこの「ジグザグジグ」プロセスの始点と終点にあります。 ${\displaystyle G\circ H}$ ${\displaystyle G}$ ${\displaystyle H}$

ジグザグ積は、Reingold、Vadhan、Wigderson（2000）によって導入されました。ジグザグ積が最初に導入されたとき、定数次数の拡張子と抽出子の明示的な構築に使用されました。その後、ジグザグ積は計算複雑性理論において、対称対数空間と対数空間が等しいことを証明するために使用されました（Reingold 2008）。

定義

を回転写像を持つ上の -正則グラフとし、を回転写像を持つ 上の -正則グラフとします。ジグザグ積は、回転写像が以下のようになる-正則グラフとして定義されます。 ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle [N]}$ ${\displaystyle \mathrm {Rot} _{G}}$ ${\displaystyle H}$ ${\displaystyle d}$ ${\displaystyle [D]}$ ${\displaystyle \mathrm {Rot} _{H}}$ ${\displaystyle G\circ H}$ ${\displaystyle d^{2}}$ ${\displaystyle [N]\times [D]}$ ${\displaystyle \mathrm {Rot} _{G\circ H}}$
${\displaystyle \mathrm {Rot} _{G\circ H}((v,a),(i,j))}$

1. とします。 ${\displaystyle (a',i')=\mathrm {Rot} _{H}(a,i)}$
2. とします。 ${\displaystyle (w,b')=\mathrm {Rot} _{G}(v,a')}$
3. とします。 ${\displaystyle (b,j')=\mathrm {Rot} _{H}(b',j)}$
4. 出力。 ${\displaystyle ((w,b),(j',i'))}$

性質

次数の縮小

ジグザグ積の定義から、グラフを-正則な新しいグラフに変換することは明らかです。したがって、が よりも大幅に大きい場合、ジグザグ積は の次数を低下させます。大まかに言えば、 の各頂点をのサイズのクラウドに増幅することにより、は実際には元の各頂点の辺を、それを置き換えるクラウドの頂点間で分割します。 ${\displaystyle G}$ ${\displaystyle d^{2}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$

スペクトルギャップの保存

グラフの展開はスペクトルギャップによって測定でき、ジグザグ積の重要な特性はスペクトルギャップの保存です。つまり、 が「十分に良い」エクスパンダー（大きなスペクトルギャップを持つ）である場合、ジグザグ積の展開は の元の展開に近くなります。 ${\displaystyle H}$ ${\displaystyle G}$

正式には、 グラフを、（関連するランダムウォークの）2番目に大きい固有値の絶対値が最大 である、頂点 上の任意の -正則グラフと定義します。 ${\displaystyle (N,D,\lambda )}$ ${\displaystyle D}$ ${\displaystyle N}$ ${\displaystyle \lambda }$

を -グラフ、 を-グラフとすると、 は-グラフであり、ここでです。 ${\displaystyle G_{1}}$ ${\displaystyle (N_{1},D_{1},\lambda _{1})}$ ${\displaystyle G_{2}}$ ${\displaystyle (D_{1},D_{2},\lambda _{2})}$ ${\displaystyle G_{1}\circ G_{2}}$ ${\displaystyle (N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))}$ ${\displaystyle f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2}}$

連結性の保存

ジグザグ積はの各連結成分に対して個別に作用します。 ${\displaystyle G\circ H}$ ${\displaystyle G}$

正式には、 （上の -正則グラフ）と （上の -正則グラフ）の2つのグラフが与えられ、がの連結成分である場合、であり、ここでは によって誘導されるの部分グラフ（つまり、の頂点間の のすべての辺を含む上のグラフ）です。 ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle [N]}$ ${\displaystyle H}$ ${\displaystyle d}$ ${\displaystyle [D]}$ ${\displaystyle S\subseteq [N]}$ ${\displaystyle G}$ ${\displaystyle G|_{S}\circ H=G\circ H|_{S\times D}}$ ${\displaystyle G|_{S}}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$

応用

定数次エクスパンダーの構築

2002年、オマー・ラインゴールド、サリル・ヴァダン、アヴィ・ウィグダーソンは、定数次数エクスパンダーグラフの単純で明示的な組み合わせ論的構成を提示しました。この構成は反復的であり、基本的な構成要素として、定数サイズの単一のエクスパンダーが必要です。各反復において、ジグザグ積を用いて、サイズは増加しますが次数と拡張は変化しない別のグラフを生成します。このプロセスが継続され、任意の大きさのエクスパンダーが生成されます。

上記のジグザグ積の特性から、大きなグラフと小さなグラフの積は、大きなグラフと同様のサイズと小さなグラフと同様の次数を継承しながら、両方の拡張特性を保持するため、悪影響を与えることなく拡張器のサイズを増やすことができることがわかります。

対数空間における無向st連結性の問題の解決

2005年、オマー・ラインゴールドは、無向グラフ内の2つの与えられた頂点間にパスがあるかどうかをテストする問題である無向st連結性を、対数空間のみを使用して解くアルゴリズムを導入しました。このアルゴリズムはジグザグ積に大きく依存しています

大まかに言えば、対数空間における無向st連結問題を解くには、入力グラフをべき乗とジグザグ積の組み合わせを用いて、対数直径を持つ定数次数の正則グラフに変換します。べき乗積は次数の増加を犠牲にして拡張を増加させ（したがって直径を減少させ）、ジグザグ積は拡張を維持しながら次数を減らすために使用されます。

参照

• グラフ演算

参考文献

• Reingold, O. ; Vadhan, S. ; Wigderson, A. (2000)、「エントロピー波、ジグザググラフ積、そして新しい定数次数拡張器と抽出器」、Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS)、pp.  3– 13、arXiv : math/0406038、doi :10.1109/SFCS.2000.892006、ISBN 0-7695-0850-2。
• Reingold, O (2008)、「対数空間における無向接続性」、Journal of the ACM、55 (4): Article 17、24ページ、doi :10.1145/1391289.1391291。
• Reingold, O. ; Trevisan, L. ; Vadhan, S. (2006)、「正則有向グラフ上の擬似ランダムウォークとRL vs. L問題」、Proc. 38th ACM Symposium on Theory of Computing (STOC)、pp.  457– 466、doi :10.1145/1132516.1132583、ISBN 1-59593-134-1。

「https://en.wikipedia.org/w/index.php?title=Zig-zag_product&oldid=1303566182」より取得