Tìm số đỉnh nhỏ nhất cần thiết để có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh

Bài 2.23 trang 50 Chuyên đề Toán 11: Tìm số đỉnh nhỏ nhất cần thiết để có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh.

Trả lời

Giả sử G là một đồ thị đầy đủ có n đỉnh và có ít nhất 1 000 cạnh (n ∈ ℕ, n ≥ 2).

Vì G là đồ thị đầy đủ nên mỗi cặp đỉnh của G đều được nối với nhau bằng một cạnh, do đó mỗi đỉnh của G đều có bậc là (n – 1).

Tổng tất cả các bậc của các đỉnh của G là n(n – 1).

Suy ra G có số cạnh là $\frac{n\left(n-1\right)}{2}$.

Vì G có ít nhất 1 000 cạnh nên ta có $\frac{n\left(n-1\right)}{2}\ge 1000$

⇔ n(n – 1) – 2 000 ≥ 0

⇔ n² – n – 2 000 ≥ 0 (*)

Giải bất phương trình (*), ta được $n\le \frac{1-3\sqrt{889}}{2}\approx -\mathrm{44,22}$ (không thỏa mãn) hoặc $n\ge \frac{1+3\sqrt{889}}{2}\approx \mathrm{45,22}$ (thỏa mãn).

Do n là số tự nhiên nên n nhỏ nhất thỏa mãn là 46.

Vậy số đỉnh nhỏ nhất cần thiết để có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh là 46 đỉnh.

Xem thêm các bài giải Chuyên đề Toán lớp 11 Kết nối tri thức hay, chi tiết khác: