그래프의 강력한 산물
Strong product of graphs
그래프 이론에서 그래프 G와 H의 강제품 G ⊠ H는 다음과[1] 같은 그래프다.
- G ⊠ H의 꼭지점 세트는 데카르트 제품 V(G) × V(H)이다.
- 고유 정점(u,u' ) 및 (v,v' )은 다음과 같은 경우에만 G ⊠ H에 인접한다.
- u = v 및 u'는 v' 또는
- u' = v' 및 u는 v에 인접하거나
- u는 v에 인접하고 u'는 v' 에 인접해 있다.
강제품은 정상제품 또는 AND제품이라고도 한다.[citation needed]1960년 사비두시에 의해 처음 도입되었다.[2]그런 설정에서 강한 제품은 약한 제품과 대비되지만, 무한히 많은 요인에 적용해야만 두 제품이 다르다.
예를 들어, 체스판의 정사각형이 정사각형이고 가장자리가 체스왕의 가능한 움직임을 나타내는 그래프인 킹의 그래프는 두 개의 경로 그래프의 강력한 산물이다.[3]
문헌에서 강한 제품이라는 용어를 접했을 때 주의를 기울여야 하는데, 이는 또한 그래프의 텐서적인 제품을 나타내는 데 사용되었기 때문이다.[4]
참고 항목
참조
- ^ Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Product, A. K. Peters, ISBN 978-1-56881-429-2.
- ^ Sabidussi, G. (1960). "Graph multiplication". Math. Z. 72: 446–457. doi:10.1007/BF01162967. hdl:10338.dmlcz/102459. MR 0209177.
- ^ Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130.
- ^ 의 2페이지를 참조하십시오.
