하위 그래프 동형성과 하위 그래프 단일형성의 차이점은 무엇입니까?

Question

제가 작업한 프로젝트 중 하나에서 주제는 다음과 같습니다. 동형 대 단일형이 등장했습니다..

약간의 배경지식:나는 그래프 이론의 전문가도 아니고 정식 교육을 받은 적도 없습니다.그러나 이 주제는 화학자들이 사용하는 구조 검색 시스템에서 특정 종류의 하위 그래프 일치가 발생할 것으로 기대하는 화학에서 매우 중요합니다.

대상 그래프 A에 n개의 노드와 m개의 모서리가 있는 경우 화학자는 쿼리 그래프 B에 n개의 노드와 m-1개의 모서리가 있는 하위 그래프 일치를 허용합니다.유일한 요구 사항은 B의 모든 간선이 A에 존재해야 한다는 것입니다.예를 들어, 6개 노드의 선형 체인은 6개 노드의 주기와 일치해야 합니다.

이런 종류의 일치는 동형인가, 단일형인가?어쩌면 완전히 다른 것일 수도 있습니까?

Answer 1

G1, G2를 각각 정점 세트와 가장자리 v1, v2 및 e1, E2로 구성된 그래프로 두십시오.

G2는 v2의 각 정점과 V1의 각 정점과 E2의 각 모서리 사이에 일대일 매핑과 E1의 일부 에지 사이에 일대일 매핑이 존재한다. 따라서 이소성이 되려면 그래프에 노드간에 둘 이상의 에지가 포함 된 경우를 포함하여 정확히 일치해야합니다.

G2입니다 단형 IFF 정점 사이에 그러한 매핑이 있고 V2의 모든 정점 사이에 가장자리가 존재하는 V1에 해당 가장자리가 있습니다. 그러나 적어도 하나의 가장자리가 존재하는 한 충분합니다.

다음은 멋진 패키지 설명이 있습니다 comp.lang.python.

Answer 2

단일성.

하나의 그래프 ( "b")에서 다른 그래프 ( "a")까지의 단일성은 b에서 s 하위 그래프로의 동형과 동일합니다.

그 예는 n vertex 경로 ( "체인")가 n vertex 사이클에 대한 단량성이라고 말하는 것입니다. 또한 N+1 정점주기에 단순성이거나 K에 대해 N+K입니다.

Answer 3

정점에서의 H가 주사 기능 일 때 방향이없는 그래프 동성애 H : H-> G는 단일성이라고합니다. 그래프로서 동종 동질성 H는 물론 가장자리를 가장자리에 맵핑하지만 가장자리 H (v0) -h (v1)가 H에 반영 될 필요는 없습니다.

지시 된 그래프의 경우는 비슷합니다.

Answer 4

여기서는 Math와 CS 용어 사이에 불일치가 있습니다.수학에서 두 가지 용어를 얻습니다.

1. 하위 그래프 동형성:H = (VH, EH) 및 G = (V, E)를 그래프로 둡니다.에프 :VH → V는 (u, v) ∈ EH인 경우 하위 그래프 동형이고, 그러면 (f(u), f(v)) ∈ E입니다.H는 G의 하위 그래프와 동형입니다.

2. 유도된 하위 그래프 동형성:H = (VH, EH) 및 G = (V, E)를 그래프로 둡니다.에프 :VH → V는 (u, v) ∈ EH이면 유도된 하위 그래프 동형이고, 그러면 (f(u), f(v)) ∈ E입니다.그리고 (u, v)가 EH의 요소가 아니면 (f(u), f(v))는 E의 요소가 아닙니다.H는 G의 유도된 부분 그래프와 동형이다

정의 http://theory.stanford.edu/~virgi/cs267/lecture1.pdf.이는 제가 "그래프 이론의 첫 번째 과정"에서 찾은 내용과 동일합니다.

이들 둘 다 그래프 단형성이라고도 불리는 그래프 사이의 주입적 동형입니다.

CS, 특히 하위 그래프 동형 문제로 이동합니다.내가 이해하는 한, 하위 그래프 동형 알고리즘은 위의 (2)를 만족하는 함수가 존재하는지 결정합니다.

그래프 단형성 일치(1).

CS 정의는 VF2 알고리즘에서 나온 것인데, 그 사용법이 얼마나 널리 퍼져 있는지는 모르겠습니다.프로젝트에 대한 올바른 알고리즘을 검색하는 동안 여전히 모호성이 있고 모든 프로젝트가 동일한 정의를 사용하는 것은 아닙니다.

이 대답을 소금 한 알씩 받아들이십시오 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf소개에서 단일형을 그래프-하위 그래프 동형과 별도로 나열했지만 섹션 2에서는 그래프-하위 그래프 동형을 개념적으로 (1)과 동일하다고 정의하여 뭔가 빠졌음을 나타냅니다.