HV: HUỲNH THANH PHỤNG GVHD: PGS.TS. ĐỖ VĂN NHƠN
Mục lục:
XÉT ĐẲNG CẤU ĐỒ THỊ VÔ HƯỚNG
1.1 Đẳng cấu giữa hai đồ thị đơn (Single Graph) 2
1.2 Đẳng cấu giữa hai giả đồ thị (Pseudo Graph) 9
1.3 Kết luận 14
Trang 1
HV: HUỲNH THANH PHỤNG GVHD: PGS.TS. ĐỖ VĂN NHƠN
XÉT ĐẲNG CẤU ĐỒ THỊ VÔ HƯỚNG
1.1 Đẳng cấu giữa hai đồ thị đơn (Single Graph)
1.1.1 Định nghĩa
Các đồ thị G
1
= (V
1
,E
1
) và G
2
= (V
2
,E
2
) được gọi là đẳng cấu với nhau nếu có một
song ánh f: V
1
→ V
2
sao cho nếu a và b là liền kề trong V
1
thì f(a) và f(b) liền kề

u
1
a v
1
u
2
a v
4
u
3
a v
2
u
4
a v
3
⇒ f là song ánh và bảo toàn quan hệ liền kề, điều kiện đủ thỏa. Vậy hai đồ
thị G và H đẳng cấu với nhau.
Ví dụ 2:
G và H có cùng số cạnh, số đỉnh nhưng H có đỉnh e' bậc 1, trong khi đó G không có
đỉnh nào bậc 1. Điều kiện cần không thỏa ⇒ G và H không đẳng cấu.
Trang 3
HV: HUỲNH THANH PHỤNG GVHD: PGS.TS. ĐỖ VĂN NHƠN
1.1.2 Thuật giải
Bước 1:
Input: Hai đồ thị vô hướng G, H
Bước 2:
2.1 if (G, H có số đỉnh khác nhau) then
Hai đồ thị có số đỉnh khác nhau
2.2 if (G, H có số cạnh khác nhau) then

>
Trang 8
HV: HUỲNH THANH PHỤNG GVHD: PGS.TS. ĐỖ VĂN NHƠN
1.2 Đẳng cấu giữa hai giả đồ thị (Pseudo Graph)
1.2.1 Định nghĩa
Một giả đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó
gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cạnh, đó là các cặp
không có thứ tự của các đỉnh (không nhất thiết là phân biệt). Với v ∈ V, nếu (v,v) ∈
E thì ta nói có một khuyên tại đỉnh v.
Một giả đồ thị vô hướng tổng quát có thể chứa các khuyên và cho phép đa
cạnh.
Ví dụ:
1.2.2 Thuật giải
Bước 1:
Input: Hai đồ thị vô hướng G1, G2
• Biến V1 lưu trữ danh sách các đỉnh của đồ thị G1
• Biến V2 không đổi, thiết lập hoán vị khác nhau giữa các đỉnh của đồ thị G2,
kiểm tra vị trí từng đỉnh của V1 trong V2 (mỗi lần lặp trong vòng lặp while)
• Biến n lưu trữ số đỉnh của đồ thị G1 để kiểm tra xem có cùng số đỉnh với đồ
thị G2
• Biến i và j dùng để kiểm tra các cạnh của đồ thị
• Biến P danh sách các cạnh hoán vị của G2
• Biến hoanvi là biến đếm các hoán vị đang xét
Trang 9
HV: HUỲNH THANH PHỤNG GVHD: PGS.TS. ĐỖ VĂN NHƠN
• Biến timthay: khởi tạo timthay= false (kiểu bool), biến là điều kiện để kết
thúc vòng lặp nếu hoán vị của các đỉnh đang xét là đẳng cấu được tìm thấy
(timthay = true). Bên trong vòng lặp khi xác định không phải là một đẳng
cấu, đặt timthay = false, cho phép vòng lặp tiếp tục.
Bước 2:

Trang 13
HV: HUỲNH THANH PHỤNG GVHD: PGS.TS. ĐỖ VĂN NHƠN
>
Hai gia do thi dang cau nhu sau:
1 -> "C"
2 -> "A"
3 -> "B"
4 -> "D"
1.3 Kết luận
Để xác định sự đẳng cấu giữa hai đồ thị là một bài toán không đơn giản, vì giữa
hai đồ thị có n đỉnh tồn tại tới n! song ánh giữa hai tập đỉnh. Phương pháp tiếp cận ở
trên chỉ giải quyết bài toán các đồ thị tương đối nhỏ và xác định.
Một cách khác để xác định đồ thị G1 và G2 đẳng cấu nếu các đỉnh của chúng
được sắp xếp lại sao cho cấu trúc các cạnh tương ứng là giống nhau. Nhưng để chỉ
ra đồ thị G1 và G2 không phải đẳng cấu, người ta phải chứng minh rằng không có
một cách sắp xếp nào như vậy.
Cách tiếp cận khác dùng một thuật toán có thời gian chạy đa thức (polynomial-
time algorithm) có số lượng các bước tính toán được giới hạn bởi một hàm đa thức
của kích thước đầu vào. Lớp các bài toán dạng này là được ký hiệu là P. Nếu đồ thị
G1 và G2 là đẳng cấu thì chúng phải có các vector tần suất dấu giống nhau theo thứ
tự từ điển f
i1
, f
i2
, , f
in
trong thời gian theo hàm đa thức.
Trang 14