Bài 2.23 trang 50 Chuyên đề học tập Toán 11 Kết nối tri thức

Trang trước Trang sau

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.

Lời giả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 (n - 1)}{2}$ .

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

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

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

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

Lời giải bài tập Chuyên đề Toán 11 Bài tập cuối chuyên đề 2 hay, chi tiết khác:

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

Xem thêm các tài liệu học tốt lớp 11 hay khác:

Trang trước Trang sau

Giải bài tập lớp 11 sách mới các môn học