Phép đẳng cấu đồ thị
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
![]() |
Phép đẳng cấu đồ thị (tiếng Anh: graph isomorphism) là một song ánh giữa các tập đỉnh của hai đồ thị và :
với tính chất rằng cặp đỉnh và bất kỳ của kề nhau khi và chỉ khi hai đỉnh và kề nhau trong đồ thị .
Nếu có thể xây dựng một phép đẳng cấu giữa hai đồ thị, ta nói rằng hai đồ thị này đẳng cấu với nhau.
Bài toán đồ thị đẳng cấu xác định xem hai đồ thị có đẳng cấu với nhau hay không.
Ví dụ[sửa | sửa mã nguồn]
Xét hai đồ thị:
Tuy trông rất khác nhau, chúng là hai đồ thị đồng cấu. Dưới đây là một phép đẳng cấu giữa chúng
Xem thêm[sửa | sửa mã nguồn]
Tham khảo[sửa | sửa mã nguồn]
Liên kết ngoài[sửa | sửa mã nguồn]
![]() |
Tra phép đẳng cấu đồ thị trong từ điển mở tiếng Việt Wiktionary |