Đơn đồ thị, đa đồ thị, đồ thị đầy đủ là gì? - Toán 11

Một đồ thị là một tập hợp gồm hữu hạn các điểm (gọi là đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị.

Chú ý: Các cạnh của đồ thị thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào đều không quan trọng.

Giả sử có đồ thị G:

- Tập hợp đỉnh V(G) = {A, B, C, D}.

- Tập hợp cạnh E(G) = {AB, AC, AD, BC, CC}.

- Hai đỉnh kề nhau nếu chúng là hai đầu mút của một cạnh, ví dụ A – B.

- Một đỉnh không kề với đỉnh nào (kể cả chính nó) gọi là đỉnh cô lập.

- Cạnh có hai đầu mút trùng nhau gọi là khuyên, ví dụ CC.

Một đồ thị không có khuyên (cạnh có hai đầu mút trùng nhau gọi là khuyên), trong đó hai đỉnh được nối bằng nhiều nhất một cạnh (không có hai cạnh nào cùng nối một cặp đỉnh) gọi là đơn đồ thị.

Ví dụ:

Đồ thị ở Hình a) là đồ thị đơn.

Đồ thị ở Hình b) không phải là đồ thị đơn vì có hai cạnh của đồ thị nối cặp đỉnh A, C.

Đồ thị ở Hình c) không phải là đồ thị đơn vì có đỉnh C được nối với chính nó bởi một cạnh của đồ thị.

Một đồ thị không có khuyên (cạnh có hai đầu mút trùng nhau gọi là khuyên), trong đó hai đỉnh có thể nối bằng nhiều cạnh, gọi là đa đồ thị.

Ví dụ:

Hình a) không có khuyên và có hai cạnh nổi hai đỉnh Z và W, nên là một đa đồ thị.

Hình b) có khuyên nên không phải là đơn đồ thị, cũng không phải là đa đồ thị.

Hình c) không có khuyên và hai đỉnh chỉ được nối bằng nhiều nhất một cạnh nên là một đơn đồ thị.

Một đồ thị là đầy đủ khi và chỉ khi mỗi cặp đỉnh của nó đều được nối bằng một cạnh.

Nhận xét: Một đồ thị đầy đủ là đồ thị mà mọi cặp đỉnh của nó là kề nhau. Đồ thị đầy đủ n đỉnh thường được kí hiệu là \({K_n}\).

Ví dụ:

Ta có các đồ thị \({K_2}\), \({K_3}\) và \({K_4}\) như hình: