Đồ thị đầy đủ

Đồ 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: ${\displaystyle {\frac {n(n-1)}{2}}}$

kí hiệu: ${\displaystyle 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 = ${\displaystyle {\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à ${\displaystyle 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ị ${\displaystyle K_{n}}$ có tất cả ${\displaystyle 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ụ

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:

${\displaystyle K_{1}:0}$	${\displaystyle K_{2}:1}$	${\displaystyle K_{3}:3}$	${\displaystyle K_{4}:6}$
${\displaystyle K_{5}:10}$	${\displaystyle K_{6}:15}$	${\displaystyle K_{7}:21}$	${\displaystyle K_{8}:28}$
${\displaystyle K_{9}:36}$	${\displaystyle K_{10}:45}$	${\displaystyle K_{11}:55}$	${\displaystyle K_{12}:66}$

Xem thêm

Chú thích

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

Tham khảo

Liên kết ngoài