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

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

Đồ thị con ${\displaystyle H}$ của đồ thị ${\displaystyle G}$ được gọi là một rút gọn của ${\displaystyle G}$ nếu tồn tại một phép đồng cấu ${\displaystyle r:G\rightarrow H}$, gọi là sự co rút với ${\displaystyle r(x)=x}$ cho mỗi đỉnh ${\displaystyle x}$ của ${\displaystyle 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ị ${\displaystyle G}$ chính là các phép đồng cấu ${\displaystyle f:G\rightarrow K_{k}}$. Do đó, nếu ${\displaystyle G\rightarrow H}$, sắc số (chromatic number) của ${\displaystyle G}$ không lớn hơn sắc số của ${\displaystyle H}$: ${\displaystyle \chi (G)\leq \chi (H)}$.
• 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

• Cameron, Peter (2006), Graph Homomorphisms, Combinatorics Study Group Notes (PDF)
• Hell, Pavol; Nešetřil, Jaroslav (2004), Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications, quyển 28, Oxford University Press, ISBN 0-19-852817-5
• Hahn, Geňa; Tardif, Claude (1997), "Graph homomorphisms: structure and symmetry", Graph Symmetry: Algebraic Methods and Applications (PDF), Springer, tr. 107–166, doi:10.1007/978-94-015-8937-6_4, ISBN 978-90-481-4885-1, Bản gốc (PDF) lưu trữ ngày 11 tháng 7 năm 2021, truy cập ngày 9 tháng 4 năm 2017
• Godsil, Chris; Royle, Gordon (2001), "6. Homomorphisms", Algebraic Graph Theory, Graduate Texts in Mathematics, quyển 207, Springer–Verlag New York, doi:10.1007/978-1-4613-0163-9, ISBN 978-1-4613-0163-9, S2CID 9661174
• Lovász, László (2012). Large Networks and Graph Limits (PDF). Providence, Rhode Island: American Mathematical Soc. ISBN 978-0-8218-9085-1.
• Bodirsky, Manuel (2007), Graph Homomorphisms and Universal Algebra, Course Notes (PDF)
• Hell, Pavol; Nešetřil, Jaroslav (2008), "Colouring, constraint satisfaction, and complexity" (PDF), Computer Science Review, 2 (3): 143–163, doi:10.1016/j.cosrev.2008.10.003, Bản gốc (PDF) lưu trữ ngày 6 tháng 7 năm 2017, truy cập ngày 9 tháng 4 năm 2017
• Brown, Ronald; Morris, Ifor; Shrimpton, John; Wensley, Christopher D. (2008), "Graphs of morphisms of graphs", Electronic Journal of Combinatorics, 15 (1): A1, doi:10.37236/919
• Gray, Charles T. (2014), The Digraph Lattice (PDF) (AMSI Vacation Research Scholarships Lưu trữ ngày 14 tháng 8 năm 2018 tại Wayback Machine, student research report supervised by Brian Davey and Jane Pitkethly, La Trobe University).

Liên kết ngoài