Câu hỏi:
11/07/2023 253
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
1,954
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,569
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,012
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
715
Câu 7:
Hãy chỉ ra ít nhất 5 đường đi từ S đến Y trong đồ thị trên Hình 2.38.
Xem đáp án »
13/07/2024
458
về câu hỏi!