Cách dễ dàng để xác định xem biểu đồ có phải là biểu đồ con của một số biểu đồ khác không?

Question

Tôi đang tìm một thuật toán để kiểm tra xem một biểu đồ đã cho có là đồ thị con của một đồ thị khác không.

Tôi có vài điều kiện để thực hiện NP hoàn chỉnh chút vấn đề này khả thi hơn ..

• Các đồ thị có khoảng < 20 đỉnh.
• Đồ thị là DAG.
• Tất cả các đỉnh không được gắn nhãn duy nhất và các đỉnh tương ứng trong biểu đồ chính và biểu đồ con phải có cùng nhãn. Tôi không biết nếu tôi đang sử dụng các thuật ngữ chính xác (bởi vì tôi đã không tham gia một khóa học lý thuyết đồ thị ...). Nó sẽ giống như sau:

Biểu đồ đường A - B là đồ thị con của A - B - A nhưng A - A không phải là đồ thị con của A - B - A.

Mọi đề xuất đều ổn. Đây không phải là một câu hỏi bài tập về nhà btw. : D

Answer 1

Nếu nhãn là duy nhất, đối với biểu đồ có kích thước N, có O(N^2) cạnh, giả sử không có vòng lặp tự hoặc nhiều cạnh giữa mỗi cặp đỉnh. Hãy sử dụng E cho số cạnh.

Nếu bạn băm các cạnh được đặt trong biểu đồ gốc, bạn có thể đi qua các cạnh của biểu đồ con, kiểm tra xem mỗi cái có nằm trong bảng băm (và với số tiền chính xác, nếu muốn). Bạn đang làm điều này một lần cho mỗi cạnh, do đó, O(E).

Hãy gọi đồ thị G (với N đỉnh) và đồ thị con có thể G_1 (với M đỉnh), và bạn muốn tìm G_1 is in G.

Kể từ khi nhãn là không duy nhất, bạn có thể, với lập trình năng động, xây dựng bài toán như vậy thay vì - thay vì phải O(2^N) bài toán, một cho mỗi đồ thị con, bạn có O(M 2^N) bài toán - một cho mỗi đỉnh trong G_1 (với M đỉnh) với mỗi biểu đồ con có thể.

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

và các quốc gia được thiết lập như vậy:

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 

với trường hợp cơ sở là index = M, và bạn có thể kiểm tra sự bình đẳng cạnh, do bitmask (và một label- ngầm ánh xạ). Ngoài ra, bạn cũng có thể thực hiện việc kiểm tra trong câu lệnh if - chỉ cần kiểm tra xem hiện tại index, biểu đồ con hiện tại G_1[0..index] bằng G[bitmask] (với ánh xạ nhãn tương tự) trước khi đệ quy.

Đối với N = 20, điều này sẽ đủ nhanh.

(thêm bản ghi nhớ của bạn hoặc bạn có thể viết lại bản ghi này bằng cách sử dụng phần dưới cùng lên DP).

Answer 2

OK, tôi phải đặt câu hỏi rõ ràng. 1. Bạn có hai mươi đỉnh. Đi theo từng đồ thị theo chiều sâu trước tiên, thứ tự bảng chữ cái trong số anh chị em để lấy chuỗi. 2. Một biểu đồ là một biểu đồ con của một chuỗi iff khác là một chuỗi khác.

Vì vậy, những gì khác đang ẩn trong đặc tả vấn đề để làm cho điều này không khả thi?

Answer 3

Bạn có thể xem vấn đề này dưới dạng sự cố căn chỉnh. Về cơ bản bạn muốn đưa ra ánh xạ tiêm a ánh xạ mọi đỉnh trong V_1 đến đỉnh trong V_2. Bản đồ căn chỉnh a có thể được ghi như sau:

s (a) = \ sum _ {(v, w) \ trong E_1} \ sigma (v, w, a (v), a (w)) ,

nơi \ sigma (v, w, a (v), a (w)) = 1, nếu (a (v), a (w)) \ in E_2 nếu không nó là 0.

Tôi nghĩ rằng điều này có thể được xây dựng dưới dạng một chương trình tuyến tính số nguyên.