그래프 검정력

Graph power
그래프의 정사각형

수학의 한 분야인 그래프 이론에서, 무방향 그래프 G의 k제곱k G는 같은 정점 집합을 가지지만, G에서의 거리가 최대 k일 때 두 정점이 인접한 또 다른 그래프이다.그래프의 거듭제곱은 숫자의 거듭제곱과 유사한 용어를 사용하여 언급된다: G는2 G의 제곱, G는3 G의 세제곱 등.[1]

그래프 검정력은 ( 검정력과 달리) 일반적으로 원래 그래프보다 더 많은 정점을 갖는 그래프 자체의 곱과 구별되어야 한다.

특성.

그래프의 직경이 d인 경우 d번째 검정력은 완전한 [2]그래프입니다.그래프 패밀리에 clique-width가 한정되어 있는 경우 고정d의 [3]d제곱도 한정되어 있습니다.

색칠

그래프의 정사각형상의 그래프 색칠은 무선통신 네트워크의 참가자에게 주파수를 할당하여 두 참가자가 공통의 [4]어느 한쪽에서 서로 간섭하지 않도록 하고 높은 각도 [5]분해능의 그래프 도면을 찾기 위해 사용할 수 있다.

최대도 δ의 평면그래프의 k승의 색수 및 축퇴는 모두 O(δ⌊k/2⌋)이며, 축퇴한계는 그리디 컬러링 알고리즘을 사용하여 그래프를 이 많은 [4]색으로 색칠할 수 있음을 나타낸다.한 평면 그래프의 사각형의 특별한 경우 웽거 감독은 1977년에 있는 평면 그래프의 제곱의 색 수 대부분의 정도 들 것(Δ+5,.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{에 추측했다.디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac.num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{.국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}3Δ/2+1컵, 그리고 색 수에 대부분의 5Δ/3+O(1)하는 것으로 알려졌다.[6][7]보다 일반적으로 축퇴 d 및 최대도 δ의 그래프에 대해 그래프의 제곱 축퇴는 O(DΩ)이므로 평면 그래프 이외의 많은 종류의 희박한 그래프도 색수가 δ에 비례하는 제곱을 가진다.

최대도 δ인 비평면 그래프의 제곱의 색수는 최악의 경우 δ에2 비례할 수 있지만, 이 경우 [8]O(δ2 / log δ)에 의해 경계가 되는 높은 둘레의 그래프일수록 작다.

그래프의 정사각형을 색칠하는 데 필요한 최소 색상 수를 결정하는 것은 평면의 [9]경우에도 NP-hard입니다.

해밀턴성

연결된 모든 그래프의 입방체에는 반드시 해밀턴 [10]사이클이 포함됩니다.연결된 그래프의 제곱이 반드시 해밀턴인 것은 아니며, 제곱이 [11]해밀턴인지 아닌지를 결정하는 것은 NP-완전이다.그럼에도 불구하고, 플라이슈너의 정리에 따르면, 2-vertex 연결 그래프의 [12]제곱은 항상 해밀턴이다.

계산의 복잡성

n개의 정점과 m개의 모서리를 가진 그래프의 k제곱은 각 정점에서 시작하여 폭 우선 검색을 수행하여 시간 O(mn)로 계산하거나 보다 정교한 [13]알고리즘을 사용하여 약간 더 빠르게 계산할 수 있습니다.그래프, 그 활동의 중요한 그리고 대각선으로 조금이라도 항목이 있을에 수정을 위해 A는 인접 행렬 또는, 그때 Ak의 영이 아닌 항목의 그것은kth 힘을 건설하는 시간의 matr를 위한 시간의 로그 인자의 양으로 수행할 수 있다음과 같이 graph,[14]의kth 권력의 인접 행렬을 준다.mix궁극의 복제.

트리의 k제곱은 입력 그래프의 크기에서 시간 선형으로 인식할 수 있습니다.[15]

그래프를 지정하면 다른 그래프의 제곱인지 아닌지는 NP-완전입니다.[16] 또한, 그래프가 다른 그래프의 k제곱인지, 주어진 수 k 22인지, k>[17]2에 대해 초당 그래프의 k제곱인지를 판정하는 것은 NP-완전이다.

유도 서브그래프

입방체4 그래프의 반제곱 K

초당 그래프 G의 반제곱은 G의 양분 중 한 변에 의해 유도되는 G의 하위2 그래프이다. 맵 그래프는 평면 [18]그래프의 반제곱이고, 반제곱 입방체 그래프는 하이퍼 큐브 [19]그래프의 반제곱이다.

잎의 힘은 나무의 잎에 의해 유도되는 나무의 힘의 하위 그래프이다.k-잎 거듭제곱은 지수가 [20]k인 잎 거듭제곱입니다.

레퍼런스

  1. ^ 를 클릭합니다Bondy, Adrian; Murty, U. S. R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 82, ISBN 9781846289699.
  2. ^ Weisstein, Eric W. "Graph Power". MathWorld.
  3. ^ 를 클릭합니다Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., vol. 2880, Springer, Berlin, pp. 370–382, doi:10.1007/978-3-540-39890-5_32, MR 2080095.
  4. ^ a b 를 클릭합니다Agnarsson, Geir; Halldórsson, Magnús M. (2000), "Coloring powers of planar graphs", Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), San Francisco, California, USA, pp. 654–662.
  5. ^ 를 클릭합니다Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing, 22 (5): 1035–1052, doi:10.1137/0222063, MR 1237161.
  6. ^ 를 클릭합니다Kramer, Florica; Kramer, Horst (2008), "A survey on the distance-colouring of graphs", Discrete Mathematics, 308 (2–3): 422–426, doi:10.1016/j.disc.2006.11.059, MR 2378044.
  7. ^ 를 클릭합니다Molloy, Michael; Salavatipour, Mohammad R. (2005), "A bound on the chromatic number of the square of a planar graph", Journal of Combinatorial Theory, Series B, 94 (2): 189–213, doi:10.1016/j.jctb.2004.12.005, hdl:1807/9473, MR 2145512.
  8. ^ 를 클릭합니다Alon, Noga; Mohar, Bojan (2002), "The chromatic number of graph powers", Combinatorics, Probability and Computing, 11 (1): 1–10, doi:10.1017/S0963548301004965, MR 1888178.
  9. ^ Agnarsson & Haldörsson(2000)은 McCormick(1983)과 Lin과 Skiena(1995)의 일반 그래프와 Ramanathan과 Lloyd(1992, 1993)의 평면 그래프에 대해 NP-경도를 입증하는 출판물을 나열했다.
  10. ^ Bondy & Murty (2008), 페이지 105.
  11. ^ 를 클릭합니다Underground, Polly (1978), "On graphs with Hamiltonian squares", Discrete Mathematics, 21 (3): 323, doi:10.1016/0012-365X(78)90164-4, MR 0522906.
  12. ^ 를 클릭합니다Diestel, Reinhard (2012), "10. Hamiltonian cycles", Graph Theory (PDF) (corrected 4th electronic ed.).
  13. ^ Chan, Timothy M. (2012), "All-pairs shortest paths for unweighted undirected graphs in time", ACM Transactions on Algorithms, 8 (4): A34:1–A34:17, doi:10.1145/2344422.2344424, MR 2981912
  14. ^ 를 클릭합니다Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi (2011), Handbook of Product Graphs, Discrete Mathematics and Its Applications (2nd ed.), CRC Press, p. 94, ISBN 9781439813058.
  15. ^ 를 클릭합니다Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I (2015), "Linear-Time Algorithms for Tree Root Problems", Algorithmica, 71 (2): 471–495, doi:10.1007/s00453-013-9815-y.
  16. ^ 를 클릭합니다Motwani, R.; Sudan, M. (1994), "Computing roots of graphs is hard", Discrete Applied Mathematics, 54: 81–88, doi:10.1016/0166-218x(94)00023-9.
  17. ^ 르, 반 빅뱅, 응우옌, 녹뚜이의(2010년),"그래프 세력을 위한 경도 결과와 효율적인 알고리즘", Graph-Theoretic 개념 컴퓨터 과학으로:35년 국제 워크숍 WG 2009년 몽펠리에, 프랑스, 6월 2426인 2009년 수정된 논문, 강의 노트 컴퓨터 과학으로, 5911 vol., 베를린:스프링거,를 대신하여 서명함. 238–249, doi:10.1007/978-3-642-11409-0_21,.아이 에스비엔 978-3-642-11408-3, MR2587715.
  18. ^ 를 클릭합니다Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM, 49 (2): 127–138, arXiv:cs/9910013, doi:10.1145/506147.506148, MR 2147819.
  19. ^ 를 클릭합니다Shpectorov, S. V. (1993), "On scale embeddings of graphs into hypercubes", European Journal of Combinatorics, 14 (2): 117–130, doi:10.1006/eujc.1993.1016, MR 1206617.
  20. ^ 를 클릭합니다Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms, 42: 69–108, doi:10.1006/jagm.2001.1195.