Đồ thị đầy đủ
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

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:

       
       
       
       
       
       

Xem thêm sửa

Chú thích sửa

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

Tham khảo sửa

Liên kết ngoài sửa