Câu hỏi:

11/07/2023 245

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.

Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 140k).

Mua bộ đề Hà Nội Mua bộ đề Tp. Hồ Chí Minh Mua đề Bách Khoa

Quảng cáo

Trả lời:

verified
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.

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?

Xem đáp án » 13/07/2024 1,881

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.
Media VietJack

Xem đáp án » 13/07/2024 1,508

Câu 3:

Viết tập hợp các đỉnh và tập hợp các cạnh của mỗi đồ thị sau:
Media VietJack

Xem đáp án » 13/07/2024 1,319

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 917

Câu 5:

Tìm một chu trình Euler trong đồ thị trên Hình 2.40.
Media VietJack

Xem đáp án » 13/07/2024 766

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.
Media VietJack

Xem đáp án » 12/07/2024 677

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.
Media VietJack

Xem đáp án » 13/07/2024 447

Bình luận


Bình luận
Đăng ký gói thi VIP

VIP 1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 2 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 3 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 4 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

tailieugiaovien.com.vn