SỰ ĐẲNG CẤU CỦA CÁC ĐỒ THỊ

Nhóm 7 :

• Duy Ân - 100301
• Minh Trung - 100310
• Bùi Vũ - 100304

Lời nói đầu

• Thông thường, người ta cần biết xem có thể vẽ được hai đồ thị theo cùng một cách không.
• Chẳng hạn trong hóa học, đồ thị dùng để mô hình hóa hợp chất. Các hợp chất có cấu trúc khác nhau có thể cùng công thức phân tử.
• Các hợp chất như vậy sẽ được biểu diễn bằng các đồ thị mà ta không thể vẽ được cùng một cách.
• Những đồ thị biểu diễn các hợp chất đã biết có thể được dùng để xác định xem một hợp chất mới thực ra đã biết từ trước chưa.

Lời nói đầu (tt)

Hình vẽ một đồ thị có 6 đỉnh và 7 cạnh (Wikipedia)

Đẳng cấu đồ thị (Graph Isomorphism)

• ĐỊNH NGHĨA :

Các đơn đồ thị G₁=(V₁,E₁) và G₂=(V₂,E₂) là đẳng cấu nếu tồn tại một song ánh f từ V₁ lên V₂ sao cho a và b là các đỉnh liền kề trong G₁ nếu và chỉ nếu f(a) và f(b) là liền kề trong G₂ , với mọi a và b trong V₁. Hàm f như thế được gọi là một đẳng cấu.

​

• Nói cách khác, khi hai đồ thị là đẳng cấu thì sẽ tồn tại một phép tương ứng 1-1 giữa các đỉnh của hai đồ thị bảo toàn quan hệ liền kề.

​

Đẳng cấu đồ thị (Graph Isomorphism)

Hai đồ thị đẳng cấu với nhau (Wikipedia)

Ví dụ

Những đồ thị nào sau đây đẳng cấu với nhau ?

​

​

​

​

​

​

Ví dụ

Hãy chứng minh rằng 2 đồ thị sau không đẳng cấu :

​

G

H

a

e

d

c

b

a

e

d

c

b

Nhận xét

Để xác định 2 đồ thị có đẳng cấu hay không :

• Các đồ thị đẳng cấu phải có cùng số đỉnh.
• Các đồ thị đẳng cấu phải có cùng số cạnh.
• Bậc của các đỉnh tương ứng phải như nhau.
• Các đồ thị phải có các chu trình đơn có độ dài như nhau.

Ví dụ

Hai đồ thị sau có phải là đẳng cấu không :

​

G

H

v3

v4

v5

v1

v2

u1

u2

u3

u5

u4

Ví dụ (tt)

Giải :

Ma trận kề tương ứng của 2 đồ thị :

​

u

1

u

2

u

3

u

4

u

5

u

1

0

1

1

0

1

u

2

1

0

1

0

1

u

3

1

1

0

0

0

u

4

0

0

0

0

1

u

5

1

1

0

1

0

v

3

v

4

v

5

v

2

v

1

v

3

0

1

1

0

1

v

4

1

0

1

0

1

v

5

1

1

0

0

0

v

2

0

0

0

0

1

v

1

1

1

0

1

0

A_G =

A_H =

Chu trình đơn là gì ?

Hai đồ thị sau có phải là đẳng cấu không ?

​

u1

u3

u4

u2

u5

v5

v2

v3

v1

v4

Chu trình đơn là gì ?

Hai đồ thị sau có phải là đẳng cấu không ?

​

u6

u5

u3

u2

u1

u4

G

v6

v5

v3

v2

v1

v4

H

Một số hình ảnh về đẳng cấu đồ thị

Nguồn: www.dharwadker.org

Ứng dụng

• ĐTĐC được sử dụng để xác định một hợp chất hóa học trong CSDL Hóa học hoặc để tìm kiếm, định danh và cung cấp thông tin trong CSDL or web.

​

• ĐTĐC còn được ứng dụng trong việc thiết kế mạch điện tử tự động hóa nhằm đơn giản hóa và tối ưu mạch điện.

​

• Cheminformatics là sự hết hợp giữa khoa học máy tính và lĩnh vực hóa học nhằm cung cấp thông tin, dữ liệu và phân tích chính xác cho việc nghiên cứu.(vd: ngành CN giấy, hóa chất, y học…).

​

�The End

​

Cảm ơn cô và các bạn đã quan tâm !

​