Phép đồng cấu đồ thị

Trong Lý thuyết đồ thị, phép đồng cấu đồ thị (tiếng Anh: graph homomorphism) là ánh xạ giữa hai đồ thị trong khi tôn trọng cấu trúc của chúng. Cụ thể hơn, nó ánh xạ các đỉnh kề nhau với các đỉnh kề nhau.

Định nghĩa
Một phép đồng cấu đồ thị  từ đồ thị  đến đồ thị , ký hiệu , là một ánh xạ
 từ tập các đỉnh của  đến tập các đỉnh của  sao cho  nếu .

Định nghĩa trên mở rộng được cho đồ thị có hướng. Khi đó, với phép đồng cấu ,  là một cung của  nếu  là một cung của .

Nếu tồn tại một phép đồng cấu , ta sẽ viết rằng . Nếu không có, ta viết . Nếu ,  được coi là đồng cấu với  hay -colourable (tô màu được thành H).

Hợp của các phép đồng cấu cũng là phép đồng cấu. Nếu phép đồng cấu  là một song ánh (bijection), thì hàm nghịch đảo của nó cũng là một phép đồng cấu, và  là phép đẳng cấu đồ thị. Việc xác định xem có tồn tại hay không một phép đồng cấu từ đồ thị này đến đồ thị khác là một bài toán quan trọng trong lý thuyết độ phức tạp tính toán; xem thêm bài toán đồ thị đẳng cấu.

Hai đồ thị  và  là tương đương đồng cấu (homomorphically equivalent) nếu
 và .

Đồ thị con  của đồ thị  được gọi là một rút gọn của  nếu tồn tại một phép đồng cấu , gọi là sự co rút với  cho mỗi đỉnh  của .

Đồ thị nhân là một đồ thị không co rút về một đồ thị con nhỏ hơn. Mỗi đồ thị bất kỳ đều tương đương đồng cấu với một nhân duy nhất.

 Ghi chú 

 Trong thuật ngữ của tô màu đồ thị (graph coloring), các k-colouring của đồ thị  chính là các phép đồng cấu . Do đó, nếu , sắc số (chromatic number) của  không lớn hơn sắc số của : .
Phép đồng cấu đồ thị bảo toàn tính liên thông của đồ thị.

Chú thích


Tham khảo








  (AMSI Vacation Research Scholarships , student research report supervised by Brian Davey and Jane Pitkethly, La Trobe University).

Liên kết ngoài

Thể loại:Lý thuyết đồ thị
Thể loại:Bài toán NP-đủ
Thể loại:Cấu xạ