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

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(G₁, G₂)

Đầu vào: hai đồ thị G₁ và G₂.

Câu hỏi: G₁ có đẳng cấu với một đồ thị con của G₂ hay không?

Đồ thị (G1) và (G2) đẳng cấu nhau.

1. γ(1)=a, γ(2)=b, γ(3)=c, γ(4)=d
2. μ(u1)=e1, μ(u2)=e2, μ(u3)=e6, μ(u4)=e5, μ(u5)=e4, μ(u6)=e3.

• Hai đồ thị vô hướng G1 và G2 đẳng cấu nhau

• Hai đồ thị có hướng G3 và G4 không đẳng cấu nhau