Câu hỏi:

11/07/2024 924

Có năm vùng đất A, B, C, D và E được nối với nhau bằng những cây cầu như Hình 28.

a) Có hay không cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ qua một lần, rồi quay trở lại nơi xuất phát?

b) Nếu không yêu cầu quay lại nơi bắt đầu thì có cách đi như vậy không? Nếu có, hãy chỉ ra một cách đi.

Xem lời giải

Câu hỏi trong đề: Chuyên đề Toán 11 CTST Chuyên đề 2. Lí thuyết đồ thị có đáp án !!

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 (chỉ từ 110k).

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

Quảng cáo

Trả lời:

Giải bởi Vietjack

a) 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ẽ.

Có năm vùng đất A, B, C, D và E được nối với nhau bằng những cây cầu như Hình 28. a) Có hay không cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ qua một lần, rồi quay trở lại nơi xuất phát? b) Nếu không yêu cầu quay lại nơi bắt đầu thì có cách đi như vậy không? Nếu có, hãy chỉ ra một cách đi. (ảnh 2)

Ta có d(A) = d(B) = d(C) = 4; d(D) = d(E) = 3.

Suy ra đồ thị trên có đúng hai đỉnh bậc lẻ là D, E.

Do đó đồ thị trên có đường đi Euler nhưng không có chu trình Euler.

Vậy nói cách khác, không có cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ qua một lần, rồi quay trở lại nơi xuất phát.

b) Nếu không yêu cầu quay lại nơi bắt đầu thì có cách đi như vậy (vì đồ thị trên có đường đi Euler).

Chẳng hạn, bắt đầu từ đỉnh A, ta có thể đi theo đường đi Euler: DACDECBabBE.

Nhà sách VIETJACK:

Xem thêm kho sách »

Combo - Sổ tay kiên thức trọng tâm Toán, Lí, Hóa dành cho 2k7 VietJack

₫29.000 (Đã bán 152)

Sách - Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia Hà Nội 2025 cho 2k7 VietJack

₫140.000 ₫300.000 (Đã bán 1,2k)

Sách Combo - Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia TP Hồ Chí Minh (2 cuốn) - 2025 cho 2k7 VietJack

₫140.000 ₫300.000 (Đã bán 1,6k)

Sách - Tuyển tập 15 đề thi Đánh giá tư duy Đại học Bách Khoa Hà Nội 2025 cho 2k7 VietJack

₫140.000 ₫300.000 (Đã bán 2,7k)

Bình luận hoặc Báo cáo
về câu hỏi!

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.

Xem đáp án » 13/07/2024 2,914

Câu 2:

Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.

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

Câu 3:

a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không?

b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?

Xem đáp án » 11/07/2024 1,170

Câu 4:

Chỉ ra một đường đi Hamilton của đồ thị ở Hình 26.

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

Câu 5:

Chỉ ra một chu trình Hamilton của đồ thị ở Hình 25.

Xem đáp án » 11/07/2024 1,122

Câu 6:

Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy.

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

Câu 7:

Hãy chỉ ra một đường đi Euler trên mỗi đồ thị sau. Mỗi đồ thị có bao nhiêu đỉnh bậc lẻ?

Xem đáp án » 12/07/2024 1,066

Xem thêm các câu hỏi khác »