Câu hỏi:
11/07/2023 263
Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 6.
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: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Lời giải:
Giả sử có đồ thị G thỏa mãn yêu cầu bài toán. Gọi x là số đỉnh bậc 3 của đồ thị.
Khi đó số đỉnh bậc 6 của đồ thì là 12 – x.
Tổng tất cả các bậc của đỉnh của đồ thị G là 3x + 6(12 – x) = 3x + 72 – 6x = 72 – 3x.
Mà đồ thị G có 28 cạnh nên tổng tất cả các bậc của đỉnh của đồ thị G bằng 28 . 2 = 56.
Do đó ta có phương trình 72 – 3x = 56, suy ra x = \(\frac{{16}}{3} \notin \mathbb{Z}\), mà số đỉnh phải là số nguyên nên không tồn tại đồ thị thỏa mãn điều kiện đề bài.
Vậy không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 6.
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,093
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
1,645
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,251
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
785
Câu 7:
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.
Xem đáp án »
13/07/2024
549
Bình luận
🔥 Đề thi HOT:
-
100 câu trắc nghiệm Tổ hợp - Xác suất cơ bản (P1)
-
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)
-
93 Bài tập trắc nghiệm Lượng giác lớp 11 có lời giải (P1)
-
75 câu trắc nghiệm Giới hạn nâng cao (P1)
-
100 câu trắc nghiệm Đạo hàm cơ bản (P1)
-
10 Bài tập Tổng của cấp số nhân lùi vô hạn và các bài toán liên quan (có lời giải)
-
10 Bài tập Trung vị, tứ phân vị của mẫu số liệu ghép nhóm và ý nghĩa (có lời giải)
-
75 câu trắc nghiệm Giới hạn cơ bản (P1)
về câu hỏi!