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.

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ụ

Xét hai đồ thị:

Tập tin:graphisomorphism1.png

Tập tin: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

 Đồ thị (G1) và (G2) đẳng cấu nhau.
Hình 1: Đẳng cấu đồ thị
 γ(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
Hình 2: Đẳng cấu đồ thị 1
 Hai đồ thị có hướng G3 và G4 không đẳng cấu nhau
Hình 3: Đồ thị không đẳng cấu

 Tính chất của đẳng cấu đồ thị 
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
hinh 2

Cách tìm Song ánh cho đồ thị đẳng cấu
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 
 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 
 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 
 Lý thuyết đồ thị
 Thuật ngữ lý thuyết đồ thị

Tham khảo
 http://mathworld.wolfram.com/IsomorphicGraphs.html
 http://mathcove.net/petersen/lessons/get-lesson?les=3 
 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

Thể loại:Lý thuyết đồ thị
Thể loại:Giải thuật lý thuyết đồ thị