グラフパワー

数学の一分野であるグラフ理論において、無向グラフ $G$ の $k$ 乗 $G k$ は、同じ頂点集合を持つ別のグラフであるが、 $G$ 内での2 つの頂点間の距離が最大で $k$ であるとき、それらの頂点は隣接している。グラフのべき乗は、数の累乗と同様の用語を使用して表される。G $2$ $は$ $G$ の平方、G $3$ $は$ $G$ の立方などと呼ばれる。 ^[1]

グラフのべき乗は、グラフ自身との積とは区別する必要があります。グラフのべき乗は、(べき乗とは異なり) 一般に元のグラフよりも多くの頂点を持ちます。

プロパティ

グラフの直径が $d$ であれば、その $d$ 乗は完全グラフです。^[2]グラフ族のクリーク幅が制限されている場合、任意の固定 $dに対してその$ $d$ 乗も制限されます。^[3]

着色

グラフの四角形上のグラフの色付けは、無線通信ネットワークの参加者に周波数を割り当てて、2つの参加者が共通の隣接周波数で互いに干渉しないようにするために使用できます。 ^{[4]また、高い}角度分解能でグラフ描画を見つけるためにも使用できます。^[5]

最大次数 $Δの$ 平面グラフの $k$ 乗の彩色数と退化はともに $O$ $(Δ$ $⌊$ $k$ $/2⌋$ $)$ であり、退化の境界は、貪欲な彩色アルゴリズムを使用してグラフをこれだけの色数で彩色できることを示しています。^[4]平面グラフの正方形の特殊なケースについて、ウェグナーは1977年に、平面グラフの正方形の彩色数は最大で $max(Δ + 5,$ $⁠$ $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}3Δ/2⁠ + 1)$ であり、彩色数は最大で $⁠であることが知られている。$ $5Δ / 3 ⁠ + O (1)$ 。^[6]^[7]より一般的には、退化度 $d$ と最大次数 $Δ を$ 持つ任意のグラフに対して、グラフの平方の退化度は $O (d Δ)$ であるため、平面グラフ以外の多くの種類の疎グラフにも、彩色数が $Δ$ に比例する平方が存在します。

$最大次数Δ$ の非平面グラフの平方の彩色数は最悪の場合 $Δ2$ に比例するかもしれないが、高内周グラフの場合はより小さくなり、この場合は $O$ $(Δ2$ $/$ $logΔ$ $)$ $で$ 制限される。 ^[8]

グラフの正方形を着色するために必要な色の最小数を決定することは、平面の場合であってもNP困難である。 ^[9]

ハミルトン性

連結グラフの立方体には必ずハミルトン閉路が含まれる。^[10]連結グラフの平方が必ずしもハミルトンであるとは限らず、平方がハミルトンであるかどうかを判断することはNP完全である。 ^[11]ただし、フライシュナーの定理によれば、 2頂点連結グラフの平方は常にハミルトンである。^[12]

計算の複雑さ

$n$ 頂点と $m$ 辺を持つグラフの k 乗は、各 $頂点$ から始めて他のすべての頂点までの距離を決定する幅優先探索を実行することによって、時間 $O$ $($ $mn$ $)で計算できますが、より洗練されたアルゴリズムを使用すると少し速くなります。$ ^[13]あるいは、 $A が$ グラフの隣接行列であり、その主対角線上に非ゼロのエントリを持つように変更されている場合、 $A$ $k$ の非ゼロのエントリはグラフの $k$ 乗の隣接行列を与え、 ^[14]そこから、 $k乗の構築は、$ 行列乗算の時間の対数係数以内の時間で実行できることがわかります。

木のk $乗$ は入力グラフのサイズに比例した時間で認識できる。 ^[15]

グラフが与えられたとき、それが別のグラフの平方であるかどうかを判断することはNP完全である。 ^[16]さらに、与えられた数 $k$ $\geq 2$ に対してグラフが別のグラフの $k乗であるかどうか、または$ $k$ $> 2$ に対して二部グラフの $k$ 乗であるかどうかを判断することもNP完全である。^[17]

誘導サブグラフ

二部グラフ $G$ の半正方形は、 $G$ の二分割の片側によって誘導される $G$ $2$ のサブグラフです。マップグラフは平面グラフの半正方形であり、^[18]半立方体グラフは超立方体グラフの半正方形です。^[19]

葉冪は木の葉によって誘導される木の冪のサブグラフである。k $葉冪は指数が$ $k$ である葉冪である。^[20]

参考文献

