Bài toán đồ thị con đẳng cấu

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong lý thuyết độ phức tạp tính toán (Computational complexity theory), Đồ thị con đẳng cấu là một bài toán quyết định (decision problem) thuộc loại NP-đầy đủ (NP-complete). Phát biểu của bài toán quyết định như sau:

Đẳng cấu đồ thị con(G1, G2)
Đầu vào: hai đồ thị G1 và G2.
Câu hỏi: G1đẳng cấu với một đồ thị con của G2 hay không?

Đôi khi bài toán này còn nhấn mạnh vào việc tìm đồ thị con đẳng cấu, thay vì chỉ xác định xem có tồn tại đồ thị con đó hay không (như trường hợp bài toán quyết định cơ bản).

Đồ thị con đẳng cấu là suy rộng của một bài toán có thể dễ hơn: bài toán đồ thị đẳng cấu; nếu bài toán này thuộc loại NP-đầy đủ thì polynomial hierarchy (cây phả hệ đa thức???) sẽ sụp đổ. Vậy có lẽ không phải như vậy.

Tham khảo[sửa | sửa mã nguồn]