Đồ thị đầy đủ

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Đồ thị đầy đủ
Complete graph K7.svg
K7, Đồ thị đầy đủ có 7 đỉnh
số đỉnh: n
đường kính: 1
chu trình ngắn nhất: 3 nếu n ≥ 3
số cạnh: \frac{n (n-1)}{2}
kí hiệu: K_n
số đồ thị đẳng cấu: n! (Sn)
sắc số: n
số màu cạnh: n nếu n lẻ
n-1 nếu n chẵn
spectral_gap = \frac{n}{n-1}
tính chất khác
(n-1)-chính quy
Đồ thị đối xứng
Vertex-transitive
Edge-transitive
Strongly regular
Integral

Đồ thị đầy đủ n đỉnh (tiếng Anh: complete graph), kí hiệu là K_n (chữ K lấy từ tiếng Đức komplett[1]), là đồ thị đơn vô hướng mà giữa hai đỉnh bất kì của nó luôn có cạnh nối.

Đồ thị K_n có tất cả n(n-1)/2 cạnh. Nó là đồ thị đơn có nhiều cạnh nhất, đồng thời là đồ thị chính quy bậc n-1.

Ví dụ[sửa | sửa mã nguồn]

Sau đây là danh sách và hình vẽ minh họa các đồ thị đầy đủ với số đỉnh từ 1 đến 12, cùng với số cạnh của chúng:

K_1: 0 K_2: 1 K_3: 3 K_4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K_5: 10 K_6: 15 K_7: 21 K_8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K_9: 36 K_{10}: 45 K_{11}: 55 K_{12}: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg

Xem thêm[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

  1. ^ David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]