2.23. 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 Làm:
Gọi số đỉnh của đồ thị là n.
Theo bài tập 2.4 trang 40 (Bài 8: Một vài khái niệm cơ bản) ta có: 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 \left[\begin{matrix}x &\leq \frac{1-3\sqrt{889}}{2}\\ \frac{1+3\sqrt{889}}{2} &\leq x\\\end{matrix}\right.$
Vì n là số tự nhiên dương nên chọn giá trị $45\approx \frac{1+3\sqrt{889}}{2} \leq x$.
Vậy số đỉnh nhỏ nhất cần thiết là 45 thì có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh.
