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.
Hai đồ thị G1 và G2 được gọi là đẳng cấu với nhau, ký hiệu là G1 ≈ G2, nếu có thể vẽ lại (bằng cách dời đỉnh, dời cạnh...) sao cho hai đồ thị này có hình vẽ y hệt nhau. Dựa trên cơ sở sự hoán vị đỉnh và hoán vị cạnh, người ta phân biệt thành 2 trường hợp là đồ thị có hướng và đồ thị vô hướ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
- Đồ thị (G1) và (G2) đẳng cấu nhau.
- γ(1)=a, γ(2)=b, γ(3)=c, γ(4)=d
- μ(u1)=e1, μ(u2)=e2, μ(u3)=e6, μ(u4)=e5, μ(u5)=e4, μ(u6)=e3.
- Hai đồ thị vô hướng G1 và G2 đẳng cấu nhau
- Hai đồ thị có hướng G3 và G4 không đẳng cấu nhau
Tính chất của đẳng cấu đồ thị
[sửa | sửa mã nguồn]Hai đồ thị đẳng cấu thì ta có:
- Cùng số đỉnh.
- Cùng số đỉnh bậc k, mọi k nguyên dương ≥ 0.
- Cùng số cạnh.
- Cùng số thành phần.
=> Nếu hai đồ thị có ma trận kề (theo một thứ tự đỉnh nào đó) bằng nhau thì chúng đẳng cấu với nhau.
Hình minh họa
[sửa | sửa mã nguồn]Cách tìm Song ánh cho đồ thị đẳng cấu
[sửa | sửa mã nguồn]Ta có song ánh:
- (A,4); (B,2); (C,1); (D,3); (E,5)
Để có được song ánh như trên thì:
- Ta giữ nguyên thứ tự các đỉnh trong V1 = {A, B, C, D, E}, thứ tự các đỉnh trong V2 được lấy từ một hoán vị của 5 đỉnh {A, B, C, D, E} với 5 đỉnh thì ta có 5! hoán vị, sau đó lấy tương ứng các đỉnh trong V1 và V2 => một song ánh giữa đồ thị G1 và G2. Tìm ma trận kề của hai đồ thị G1 và G2 theo thứ tự đỉnh như trên, nếu có hai ma trận kề giống nhau thì ta được song ánh cần tìm.
Đẳng cấu đồ thị vô hướng
[sửa | sửa mã nguồn]- Cho hai đồ thị vô hướng G1=(X1, E1) và G2=(X2, E2).
- Hai đồ thị G1 và G2 được gọi là đẳng cấu với nhau nếu tồn tại hai song ánh γ và μ thỏa mãn điều kiện sau:
- γ: X1 → X2 và μ: E1 → E2
- Nếu cạnh e ∈ E1 liên kết với cặp đỉnh {x, y} ⊆ X1 xét trong đồ thị G1 thì cạnh μ(e) sẽ liên kết với cặp đỉnh {γ(x), γ(y)} xét trong đồ thị G2 (điều này được gọi là sự tương ứng cạnh).
Đẳng cấu đồ thị có hướng
[sửa | sửa mã nguồn]- Cho hai đồ thị có hướng G1=(X1, E1) và G2=(X2, E2).
- Hai đồ thị G1 và G2 được gọi là đẳng cấu với nhau nếu tồn tại hai song ánh γ và μ thỏa mãn điều kiện sau:
- γ: X1 → X2 và μ: E1 → E2
- Nếu cạnh e ∈ E1 liên kết với cặp đỉnh {x, y} ∈ X1 xét trong đồ thị G1 thì cạnh μ(e) sẽ liên kết với cặp đỉnh {γ(x), γ(y)} xét trong đồ thị G2 (điều này được gọi là sự tương ứng cạnh).
Đọc thêm
[sửa | sửa mã nguồn]Tham khảo
[sửa | sửa mã nguồn]- http://mathworld.wolfram.com/IsomorphicGraphs.html
- http://mathcove.net/petersen/lessons/get-lesson?les=3 Lưu trữ 2013-06-04 tại Wayback Machine
- http://www.edmath.org/MATtours/discrete/concepts/ciso.html
- Trần Đan Thư - Dương Anh Đức, Lý thuyết đồ thị, Nhà xuất bản ĐHQG Thành phố Hồ Chí Minh, 2008. Từ trang 18 đến trang 22
Liên kết ngoài
[sửa | sửa mã nguồn]