Đồ 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:
kí hiệu:
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 =
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à (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ị có tất cả 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:

Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
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]