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ị $G$$G$ và $H$$H$:

$f:V(G)\rightarrow V(H)$$f:V(G)\rightarrow V(H)$

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

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

$f(a)=1$$f(a)=1$

$f(b)=6$$f(b)=6$

$f(c)=8$$f(c)=8$

$f(d)=3$$f(d)=3$

$f(g)=5$$f(g)=5$

$f(h)=2$$f(h)=2$

$f(i)=4$$f(i)=4$

$f(j)=7$$f(j)=7$

Xem thêm

• Phép đồng cấu đồ thị