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ị $f$ từ đồ thị $G:=(V,E)$ đến đồ thị $G':=(V',E')$, ký hiệu $f:G\rightarrow G'$, là một ánh xạ $f:V\rightarrow V'$ từ tập các đỉnh của $G$ đến tập các đỉnh của $G'$ sao cho $\{f(u),f(v)\}\in E'$ nếu $\{u,v\}\in E$.

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

Nếu tồn tại một phép đồng cấu $f:G\rightarrow H$, ta sẽ viết rằng $G\rightarrow H$. Nếu không có, ta viết $G\not \rightarrow H$. Nếu $G\rightarrow H$, $G$ được coi là đồng cấu với $H$ hay $H$-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 $f:G\rightarrow G$ 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à $f$ 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ị $G$ và $G'$ là tương đương đồng cấu (homomorphically equivalent) nếu $G\rightarrow G'$ và $G'\rightarrow G$.

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

Đồ 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ị $G$ chính là các phép đồng cấu $f:G\rightarrow K_{k}$. Do đó, nếu $G\rightarrow H$, sắc số (chromatic number) của $G$ không lớn hơn sắc số của $H$: $\chi (G)\leq \chi (H)$.
• Phép đồng cấu đồ thị bảo toàn tính liên thông của đồ thị.

Tham khảo

• P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications 28, Oxford University Press, 2004.

Xem thêm

• Hadwiger's conjecture.
• Graph rewriting