^ ボンディ、エイドリアン、マーティ、USR (2008)、グラフ理論、Graduate Texts in Mathematics、vol. 244、Springer、p. 82、ISBN 9781846289699。
^ Weisstein, Eric W.、「グラフパワー」、MathWorld
^ Todinca, Ioan (2003)、「境界付きクリーク幅のグラフの色付け能」、コンピュータサイエンスにおけるグラフ理論的概念、Lecture Notes in Comput. Sci.、vol. 2880、Springer、ベルリン、pp. 370–382、doi :10.1007/978-3-540-39890-5_32、MR 2080095。
^ ab Agnarsson, Geir; Halldórsson, Magnús M. (2000)、「平面グラフの彩色能力」、第 11 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA '00) の議事録、米国カリフォルニア州サンフランシスコ、pp. 654–662{{citation}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)。
^ Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E. ; Woeginger, G. (1993)、「高解像度での平面グラフの描画」、SIAM Journal on Computing、22 (5): 1035–1052、doi :10.1137/0222063、MR 1237161。
^ クレイマー、フロリカ、クレイマー、ホルスト (2008)、「グラフの距離彩色に関する調査」、離散数学、308 (2–3): 422–426、doi : 10.1016/j.disc.2006.11.059、MR 2378044。
^ モロイ、マイケル; サラバティプール、モハマド R. (2005)、「平面グラフの平方の彩色数の上限」、Journal of Combinatorial Theory、シリーズ B、94 (2): 189–213、doi :10.1016/j.jctb.2004.12.005、hdl : 1807/9473、MR 2145512。
^ Alon, Noga ; Mohar, Bojan (2002)、「グラフのべき乗の彩色数」、組合せ論、確率および計算、11 (1): 1–10、doi :10.1017/S0963548301004965、MR 1888178、S2CID 2706926。
^ Agnarsson & Halldórsson (2000) は、McCormick (1983) と Lin と Skiena (1995) による一般グラフの NP 困難性、および Ramanathan と Lloyd (1992、1993) による平面グラフの NP 困難性を証明した出版物をリストしています。
^ ボンディ＆マーティ（2008）、105ページ。
^ アンダーグラウンド、ポリー（1978）、「ハミルトン平方グラフについて」、離散数学、21（3）：323、doi：10.1016/0012-365X（78）90164-4、MR 0522906。
^ Diestel, Reinhard (2012)、「10. ハミルトンサイクル」、グラフ理論(PDF) (訂正第 4 版電子版)。
^ Chan, Timothy M. (2012)、「時間内の重みなし無向グラフの全ペア最短経路」、ACM Transactions on Algorithms、8 (4): A34:1–A34:17、doi :10.1145/2344422.2344424、MR 2981912、S2CID 1212001 $o(mn)$
^ ハマック、リチャード、イムリッチ、ウィルフリード、クラヴジャー、サンディ（2011）、積グラフハンドブック、離散数学とその応用（第2版）、CRCプレス、p.94、ISBN 9781439813058。
^ Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I (2015)、「ツリールート問題に対する線形時間アルゴリズム」、Algorithmica、71 (2): 471–495、doi :10.1007/s00453-013-9815-y、S2CID 253971732。
^ モトワニ、R.; スーダン、M. (1994)、「グラフの根を計算するのは難しい」、離散応用数学、54：81–88、doi：10.1016/0166-218x(94)00023-9。
^ Le, Van Bang; Nguyen, Ngoc Tuy (2010)、「グラフべき乗の困難性結果と効率的なアルゴリズム」、Graph-Theoretic Concepts in Computer Science: 35th International Workshop、WG 2009、モンペリエ、フランス、2009 年 6 月 24 ～ 26 日、改訂版論文、Lecture Notes in Computer Science、vol. 5911、ベルリン: Springer、pp. 238 ～ 249、doi :10.1007/978-3-642-11409-0_21、ISBN 978-3-642-11408-3、MR 2587715。
^ 陳志中;グリニ、ミケランジェロ。Papadimitriou、Christos H. (2002)、「マップグラフ」、Journal of the ACM、49 (2): 127–138、arXiv : cs/9910013、doi :10.1145/506147.506148、MR 2147819、S2CID 2657838。
^ Shpectorov, SV (1993)、「グラフのハイパーキューブへのスケール埋め込みについて」、European Journal of Combinatorics、14 (2): 117–130、doi : 10.1006/eujc.1993.1016、MR 1206617。
^ 西村, N.; Ragde, P.; Thilikos, DM (2002)、「葉ラベル付き木のグラフべき乗について」、Journal of Algorithms、42 : 69–108、doi :10.1006/jagm.2001.1195。

