그래프에서 부분 그래프 찾기

Question

여기 그래프가 있습니다. 노드 B_0, B_1이 B 유형의 노드 C_0, C_1에 속하는 노드에만. C_2, C_3은 C 유형의 노드에 속합니다.

기준 - - 지금, 나는이 예제에 의해 정의 된 같은 기준을 satify 수있는 다수의 서브 그래프를 찾으려면

서브 그래프는 A 형 1 개 노드 B 형 1 개 노드 유형의 한 노드를 포함

1. C 유형 D의 한 노드
2. 서브 그래프는 유형 A의 노드에서 유형 B의 한 노드까지 하나의 에지를 가지며, 하나의 에지 연결 유형 B 및 유형 C와 하나의 노드 연결 유형 C 및 유형 D를가집니다.
3. 하위 그래프 유형 A의 한 모서리가 부 그래프에서 유형 B 노드로 가고 한쪽 모서리가 유형 B에서 유형 C 노드로 이동합니다. D 형에서 E 형 외부로 한쪽 가장자리.

지금이 설명은 결과를 제공한다 등 -

1. 서브 그래프 :: A_0, B_0, C_1, d_1의 파라미터
2. 서브 그래프 :: A_0, B_0, C_0, D_0
3. 서브 그래프 :: A_0 , B_1, C_2, d_2라는
4. 서브 그래프 :: A_0, B_1, C_3, D_3
내가 알고 싶은

, 어떤 알고리즘이있는 경우, B y와 같은 하위 그래프를 찾을 수 있습니까? 가능한 조합을 모두 만들어 알고리즘을 파악하려고했습니다. 그러나 이것은 서브 그래프의 노드 수에 지수 적입니다. 따라서 나는 그것을 계산할 효율적인 방법이 있는지 알고 싶다. 아니면 그래프 이론에서 비슷한 성격의 문제가 존재한다면?

Answer 1

당신은 거기에서 등등 모든 종류 C의 노드와 모양 타입 B의 수 있습니다에 연결된 모든 노드를 보면, 각 노드에 대한 A 형의 모든 노드를 방문하여 시작할 수 있습니다

, 마지막 A 노드에서 방문한 노드를 추적합니다. 그런 다음 검색 조건을 완료하는 하위 노드에 도달 할 때마다 A 노드의 모든 노드 목록을 현재 위치까지 추가합니다. 본질적으로 깊이 우선 검색을 수행하는 곳에서 노드가 어떤 노드가 더 이상 유효하지 않은지 (즉 유효한 서브 그래프를 생성 할 때마다) 뒤따라야하는 기준을 노드가 만족하는 한 그래프로 계속 탐색합니다. 현재 노드.