Đẳ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. 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. 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. 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). 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). Đồ 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 Lý thuyết đồ thị Thuật ngữ lý thuyết đồ thị 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