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ị ${\displaystyle G}$ và ${\displaystyle H}$:

${\displaystyle f:V(G)\rightarrow V(H)}$

với tính chất rằng cặp đỉnh ${\displaystyle u}$ và ${\displaystyle v}$ bất kỳ của ${\displaystyle G}$ kề nhau khi và chỉ khi hai đỉnh ${\displaystyle f(u)}$ và ${\displaystyle f(v)}$ kề nhau trong đồ thị ${\displaystyle 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.

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

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

${\displaystyle f(a)=1}$

${\displaystyle f(b)=6}$

${\displaystyle f(c)=8}$

${\displaystyle f(d)=3}$

${\displaystyle f(g)=5}$

${\displaystyle f(h)=2}$

${\displaystyle f(i)=4}$

${\displaystyle f(j)=7}$

• Đồ thị (G1) và (G2) đẳng cấu nhau.

1. γ(1)=a, γ(2)=b, γ(3)=c, γ(4)=d
2. μ(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ị

Hai đồ thị đẳng cấu thì ta có:

1. Cùng số đỉnh.
2. Cùng số đỉnh bậc k, mọi k nguyên dương ≥ 0.
3. Cùng số cạnh.
4. 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:

1. γ: X1 → X2 và μ: E1 → E2
2. 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:

1. γ: X1 → X2 và μ: E1 → E2
2. 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 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