查看“︁图的次幂”︁的源代码

[[File:Square_of_a_graph.svg|缩略图|300x300像素|一个图的二次幂。]]
在数学的一个分支[[图论]]中，一个[[图 (数学)|无向图]]的'''''k''次幂''G''<sup>''k''</sup>'''指的是另一个有相同[[顶点 (图论)|顶点]]集的图，但在G中所有[[距离 (图论)|距离]]小于''k''的[[顶点 (图论)|顶点]]在该图中是相邻的。图的次幂常用数的[[冪|次幂]]相关术语来表示：''G''<sup>2</sup>被称为''G''的'''平方'''，''G''<sup>3</sup>被称为'''立方'''，以此类推。<ref>{{Citation|title=Graph Theory|volume=244|series=Graduate Texts in Mathematics|first=Adrian|last=Bondy|first2=U. S. R.|last2=Murty|publisher=Springer|year=2008|isbn=9781846289699|page=82|url=https://books.google.com/books?id=HuDFMwZOwcsC&pg=PA82}}</ref>

图的次幂应该与[[图的乘积|图本身的乘积]]区别开来，图的乘积（与次幂不同）通常比原图有更多的顶点。

== 属性 ==
如果一个图的[[距离 (图论)|直径]]是d，那么它的d次幂就是[[完全圖|完全图]]。<ref>{{cite mathworld|id=GraphPower|title=Graph Power}}</ref>如果一个图族具有有界的[[团宽]]，那么对于任意固定的d，它的d次幂也具有有界的团宽。<ref>{{Citation|last=Todinca|first=Ioan|contribution=Coloring powers of graphs of bounded clique-width|doi=10.1007/978-3-540-39890-5_32|mr=2080095|pages=370–382|publisher=Springer, Berlin|series=Lecture Notes in Comput. Sci.|title=Graph-theoretic concepts in computer science|volume=2880|year=2003}}.</ref>

=== 着色 ===
图平方的[[图着色问题|着色]]可以用来为无线通信网络的参与者分配频率，使两个参与者互动时不受任何共同邻居的干扰，并可以在[[图绘制]]时找到[[角分辨率 (图论）|角分辨率]]高的图。<ref name="ah00">{{Citation|last=Agnarsson|first=Geir|last2=Halldórsson|first2=Magnús M.|contribution=Coloring powers of planar graphs|place=San Francisco, California, USA|pages=654–662|title=Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00)|year=2000}}.</ref><ref>{{Citation|last=Formann|first=M.|last2=Hagerup|first2=T.|last3=Haralambides|first3=J.|last4=Kaufmann|first4=M.|last5=Leighton|first5=F. T.|author5-link=F. Thomson Leighton|last6=Symvonis|first6=A.|last7=Welzl|first7=E.|author7-link=Emo Welzl|last8=Woeginger|first8=G.|author8-link=Gerhard J. Woeginger|doi=10.1137/0222063|number=5|journal=[[SIAM Journal on Computing]]|mr=1237161|pages=1035–1052|title=Drawing graphs in the plane with high resolution|volume=22|year=1993}}.</ref>

最大度为&#x394;的[[平面图 (图论)|平面图]]的''k''次幂其[[图着色问题|着色数]]和[[简并(图论)|简并度]]均为<math>O(\Delta^{\lfloor k/2\rfloor})</math>，其中简并度表明[[贪婪的着色|颜色贪婪]]算法可利用这么多颜色给图着色。<ref name="ah00">{{Citation|last=Agnarsson|first=Geir|last2=Halldórsson|first2=Magnús M.|contribution=Coloring powers of planar graphs|place=San Francisco, California, USA|pages=654–662|title=Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00)|year=2000}}.</ref> 考虑一个平面图平方的特例，Wegner在1977年推算出平面图平方的最大着色数为<math>\max\left(\Delta+5, \frac{3\Delta}{2}+1\right)</math>而目前更普遍的最大着色数为<math>\frac{5\Delta}{3}+O(1)</math>。<ref>{{Citation|last=Kramer|first=Florica|last2=Kramer|first2=Horst|doi=10.1016/j.disc.2006.11.059|number=2-3|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|mr=2378044|pages=422–426|title=A survey on the distance-colouring of graphs|volume=308|year=2008}}.</ref><ref>{{Citation|last=Molloy|first=Michael|last2=Salavatipour|first2=Mohammad R.|doi=10.1016/j.jctb.2004.12.005|number=2|journal=[[Journal of Combinatorial Theory]]|series=Series B|mr=2145512|pages=189–213|title=A bound on the chromatic number of the square of a planar graph|volume=94|year=2005}}.</ref> 更一般地说，对任何简并度为''d''和最大度为&#x394;的图，图平方的简并度为''O''(''d''&#x394;)，因此许多不是平面图的[[疏图|稀疏图]]其平方的着色数与&#x394;成比例。

尽管最大度为Δ的非平面图平方的着色数最坏情况是与&#x394;<sup>2</sup>成比例，对于高[[圍長 (圖論)|围长]]的图来说其往往更小，通常在这种情况下量级为O(&#x394;<sup>2</sup>/log&nbsp;&#x394;)。<ref>{{Citation|last=Alon|first=Noga|author-link=Noga Alon|last2=Mohar|first2=Bojan|author2-link=Bojan Mohar|doi=10.1017/S0963548301004965|number=1|journal=[[Combinatorics, Probability and Computing]]|mr=1888178|pages=1–10|title=The chromatic number of graph powers|volume=11|year=2002}}.</ref>

确定为图平方着色需要的颜色数是[[NP困难]]，即使在平面图中也是如此。<ref>{{Harvard citation text|Agnarsson|Halldórsson|2000}} list publications proving NP-hardness for general graphs by McCormick (1983) and Lin and Skiena (1995), and for planar graphs by Ramanathan and Lloyd (1992, 1993).</ref>

=== 哈密顿性 ===
每个连通图的立方必然包含一个[[哈密顿图|哈密顿循环]]。<ref>{{Harvard citation text|Bondy|Murty|2008}}, p. 105.</ref>一个连通图的平方不一定满足哈密顿性，它是否满足哈密顿性是[[NP完全|NP完备]]的。<ref>{{Citation|last=Underground|first=Polly|author-link=Václav Chvátal|doi=10.1016/0012-365X(78)90164-4|number=3|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|mr=522906|page=323|title=On graphs with Hamiltonian squares|volume=21|year=1978}}.</ref>然而，根据[[弗莱施纳定理]]，[[K-顶点连通图|2-顶点连通图]]的平方总是满足哈密顿性的。<ref>{{Citation|last=Diestel|first=Reinhard|contribution=10. Hamiltonian cycles|edition=corrected 4th electronic|title=Graph Theory|url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch10.pdf|year=2012|accessdate=2019-06-26|archive-date=2012-06-17|archive-url=https://web.archive.org/web/20120617001024/http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch10.pdf|dead-url=yes}}.</ref>

== 计算复杂度 ==
一个有''n'' 个[[顶点 (图论)|顶点]]和''m''条边的图的''k''次幂可以通过从每个顶点开始执行[[广度优先搜索]]来确定到所有其他顶点的距离，从而在时间O(''mn'')中计算出来。如果''A''是一个图的[[邻接矩阵]]，修改主对角线的非零元素，那么''A<sup>k</sup>''的非零项给出了图的''k''次幂的邻接矩阵，由此可以在[[矩阵乘法]]时间的对数因子内构造出第k次幂的时间量。<ref>{{Citation|title=Handbook of Product Graphs|edition=2nd|series=Discrete Mathematics and Its Applications|first=Richard|last=Hammack|first2=Wilfried|last2=Imrich|first3=Sandi|last3=Klavžar|author3-link=Sandi Klavžar|publisher=CRC Press|year=2011|isbn=9781439813058|page=94|url=https://books.google.com/books?id=WiB6UO1nqHAC&pg=PA94}}.</ref>

树的''k''次幂可以在输入图的尺寸上用时间线性的方式识别。<ref>{{Citation|last=Chang|first=Maw-Shang|last2=Ko|first2=Ming-Tat|last3=Lu|first3=Hsueh-I|journal=[[Algorithmica]]|title=Linear-Time Algorithms for Tree Root Problems|pages=471-495|year=2015|volume=71|number=2|doi=10.1007/s00453-013-9815-y}}.</ref>

给定一个图，判断它是否是另一个图的平方是[[NP完全]]的。<ref>{{Citation|last=Motwani|first=R.|last2=Sudan|first2=M.|journal=[[Discrete Applied Mathematics]]|pages=81–88|title=Computing roots of graphs is hard|volume=54|year=1994|doi=10.1016/0166-218x(94)00023-9}}.</ref>此外，对于给定的数字k≥2，确定一个图是否是另一个图的k次幂，或是[[二分图]]的k次幂，是[[NP完全]]的。<ref>{{Citation|last=Le|first=Van Bang|last2=Nguyen|first2=Ngoc Tuy|contribution=Hardness results and efficient algorithms for graph powers|doi=10.1007/978-3-642-11409-0_21|place=Berlin|mr=2587715|pages=238–249|publisher=Springer|series=Lecture Notes in Computer Science|title=Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers|volume=5911|year=2010|isbn=978-3-642-11408-3}}.</ref>

== 导出子图 ==
[[File:Demi-3-cube.svg|缩略图|{{Math|''K''<sub>4</sub>}} 是一个[[超方形圖|超立方图]]的半二分结果。]]
[[二分图]]G的[[半二分]]是{{math|''G''<sup>2</sup>}} 的子图，其为将''{{mvar|G}}''平分为两部分的一部分。[[平面图 (图论)|平面图]]的半二分是[[地图图]]，[[超立方图]]的半二分是[[半立方图]]。<ref>{{Citation|last=Chen|first=Zhi-Zhong|last2=Grigni|first2=Michelangelo|last3=Papadimitriou|first3=Christos H.|author3-link=Christos Papadimitriou|doi=10.1145/506147.506148|number=2|journal=[[Journal of the ACM]]|mr=2147819|pages=127–138|title=Map graphs|volume=49|year=2002|arxiv=cs/9910013}}.</ref><ref>{{Citation|last=Shpectorov|first=S. V.|doi=10.1006/eujc.1993.1016|number=2|journal=[[European Journal of Combinatorics]]|mr=1206617|pages=117–130|title=On scale embeddings of graphs into hypercubes|volume=14|year=1993}}.</ref>

[[叶幂]]是由树的叶导出的树的次幂子图。''{{mvar|k}}''叶幂是指数为''{{mvar|k}}''的叶幂。<ref>{{Citation|last=Nishimura|first=N.|last2=Ragde|first2=P.|last3=Thilikos|first3=D.M.|journal=[[Journal of Algorithms]]|pages=69–108|title=On graph powers for leaf-labeled trees|volume=42|year=2002|doi=10.1006/jagm.2001.1195}}.</ref>

== 参考文献 ==
{{Reflist}}
[[Category:图论]]
[[Category:有未审阅翻译的页面]]