쉬운지 여부를 결정하는 방법은 주어진 그래프 를 본다면 다른 그래프?

Question

내가 찾는 알고리즘 여부를 확인하는 특정 그래프 를 본다면의 또 다른 주어진 그래프입니다.

나는 몇 가지 조건이 NP 완전한 문제를 조금 더 실현 가능한..

• 그래프는 약 <20 꼭지점입니다.
• 그래프는 DAG.
• 모든 꼭지점이 아닌 고유하게 표시하고 해당 정점에서 주요 그래프와 를 본다면 이해야 같은 레이블이 있습니다.내가 알지 못하는 경우 나를 사용하여 정확한 용어(기 때문에 나지 않았는지는 그래프 이론은 물론...).그것은 있어 쉽게 접근하실 수 있습니다.:

라인 그래프--B 를 본다면의 B--지만--A 를 본다면의 B--A.

어떤 제안도 괜찮습니다.이 숙제를 질문 btw.:D

Answer 1

If the labels are unique, for a graph of size N, there are O(N^2) edges, assuming there are no self loops or multiple edges between each pair of vertices. Let's use E for the number of edges.

If you hash the set edges in the parent graph, you can go through the subgraph's edges, checking if each one is in the hash table (and in the correct amount, if desired). You're doing this once for each edge, therefore, O(E).

Let's call the graph G (with N vertices) and the possible subgraph G_1 (with M vertices), and you want to find G_1 is in G.

Since the labels are not unique, you can, with Dynamic Programming, build the subproblems as such instead - instead of having O(2^N) subproblems, one for each subgraph, you have O(M 2^N) subproblems - one for each vertex in G_1 (with M vertices) with each of the possible subgraphs.

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

and the states are set up as such:

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

with the base case being index = M, and you can check for the edges equality, given the bitmask (and an implicit label-mapping). Alternatively, you can also do the checking within the if statement - just check that given current index, the current subgraph G_1[0..index] is equal to G[bitmask] (with the same implicit label mapping) before recursing.

For N = 20, this should be fast enough.

(add your memo, or you can rewrite this using bottoms up DP).

Answer 2

OK, I have to ask the obvious question. 1. You have twenty vertices. Walk each graph in depth first, alphabetical order among siblings to get strings. 2. One graph is a subgraph of another iff one string is in another.

So, what else is hiding in the problem specification to make this infeasible?

Answer 3

당신이 볼 수 있습니다 이것으로 정렬 문제입니다.기본적으로 당신이 원한을 가지고 올 injective mapping a 매핑하는 모든 꼭지점에서 V_1 을 꼭짓점에서 V_2.맞춤 맵 a 할 수 있습을 얻었는 다음과 같다:

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

어디\sigma(v w,(v)(w))=1,if(a(v)(w))\에 E_2 그렇지 않으면 그것은 0 입니다.

나는 생각이 될 수 있는 공식화의 형태로 정수 선형 프로그램입니다.