Câu hỏi:
13/07/2024 629
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.
Câu hỏi trong đề:
Chuyên đề Toán 11 KNTT Bài tập cuối chuyên đề 2 có đáp án !!
Sách mới 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 49k/cuốn).
Quảng cáo
Trả lời:
Giải bởi Vietjack
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\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\)
⇔ n(n – 1) – 2 000 ≥ 0
⇔ n2 – n – 2 000 ≥ 0 (*)
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.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Vẽ đồ thị G = (V, E) với các đỉnh và các cạnh như sau:
V = {1; 2; 3; 4; 5; 6; 7; 8} và E = {12; 13; 23; 34; 35; 67; 68; 78}.
Đồ thị này có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?
Vẽ đồ thị G = (V, E) với các đỉnh và các cạnh như sau:
V = {1; 2; 3; 4; 5; 6; 7; 8} và E = {12; 13; 23; 34; 35; 67; 68; 78}.
Đồ thị này có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?
Xem đáp án »
13/07/2024
2,502
Câu 2:
Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.42.
Xem đáp án »
13/07/2024
2,267
Câu 4:
Chứng minh rằng nếu G là một đơn đồ thị có ít nhất hai đỉnh thì G có ít nhất hai đỉnh cùng bậc.
Xem đáp án »
12/07/2024
1,480
Câu 6:
Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.41.
Xem đáp án »
12/07/2024
982
Câu 7:
Kiểm tra xem các điều kiện của định lí Ore có thỏa mãn với các đồ thị trên Hình 2.39 không.
Xem đáp án »
11/07/2023
902
Bình luận
🔥 Đề thi HOT:
-
10 Bài tập Tính xác suất của biến cố hợp của hai biến cố bất kì bằng cách sử dụng công thức cộng xác suất và phương pháp tổ hợp (có lời giải)
-
Bài tập Hình học không gian lớp 11 cơ bản, nâng cao có lời giải (P11)
-
10 Bài tập Vận dụng đạo hàm cấp hai để giải quyết một số bài toán thực tiễn (có lời giải)
-
20 câu trắc nghiệm Toán 11 Kết nối tri thức Mẫu số liệu ghép nhóm có đáp án
-
38 câu trắc nghiệm Toán 11 Kết nối tri thức Lôgarit có đáp án
-
10 Bài tập Bài toán thực tiễn liên quan đến thể tích (có lời giải)
-
10 Bài tập Biến cố hợp. Biến cố giao (có lời giải)
-
10 Bài tập Nhận biết góc phẳng của góc nhị diện và tính góc phẳng nhị diện (có lời giải)
về câu hỏi!