Câu hỏi:
25 lượt xemChứ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.
Lời giải
Hướng dẫn 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 = 16/3 ∉ℤ, 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.
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