Đẳ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ó BULLET 1 Cùng số đỉnh BULLET 2 Cùng số đỉnh bậc k mọi k nguyên dương 0 BULLET 3 Cùng số cạnh BULLET 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 Cách tìm Song ánh cho đồ_thị đẳng_cấu Ta có song ánh BULLET A 4 B 2 C 1 D 3 E 5 Để có được song ánh như trên thì Đẳng_cấu đồ_thị vô hướng BULLET Cho hai đồ_thị vô hướng G1 X1 E1 và G2 X2 E2 BULLET 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à μ thoả_mãn điều_kiện sau BULLET 1 γ X1 X2 và μ E1 E2 BULLET 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 BULLET Cho hai đồ_thị có hướng G1 X1 E1 và G2 X2 E2 BULLET 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à μ thoả_mãn điều_kiện sau BULLET 1 γ X1 X2 và μ E1 E2 BULLET 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 Ví_dụ BULLET Đồ_thị G1 và G2 đẳng_cấu nhau BULLET 1 γ 1 a γ 2 b γ 3 c γ 4 d BULLET 2 μ u1 e1 μ u2 e2 μ u3 e6 μ u4 e5 μ u5 e4 μ u6 e3 BULLET Hai đồ_thị vô hướng G1 và G2 đẳng_cấu nhau BULLET Hai đồ_thị có hướng G3 và G4 không đẳng_cấu nhau Đọc thêm BULLET Lý_thuyết đồ_thị BULLET Thuật_ngữ lý_thuyết đồ_thị Tham_khảo BULLET http mathworld wolfram com IsomorphicGraphs html BULLET http mathcove net petersen lessons get lesson les 3 BULLET http www edmath org MATtours discrete concepts ciso html BULLET 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
Đẳng_cấu đồ_thị