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

Public on April 22, 2014
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 có đẳng cấu với một đồ thị con của G2 hay không?

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

Hình 1: Đẳng cấu đồ thị
  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
Hình 2: Đẳng cấu đồ thị 1
  • Hai đồ thị có hướng G3 và G4 không đẳng cấu nhau
Hình 3: Đồ thị không đẳng cấu





    [Advertising]Faster Thinking - Speed up your brain


    Faster Thinking Game
    avatar
    Thanh Nguyen person

    Đồ thị con đẳng cấu

    delete 4/23/14, 3:26 PM



    sentiment_satisfied Emoticon