部分的に二つのグラフ例えば

Question

を比較する方法は、これらの2つのグラフは、完全、部分一致であると考えられています - 0

と

0から1

1 - 2

これら二つが悪い一致

0であると考えられる - 1

1 - 2

2から3

、3 - 0

AND

、0 - 1

1 - 2

、2 - 0

番号があれば、それらのノード間の関係が完全に一致することができるように、一致する必要はありません。

Answer 1

これは部分グラフ同型問題である：ウルマンによる資料に記載つのアルゴリズムがありhttp://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

。

ウルマンのアルゴリズムは、深さ優先探索の拡張です。基本的なアルゴリズムについては

def search(graph,subgraph,assignments): 
    i=len(assignments) 

    # Make sure that every edge between assigned vertices in the subgraph is also an 
    # edge in the graph. 
    for edge in subgraph.edges: 
    if edge.first<i and edge.second<i: 
     if not graph.has_edge(assignments[edge.first],assignments[edge.second]): 
     return False 

    # If all the vertices in the subgraph are assigned, then we are done. 
    if i==subgraph.n_vertices: 
    return True 

    # Otherwise, go through all the possible assignments for the next vertex of 
    # the subgraph and try it. 
    for j in possible_assignments[i]: 
    if j not in assignments: 
     assignments.append(j) 
     if search(graph,subgraph,assignments): 
     # This worked, so we've found an isomorphism. 
     return True 
     assignments.pop() 

def find_isomporhism(graph,subgraph): 
    assignments=[] 
    if search(graph,subgraph,assignments): 
    return assignments 
    return None 

、possible_assignments[i] = range(0,graph.n_vertices)：深さ優先探索は次のように動作します。つまり、すべての頂点が可能です。

ウルマンの可能性を狭めることにより、この基本アルゴリズムを拡張：

def update_possible_assignements(graph,subgraph,possible_assignments): 
    any_changes=True 
    while any_changes: 
    any_changes = False 
    for i in range(0,len(subgraph.n_vertices)): 
     for j in possible_assignments[i]: 
     for x in subgraph.adjacencies(i): 
      match=False 
      for y in range(0,len(graph.n_vertices)): 
      if y in possible_assignments[x] and graph.has_edge(j,y): 
       match=True 
      if not match: 
      possible_assignments[i].remove(j) 
      any_changes = True 

アイデアがあれば、ノードは、サブグラフの私はおそらくノードに隣接する全てのノードxについて、次に、グラフのノードjと一致することができることですサブグラフでは、グラフ内のノードjに隣接するノードyを見つけることが可能でなければならない。このプロセスは、可能性のある割り当てを排除するたびに相互依存するため、他の可能な割り当てが排除される可能性があるため、最初に明らかになる可能性があります。

最終的アルゴリズムは次のとおりです。

def search(graph,subgraph,assignments,possible_assignments): 
    update_possible_assignments(graph,subgraph,possible_assignments) 

    i=len(assignments) 

    # Make sure that every edge between assigned vertices in the subgraph is also an 
    # edge in the graph. 
    for edge in subgraph.edges: 
    if edge.first<i and edge.second<i: 
     if not graph.has_edge(assignments[edge.first],assignments[edge.second]): 
     return False 

    # If all the vertices in the subgraph are assigned, then we are done. 
    if i==subgraph.n_vertices: 
    return True 

    for j in possible_assignments[i]: 
    if j not in assignments: 
     assignments.append(j) 

     # Create a new set of possible assignments, where graph node j is the only 
     # possibility for the assignment of subgraph node i. 
     new_possible_assignments = deep_copy(possible_assignments) 
     new_possible_assignments[i] = [j] 

     if search(graph,subgraph,assignments,new_possible_assignments): 
     return True 

     assignments.pop() 
    possible_assignments[i].remove(j) 
    update_possible_assignments(graph,subgraph,possible_assignments) 

def find_isomporhism(graph,subgraph): 
    assignments=[] 
    possible_assignments = [[True]*graph.n_vertices for i in range(subgraph.n_vertices)] 
    if search(graph,subgraph,asignments,possible_assignments): 
    return assignments 
    return None