Đồ thị đầy đủ

Đồ 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 đổi

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êmSửa đổi

Chú thíchSửa đổi

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

Tham khảoSửa đổi

Liên kết ngoàiSửa đổi