Câu hỏi:
25 lượt xemTì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
Hướng dẫn 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à (𝑛(𝑛−1))/2.
Vì G có ít nhất 1 000 cạnh nên ta có (𝑛(𝑛−1))/2≥1000
⇔ n(n – 1) – 2 000 ≥ 0
⇔ n2 – n – 2 000 ≥ 0 (*)
Giải bất phương trình (*), ta được 𝑛≤(1−3 căn 889)/2≈−44,22 (không thỏa mãn) hoặc 𝑛≥(1+3 căn 889)/2≈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.
Hãy chỉ ra ít nhất 5 đường đi từ S đến Y trong đồ thị trên Hình 2.38.
Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.41.
Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.42.
ĐỀ THI LIÊN QUAN:
-
34 câu hỏi 68 lượt thi