그래프의 모듈형 제품

그래프의 모듈형 제품.

그래프 이론에서 그래프 G와 H의 모듈형 산출물은 이소모르퍼리즘을 측량하기 위한 응용이 있는 G와 H를 결합하여 형성된 그래프다.그것은 연구된 여러 가지 다른 종류의 그래프 제품들 중 하나이며, 일반적으로 동일한 꼭지점 세트(두 그래프 G와 H의 정점 집합의 데카르트 제품)를 사용하지만 어떤 가장자리를 포함시킬지 결정하는 데 다른 규칙을 가지고 있다.

정의

G와 H의 모듈형 제품의 꼭지점 세트는 데카르트 제품 V(G) × V(H)이다.어떤 두 꼭지점(u, v)과 (u' , v' )은 i가 u'와 구별되는 경우에만 G와 H의 모듈형 제품에 인접해 있으며, v는 v' 와 구별된다.

• u는 u'와 인접하고 v는 v' , 또는
• u는 u'와 인접하지 않고 v는 v' 와 인접하지 않다.

서브그래프 이소모르퍼시즘

모듈형 제품 그래프의 부류는 G와 H의 유도 하위 그래프의 이형성에 해당한다.따라서 모듈형 제품 그래프는 유도 서브그래프 이형성 문제를 그래프에서 패트릭을 찾는 문제로 줄이는 데 사용될 수 있다.특히 G와 H의 최대 공통 유도 하위그래프는 모듈형 제품에서 최대 집단에 해당한다.가장 큰 공통 유도 서브그래프를 찾는 문제와 최대 집단을 찾는 문제가 모두 NP-완전하지만, 이러한 감소는 공통 서브그래프 문제에 클라이크 탐색 알고리즘을 적용할 수 있게 한다.

참조

• Barrow, H.; Burstall, R. (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Information Processing Letters, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1.
• Levi, G. (1973), "A note on the derivation of maximal common subgraphs of two directed or undirected graphs", Calcolo, 9 (4): 341–352, doi:10.1007/BF02575586.
• Vizing, V. G. (1974), "Reduction of the problem of isomorphism and isomorphic entrance to the task of finding the nondensity of a graph", Proc. 3rd All-Union Conf. Problems of Theoretical Cybernetics, p. 124.