Câu hỏi:
13/07/2024 574
Có thể đi qua tất cả các cây cầu, mỗi cây cầu qua đúng một lần, rồi quay trở về điểm xuất phát?
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).
Quảng cáo
Trả lời:
Sau các bài học của chuyên đề này, chúng ta sẽ giải quyết được bài toán trên như sau:
Biểu thị mỗi vùng đất bằng một đỉnh, mỗi cây cầu bằng một cạnh nối hai đỉnh, ta được đồ thị như hình vẽ.
Ta thấy d(A) = 5; d(B) = d(C) = d(D) = 3.
Suy ra tất cả các đỉnh của đồ thị trên đều có bậc lẻ.
Do đó đồ thị không có chu trình Euler.
Vậy nói cách khác, không thể bắt đầu từ một điểm nào đó trong thành phố, đi qua khắp các cây cầu, mỗi cầu chỉ đi qua một lần, rồi quay về điểm xuất phát.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Một đồ thị có bốn đỉnh có bậc lần lượt là 2; 3; 4; 3. Tính số cạnh của đồ thị và vẽ đồ thị này.
Câu 2:
Biết rằng G là đồ thị có 6 đỉnh, 8 cạnh và các đỉnh của nó có bậc 2 hoặc 4. Đồ thị có bao nhiêu đỉnh bậc 4? Hãy vẽ một đồ thị như vậy.
Câu 3:
Cho đồ thị như Hình 11.
a) Hãy chỉ ra bậc của tất cả các đỉnh và tìm tổng của chúng.
b) Tìm tất cả các đỉnh kề với đỉnh B. Số đỉnh này có bằng bậc của đỉnh B không?
Câu 4:
Hãy chỉ ra các đỉnh, các cạnh, số đỉnh, số cạnh của mỗi đồ thị như Hình 12.
Câu 5:
Cho đồ thị như Hình 13.
a) Chỉ ra bậc của các đỉnh của đồ thị.
b) Chỉ ra các đỉnh bậc lẻ của đồ thị.
c) Tính tổng tất cả các bậc của các đỉnh của đồ thị.
Câu 6:
Đồ thị ở Hình 6 biểu diễn năm ngôi làng A, B, C, D và E cùng các con đường giữa chúng (mỗi cạnh biểu diễn một con đường giữa hai ngôi làng). Biết rằng mỗi con đường ra, vào làng đều phải đi qua một cổng chào; hai con đường khác nhau thì ra, vào làng qua hai cổng chào khác nhau. Ngoài ra, các ngôi làng không còn cổng chào nào khác.
a) Ngôi làng nào có ít cổng chào nhất? Ngôi làng nào có nhiều cổng chào nhất?
b) Năm ngôi làng có tất cả bao nhiêu cổng chào?
Câu 7:
Có năm học sinh An, Bình, Mai, Quang, Xuân. Biết rằng An quen Bình, Bình quen Quang, An quen Mai, Mai quen Xuân, Xuân quen Quang. Các cặp không được liệt kê ở trên thì không quen nhau. Hãy vẽ đồ thị để thể hiện mối quan hệ quen nhau giữa các học sinh trên.
về câu hỏi!