グラフ帯域幅

グラフ理論において、グラフバンド幅問題は、グラフGのn 個の 頂点 v _iに異なる整数⁠ ⁠ のラベルを付けて、その量が最小になるようにすることです ( EはGの辺集合です)。^{[1]この問題は、最長辺の長さが最小になるように、グラフの頂点を}x軸 に沿った異なる整数点に配置するという形で視覚化できます。このような配置は、線形グラフ配置、線形グラフレイアウト、または線形グラフ配置と呼ばれます。^[2] ${\displaystyle f(v_{i})}$${\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$

重み付きグラフ帯域幅問題は、エッジに重みw _ijが割り当てられ、最小化されるコスト関数がとなる一般化です。 ${\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$

行列の観点から見ると、（重み付けされていない）グラフ帯域幅は、グラフの隣接行列である対称行列の最小帯域幅です。帯域幅は、特定のグラフの適切な区間スーパーグラフの最大クリークサイズより 1 小さい値として定義することもできます。この値は、クリーク サイズを最小化するように選択されます（Kaplan & Shamir 1996）。

固定に対して、すべての集合 に対して定義されます。は、区間 から形成される対応する区間グラフです。 これらは、帯域幅 を持つグラフの適切な区間グラフです。 これらのグラフは、区間を周期的な順序で層に割り当てることができ 、層の区間が交差しないため、周期的区間グラフと呼ばれ ます。 ${\displaystyle k}$${\displaystyle i}$${\displaystyle I_{k}(i):=[i,i+k+1)}$${\displaystyle G_{k}(n)}$${\displaystyle I_{k}(1),I_{k}(2),...I_{k}(n)}$${\displaystyle k}$${\displaystyle L_{1},L_{2},...L_{k+1}}$

したがって、パス幅との関係がわかります。パス幅制限グラフはマイナークローズですが、周期的区間グラフのサブグラフの集合はそうではありません。これは、次数 2 の頂点を循環させると帯域幅が増加する可能性があるという事実から生じます。

エッジに交互に頂点を追加すると、帯域幅が減少する可能性があります。ヒント: 最後の問題は、 トポロジ帯域幅として知られています。帯域幅に関連する別のグラフ測定は、二分帯域幅です 。

いくつかのグラフ ファミリでは、帯域幅は明示的な式によって与えられます。 ${\displaystyle \varphi (G)}$

n頂点のパスグラフ P _nの帯域幅は1 であり、完全グラフK _mの場合はとなる。完全二部グラフK _{m , n}の場合、 ${\displaystyle \varphi (K_{n})=n-1}$

${\displaystyle \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n}$、仮定すると${\displaystyle m\geq n\geq 1,}$

これはChvátalによって証明された。^[3]この式の特別なケースとして、k  + 1頂点上のスターグラフは 帯域幅を持つ。 ${\displaystyle S_{k}=K_{k,1}}$${\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}$

頂点上の超立方体グラフの 帯域 幅は、Harper (1966) によって次のように決定されました。${\displaystyle Q_{n}}$${\displaystyle 2^{n}}$

${\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}$

Chvatálováは^[4]、m  ×  n 正方格子グラフ の帯域幅、つまり頂点と頂点上の2つのパスグラフの直積がmin{ m , n }に等しいことを示しました。 ${\displaystyle P_{m}\times P_{n}}$${\displaystyle m}$${\displaystyle n}$

グラフのバンド幅は、他の様々なグラフパラメータによって制限される。例えば、χ( G ) をGの彩色数とすると、

${\displaystyle \varphi (G)\geq \chi (G)-1;}$

Gの直径をdiam( G )とすると、次の不等式が成り立つ: ^[5]

${\displaystyle \lceil (n-1)/\operatorname {diam} (G)\rceil \leq \varphi (G)\leq n-\operatorname {diam} (G),}$

ここで、は の頂点の数です。 ${\displaystyle n}$${\displaystyle G}$

グラフG の帯域幅がkの場合、そのパス幅は最大でk (Kaplan & Shamir 1996)、ツリーの深さは最大でk  log( n / k ) (Gruber 2012) です。対照的に、前のセクションで述べたように、構造的に非常に単純なツリーの例であるスターグラフS _{k は、比較的大きな帯域幅を持ちます。S k}のパス幅は 1 で、ツリーの深さは 2 である ことに注意してください。

制限次数のグラフ族の中には、線形以下の帯域幅を持つものがある。Chung (1988) は、T が最大次数 ∆ の木である場合、

${\displaystyle \varphi (T)\leq {\frac {5n}{\log _{\Delta }n}}.}$

より一般的には、最大次数が∆以下の平面グラフに対しても同様の境界が成り立つ（Böttcher et al. 2010を参照）。

${\displaystyle \varphi (G)\leq {\frac {20n}{\log _{\Delta }n}}.}$

重み付けなしバージョンと重み付けバージョンはどちらも、2次ボトルネック割り当て問題の特殊なケースです。帯域幅の問題は、いくつかの特殊なケースでもNP困難です。 ^{[6]効率的な}近似アルゴリズムの存在に関しては 、帯域幅を任意の定数内で近似することはNP困難であることが知られており、これは入力グラフが最大毛の長さ2のキャタピラーツリーに制限されている場合でも当てはまります（Dubey、Feige、Unger 2010）。密なグラフの場合、3近似アルゴリズムがKarpinski、Wirtgen、Zelikovsky（1997）によって設計されました。一方、多項式で解決可能な特殊なケースが多数知られています。^[2]低帯域幅の線形グラフレイアウトを取得するためのヒューリスティックアルゴリズムは、 Cuthill-McKeeアルゴリズムです。グラフ帯域幅計算のための高速マルチレベルアルゴリズムは、で提案されました。^[7]

この問題への関心は、いくつかの応用分野から生まれています。

1 つの領域は疎行列/バンド行列の処理であり、この領域の一般的なアルゴリズム(Cuthill-McKee アルゴリズムなど) は、グラフ帯域幅問題の近似解を見つけるために適用できます。

もう 1 つの応用分野は、電子設計自動化です。標準セル設計手法では、通常、標準セルの高さは同じで、複数の行に配置されます。このコンテキストでは、グラフ帯域幅問題は、最大伝播遅延(ワイヤの長さに比例すると想定) を最小化することを目的として、標準セルのセットを 1 行に配置する問題をモデル化します。

• Cutwidthとpathwidth は、グラフの線形レイアウトを含むさまざまな NP 完全最適化問題です。

• Böttcher, J.; Pruessmann, KP; Taraz, A.; Würfl, A. (2010). 「制限次数グラフの帯域幅、拡張、ツリー幅、セパレータ、普遍性」。European Journal of Combinatorics . 31 (5): 1217–1227. arXiv : 0910.3014 . doi :10.1016/j.ejc.2009.10.010.
• Chinn, PZ ; Chvátalová, J.; Dewdney, AK ; Gibbs, NE (1982). 「グラフと行列の帯域幅問題 - 概要」. Journal of Graph Theory . 6 (3): 223–254. doi :10.1002/jgt.3190060302.
• Chung, Fan RK (1988)、「グラフのラベル付け」、Beineke, Lowell W.、Wilson, Robin J. (編)、『グラフ理論の選択されたトピック』(PDF)、Academic Press、pp. 151–168、ISBN 978-0-12-086203-0
• Dubey, C.; Feige, U.; Unger, W. (2010). 「帯域幅を近似するための困難性の結果」. Journal of Computer and System Sciences . 77 : 62–90. doi : 10.1016/j.jcss.2010.06.006 .
• ガリー、MR ;ジョンソン、DS (1979)。コンピュータと扱いにくさ：NP完全性理論ガイド。ニューヨーク：WHフリーマン。ISBN 0-7167-1045-5。
• グルーバー、ヘルマン (2012)、「バランスセパレータ、ツリー幅、サイクルランクについて」、Journal of Combinatorics、3 (4): 669–682、arXiv : 1012.1344、doi :10.4310/joc.2012.v3.n4.a5
• Harper, L. (1966). 「グラフ上の最適番号付けと等周問題」.組合せ理論ジャーナル. 1 (3): 385–393. doi : 10.1016/S0021-9800(66)80059-5 .
• Kaplan, Haim; Shamir, Ron (1996)、「小さなクリークを持つ適切な区間グラフへのパス幅、帯域幅、および完了問題」、SIAM Journal on Computing、25 (3): 540–561、doi :10.1137/s0097539793258143
• Karpinski, Marek; Wirtgen, Jürgen; Zelikovsky, Aleksandr ( 1997). 「密なグラフの帯域幅問題に対する近似アルゴリズム」。計算複雑性に関する電子コロキウム。4 (17)。

• 最小帯域幅問題、Pierluigi Crescenzi および Viggo Kann (編)、『NP 最適化問題の概要』。2010年 5 月 26 日にアクセス。