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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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ị GH:

 f: V(G) \rightarrow V(H)

với tính chất rằng cặp đỉnh uv bất kỳ của G kề nhau khi và chỉ khi hai đỉnh f(u)f(v) kề nhau trong đồ thị H.

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ị:

Graphisomorphism1.png

Graphisomorphism2.png

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

 f(a) = 1
 f(b) = 6
 f(c) = 8
 f(d) = 3
 f(g) = 5
 f(h) = 2
 f(i) = 4
 f(j) = 7

Xem thêm[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]