Ví dụ: hai biểu đồ này được coi là khớp một phần hoàn hảo:

0-1

1-2

hai mươi ba

3-0

Và

0-1

1-2

Cả hai được coi là không phù hợp

0-1

1-2

hai mươi ba

3-0

Và

0-1

1-2

2-0

Các con số không nhất thiết phải trùng khớp, miễn là mối quan hệ giữa các nút này khớp hoàn hảo.

câu trả lời hay nhất

Đây là vấn đề đẳng cấu đồ thị con:http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

Một thuật toán được đề cập trong bài viết nhờ Ullmann.

Thuật toán Ullman là sự mở rộng của tìm kiếm theo chiều sâu. Tìm kiếm theo chiều sâu sẽ hoạt động như thế này:

tìm kiếm def (đồ thị, đồ thị con, bài tập):
  i=len(bài tập)

  # Đảm bảo rằng mọi cạnh giữa các đỉnh được gán trong đồ thị con cũng là một
  # cạnh trong biểu đồ.
  cho cạnh trong subgraph.edges:
    nếu edge.first<>
      nếu không phải là graph.has_edge(bài tập [edge.first], bài tập [edge.second]):
        trả về Sai

  # Nếu tất cả các đỉnh trong đồ thị con đều được chỉ định thì chúng ta đã hoàn thành.
  nếu i==subgraph.n_vertices:
    trả về Đúng

  # Ngược lại, duyệt qua tất cả các phép gán có thể có cho đỉnh tiếp theo của
  # đồ thị con và thử nó.
  cho j trong khả năng_phân công [i]:
    nếu j không có trong bài tập:
      bài tập.append(j)
      nếu tìm kiếm (đồ thị, đồ thị con, bài tập):
        # Cách này hiệu quả nên chúng tôi đã tìm thấy một đẳng cấu.
        trả về Đúng
      bài tập.pop()

def find_isomorphism(đồ thị,đồ thị con):
  bài tập=[]
  nếu tìm kiếm (đồ thị, đồ thị con, bài tập):
    trả bài tập
  trả về Không có

Đối với thuật toán cơ bản,có thể_phân công [i] = phạm vi (0,graph.n_vertices). Tức là mọi đỉnh đều có thể.

Ullmann đã mở rộng thuật toán cơ bản này bằng cách thu hẹp các khả năng:

def update_possible_signments(biểu đồ,đồ thị con,có thể_phân công):
  Any_changes=Đúng
  trong khi Any_changes:
    Any_changes = Sai
    cho i trong phạm vi (0, len(subgraph.n_vertices)):
      cho j trong khả năng_phân công [i]:
        cho x trong sơ đồ con.adjacency(i):
          trận đấu=Sai
          cho y trong phạm vi(0,len(graph.n_vertices)):
            nếu y trong might_signments[x] và graph.has_edge(j,y):
              trận đấu=Đúng
          nếu không khớp:
            có thể_phân công[i].remove(j)
            Any_changes = Đúng

Ý tưởng là nếu nút i của đồ thị con có khả năng khớp với nút j của đồ thị thì với mọi nút x liền kề với nút i trong đồ thị con, thì phải tìm được nút y liền kề với nút j trong đồ thị. Quá trình này có thể giúp ích nhiều hơn những gì rõ ràng ban đầu, bởi vì mỗi khi chúng tôi loại bỏ một phân bổ có thể, điều này có thể khiến các phân bổ có thể khác cũng bị loại bỏ vì chúng phụ thuộc lẫn nhau.

Khi đó thuật toán cuối cùng là:

tìm kiếm def (biểu đồ, sơ đồ con, bài tập, bài tập có thể):
  update_possible_signments(biểu đồ,đồ thị con,có thể_phân công)

  i=len(bài tập)

  # Đảm bảo rằng mọi cạnh giữa các đỉnh được gán trong đồ thị con cũng là một
  # cạnh trong biểu đồ.
  cho cạnh trong subgraph.edges:
    nếu edge.first<>
      nếu không phải là graph.has_edge(bài tập [edge.first], bài tập [edge.second]):
        trả về Sai

  # Nếu tất cả các đỉnh trong đồ thị con đều được chỉ định thì chúng ta đã hoàn thành.
  nếu i==subgraph.n_vertices:
    trả về Đúng

  cho j trong khả năng_phân công [i]:
    nếu j không có trong bài tập:
      bài tập.append(j)

      # Tạo một tập hợp các phép gán mới, trong đó nút đồ thị j là nút duy nhất 
      # khả năng gán nút đồ thị con i.
      new_possible_signments = deep_copy(có thể_phân công)
      new_possible_signments[i] = [j]

      nếu tìm kiếm (biểu đồ, sơ đồ con, bài tập, new_possible_taskments):
        trả về Đúng

      bài tập.pop()
    có thể_phân công[i].remove(j)
    update_possible_signments(biểu đồ,đồ thị con,có thể_phân công)

def find_isomorphism(đồ thị,đồ thị con):
  bài tập=[]
  có thể_phân công = [[True]*graph.n_vertices cho i trong phạm vi(subgraph.n_vertices)]
  nếu tìm kiếm (biểu đồ, sơ đồ con, bài tập, bài tập có thể):
    trả bài tập
  trả về Không có

Về thuật toán - cách so sánh một phần hai biểu đồ, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/13537716/