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

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ụ

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

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

Tham khảo

Liên kết ngoài

Lý thuyết đồ thị
Giải thuật lý thuyết đồ thị