Bài tự luận · Bài 21
Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 21
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 1000 cạnh.
Xem lời giải
Lời giải
Gọi số đỉnh của đồ thị là $n$.
Một đồ thị đầy đủ có $n$ đỉnh thì có $\frac{n(n-1)}{2}$ cạnh.
Ta có $\frac{n(n-1)}{2}\geq 1000\Leftrightarrow n^2-n-2000\geq 0$.
$\Leftrightarrow n\leq\frac{1-3\sqrt{889}}{2}$ hoặc $n\geq\frac{1+3\sqrt{889}}{2}$.
Vì $n$ là số tự nhiên dương và $\frac{1+3\sqrt{889}}{2}\approx45,22$ nên giá trị nhỏ nhất là $n=46$.
Vậy số đỉnh nhỏ nhất cần thiết là 46 thì có thể xây dựng một đồ thị đầy đủ với ít nhất 1000 cạnh.
Một đồ thị đầy đủ có $n$ đỉnh thì có $\frac{n(n-1)}{2}$ cạnh.
Ta có $\frac{n(n-1)}{2}\geq 1000\Leftrightarrow n^2-n-2000\geq 0$.
$\Leftrightarrow n\leq\frac{1-3\sqrt{889}}{2}$ hoặc $n\geq\frac{1+3\sqrt{889}}{2}$.
Vì $n$ là số tự nhiên dương và $\frac{1+3\sqrt{889}}{2}\approx45,22$ nên giá trị nhỏ nhất là $n=46$.
Vậy số đỉnh nhỏ nhất cần thiết là 46 thì có thể xây dựng một đồ thị đầy đủ với ít nhất 1000 cạnh.