[1] ボンディ、エイドリアン、マーティ、USR (2008)、グラフ理論、Graduate Texts in Mathematics、vol. 244、Springer、p. 82、ISBN 9781846289699。

[2] Weisstein, Eric W.、「グラフパワー」、MathWorld

[3] Todinca, Ioan (2003)、「境界付きクリーク幅のグラフの色付け能」、コンピュータサイエンスにおけるグラフ理論的概念、Lecture Notes in Comput. Sci.、vol. 2880、Springer、ベルリン、pp. 370–382、doi :10.1007/978-3-540-39890-5_32、MR 2080095。

[ah00-4] Agnarsson, Geir; Halldórsson, Magnús M. (2000)、「平面グラフの彩色能力」、第 11 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA '00) の議事録、米国カリフォルニア州サンフランシスコ、pp. 654–662{{citation}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)。

[5] Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E. ; Woeginger, G. (1993)、「高解像度での平面グラフの描画」、SIAM Journal on Computing、22 (5): 1035–1052、doi :10.1137/0222063、MR 1237161。

[6] クレイマー、フロリカ、クレイマー、ホルスト (2008)、「グラフの距離彩色に関する調査」、離散数学、308 (2–3): 422–426、doi : 10.1016/j.disc.2006.11.059、MR 2378044。

[7] モロイ、マイケル; サラバティプール、モハマド R. (2005)、「平面グラフの平方の彩色数の上限」、Journal of Combinatorial Theory、シリーズ B、94 (2): 189–213、doi :10.1016/j.jctb.2004.12.005、hdl : 1807/9473、MR 2145512。

[8] Alon, Noga ; Mohar, Bojan (2002)、「グラフのべき乗の彩色数」、組合せ論、確率および計算、11 (1): 1–10、doi :10.1017/S0963548301004965、MR 1888178、S2CID 2706926。

[9] Agnarsson & Halldórsson (2000) は、McCormick (1983) と Lin と Skiena (1995) による一般グラフの NP 困難性、および Ramanathan と Lloyd (1992、1993) による平面グラフの NP 困難性を証明した出版物をリストしています。

[10] ボンディ＆マーティ（2008）、105ページ。

[11] アンダーグラウンド、ポリー（1978）、「ハミルトン平方グラフについて」、離散数学、21（3）：323、doi：10.1016/0012-365X（78）90164-4、MR 0522906。

[12] Diestel, Reinhard (2012)、「10. ハミルトンサイクル」、グラフ理論(PDF) (訂正第 4 版電子版)。

[13] Chan, Timothy M. (2012)、「時間内の重みなし無向グラフの全ペア最短経路」、ACM Transactions on Algorithms、8 (4): A34:1–A34:17、doi :10.1145/2344422.2344424、MR 2981912、S2CID 1212001 $o(mn)$

[14] ハマック、リチャード、イムリッチ、ウィルフリード、クラヴジャー、サンディ（2011）、積グラフハンドブック、離散数学とその応用（第2版）、CRCプレス、p.94、ISBN 9781439813058。

[15] Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I (2015)、「ツリールート問題に対する線形時間アルゴリズム」、Algorithmica、71 (2): 471–495、doi :10.1007/s00453-013-9815-y、S2CID 253971732。

[16] モトワニ、R.; スーダン、M. (1994)、「グラフの根を計算するのは難しい」、離散応用数学、54：81–88、doi：10.1016/0166-218x(94)00023-9。

[17] Le, Van Bang; Nguyen, Ngoc Tuy (2010)、「グラフべき乗の困難性結果と効率的なアルゴリズム」、Graph-Theoretic Concepts in Computer Science: 35th International Workshop、WG 2009、モンペリエ、フランス、2009 年 6 月 24 ～ 26 日、改訂版論文、Lecture Notes in Computer Science、vol. 5911、ベルリン: Springer、pp. 238 ～ 249、doi :10.1007/978-3-642-11409-0_21、ISBN 978-3-642-11408-3、MR 2587715。

[18] 陳志中;グリニ、ミケランジェロ。Papadimitriou、Christos H. (2002)、「マップグラフ」、Journal of the ACM、49 (2): 127–138、arXiv : cs/9910013、doi :10.1145/506147.506148、MR 2147819、S2CID 2657838。

[19] Shpectorov, SV (1993)、「グラフのハイパーキューブへのスケール埋め込みについて」、European Journal of Combinatorics、14 (2): 117–130、doi : 10.1006/eujc.1993.1016、MR 1206617。

[20] 西村, N.; Ragde, P.; Thilikos, DM (2002)、「葉ラベル付き木のグラフべき乗について」、Journal of Algorithms、42 : 69–108、doi :10.1006/jagm.2001.1195。