주어진 그래프가 다른 그래프의 서브 그래프인지 확인하는 쉬운 방법은 무엇입니까?

Question

주어진 그래프가 다른 주어진 그래프의 서브 그래프인지 확인하는 알고리즘을 찾고 있습니다.

나는

• 그래프는 약 < (20) 정점을 ..이 NP 완전 문제를 좀 더 가능하게하는 몇 가지 조건이있다.
• 그래프는 DAG입니다.
• 모든 꼭지점은 유일하게 레이블링되지 않으며 주 그래프와 하위 그래프의 해당 꼭지점은 동일한 레이블을 가져야합니다. 나는 정확한 용어를 사용하고 있는지 알지 못한다. 왜냐하면 나는 그래프 이론 과정을 택하지 않았기 때문이다.

선 그래프 A - B는 A - B - A의 하위 그래프이지만 A - A는 A - B - A의 하위 그래프가 아닙니다.

제안 사항은 문제가 없습니다. 이것은 숙제 문제가 아닙니다. : D

Answer 1

레이블이 고유 한 경우 크기가 N 인 그래프의 경우 자체 루프가 없거나 각 정점 쌍 사이에 여러 개의 가장자리가 있다고 가정하면 O(N^2) 가장자리가 있습니다. 모서리 수를 E으로합시다.

부모 그래프에서 설정된 가장자리를 해시하는 경우 하위 그래프의 가장자리를 통과하여 각각이 해시 테이블에 있는지 (원하는 경우 올바른 값으로) 확인할 수 있습니다. 각 가장자리에 대해이 작업을 한 번 수행하므로 O(E)입니다.

이의이 ( N 꼭지점) 그래프 G과 ( M 정점으로) 가능한 서브 그래프 G_1을 부르 자, 당신은 G_1 is in G을 찾고 싶어요. 레이블이 고유하지 때문에

, 당신은, 동적 프로그래밍과 같은 대신으로 하위 문제를 구축 할 수 있습니다 - 대신 O(2^N) 하위 문제, 각 서브 그래프 하나를 가지고, 당신은 O(M 2^N) 하위 문제가 - G_1의 각 정점 일 (M으로 정점)을 각각의 가능한 하위 그래프와 비교합니다. 기본 케이스 index = M 인과

isSubgraph(index, bitmask) = 
    for all vertex in G 
     if G[vertex] is not used (check bitmask) 
      and G[vertex]'s label is equal to G_1[index]'s label 
      and isSubgraph(index + 1, (add vertex to bitmask)) 
       return true 
    return false 

, 당신은 비트 마스크 (그리고 암시 적 레이블 - 주어진 가장자리 평등를 확인할 수 있습니다

G_1 is in G = isSubgraph(0, empty bitmask)

과 상태는 같은 설정됩니다 매핑). 또는 if 문 내에서 검사를 수행 할 수도 있습니다. 현재 index을 확인하고 현재 서브 그래프 G_1[0..index]은 G[bitmask] (동일한 암시 적 레이블 매핑과 동일 함)과 재귀하기 전에 비교합니다.

N = 20의 경우이 값은 충분히 빠릅니다.

(귀하의 메모를 추가하거나 DP를 사용하여 이것을 다시 작성할 수 있습니다).

Answer 2

그래, 나는 명백한 질문을해야만한다. 1. 20 개의 꼭지점이 있습니다. 문자열을 얻기 위해 형제 중 알파벳 순서로 각 그래프를 먼저 이동하십시오. 2. 하나의 그래프는 한 문자열이 다른 문자열에있는 경우 다른 벡터의 하위 그래프입니다.

그렇다면이 문제를 해결하기 위해 문제 사양에 무엇을 숨기고 있습니까?

Answer 3

정렬 문제로 볼 수 있습니다. 기본적으로 주사 바늘 매핑 을 사용하여 V_1의 모든 정점을 V_2의 정점에 매핑합니다. 정렬 맵 은 다음과 같이 점수를 매길 수 있습니다.

s (a) = \ sum_ {(v, w) \ in E_1} \ sigma (v, w, a (v), a (w) ,

여기서 \ 시그마 (V, W A (V)와,() w) (a는 (V)이고, a는 (w)) \에서 E_2, 그렇지 않으면 0

인 경우, = 1 이것은 선형 선형 프로그램의 형태로 공식화 될 수 있다고 생각합니다.