✨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\text{'}:=(V\text{'},E\text{'})$, ký hiệu $f:G\; \backslash rightarrow\; G\text{'}$, là một ánh xạ

Định nghĩa trên mở rộng được cho đồ thị có hướng. Khi đó, với phép đồng cấu $f:G\; \backslash rightarrow\; G\text{'}$, $(f(u),f(v))$ là một cung của $G\text{'}$ 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\backslash rightarrow\; H$, ta sẽ viết rằng $G\backslash rightarrow\; H$. Nếu không có, ta viết $G\backslash not\backslash rightarrow\; H$. Nếu $G\backslash 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\backslash 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\text{'}$ là tương đương đồng cấu (homomorphically equivalent) nếu

Đồ 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\backslash 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.