Đẳng cấu đồ thị

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.

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

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).

Ví dụ 

 Đồ 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

Đọ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