Giải bài 2. 23 trang 50 Chuyên đề học tập Toán 11 Kết nối tri thức — Không quảng cáo

Đề bài

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.

Lời giải chi tiết

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\)

\(\begin{array}{*{20}{l}}{ \Leftrightarrow \;n\left( {n-1} \right)-2000 \ge 0}\\{ \Leftrightarrow \;{n^2}\;-n-2000{\rm{ }} \ge {\rm{ }}0{\rm{ }}\left( * \right)}\end{array}\)

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