Có một vùng biển gồm 300 hòn đảo. Người ta xây dựng cây cầu; mỗi cây cầu nối trực tiếp hai hòn đảo với nhau, và giữa hai hòn đảo có không quá một cây cầu.
(1) Tìm số lượng cây cầu lớn nhất có thể xây dựng, biết rằng tồn tại ít nhất một tuyến du lịch khép kín đi qua tất cả các cây cầu, mỗi cây cầu đúng một lần; một hòn đảo có thể được đi qua nhiều lần.
(2) Các hòn đảo được phân cho 5 vương quốc khác nhau quản lí, mỗi hòn đảo do đúng một vương quốc quản lí. Hệ thống cầu có tính chất: mọi tuyến du lịch khép kín đều phải đi qua các hòn đảo thuộc đủ cả 5 vương quốc. Hỏi tổng số cây cầu có thể vượt quá 398 hay không?

Phương pháp & hướng dẫn giải

Phương pháp & hướng dẫn giải: Ta mô hình hóa bài toán bằng một đồ thị đơn G = (V, E), trong đó mỗi đỉnh tương ứng với một hòn đảo và mỗi cạnh tương ứng với một cây cầu. Khi đó |V| = 300 và |E| = m. (1)... Xem đáp án chính thức và trọn bộ lời giải chi tiết từng bước câu hỏi thuộc Đề Chọn ĐTQG TP Hồ Chí Minh 2026 - Ngày 2 (Lim Olympic - TPHCM TST) trên dethichuan.com.

Quảng cáo
Câu hỏi này trích từ đề thi chính thức:

Đề Chọn ĐTQG TP Hồ Chí Minh 2026 - Ngày 2 (Lim Olympic - TPHCM TST)

4 câu hỏi•Thời gian 90 phút•Chấm điểm & giải thích chi tiết

Các câu hỏi khác trong đề (4 câu)

Xem toàn bộ đề →
Chuyên đề học tập • Lớp 11

Bài tập trắc nghiệm cùng chuyên đề: Đường đi và chu trình Euler (15 câu)

Câu luyện thêm 1Trích từ: Đề Thi Chọn Học Sinh Giỏi Cấp Trường Toán 10 THPT Thuận Thành - Đề Số 1
Một người đưa thư xuất phát từ bưu điện ở vị trí A, các điểm cần phát thư nằm dọc các con đường cần đi qua. Biết rằng người này phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho tất cả các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại điểm xuất phát. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu?

Hình từ đề gốc
Xem trang câu hỏi →
Câu luyện thêm 2Trích từ: Đề Thi Học Sinh Giỏi Lớp 12 Cấp Tỉnh Đề Thi Thử Lần IV Môn Toán
Cho bảy điểm có là hình chữ nhật, là trung điểm , độ dài các cạnh được ghi trên hình vẽ (đơn vị độ dài). Hình từ đề gốc Một trò chơi được quy định như sau: xuất phát từ một điểm bất kỳ trong bảy điểm trên đi qua hết tất cả các cạnh trên hình vẽ mỗi cạnh ít nhất một lần rồi quay lại điểm xuất phát. Người chơi là người thắng cuộc nếu tổng độ dài đường đi là ngắn nhất. Tính tổng độ dài đường đi đó.
Xem trang câu hỏi →
Câu luyện thêm 3Trích từ: Đề Khảo Sát Chất Lượng Thi Tốt Nghiệp THPT Lần 2 Toán 12 THPT Khoa Học Giáo Dục 2024-2025
Một người đưa thư xuất phát từ bưu điện ở vị trí , các điểm cần phát thư nằm dọc theo các con đường cần phải đi qua. Biết người này phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho tất cả các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại điểm xuất phát. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể bằng bao nhiêu?

Hình từ đề gốc
Xem trang câu hỏi →
Câu luyện thêm 4Trích từ: Đề Khảo Sát Học Sinh Giỏi Lớp 12 Sở GD&ĐT Ninh Bình Cụm THPT Số 11
Một người đưa thư xuất phát từ bưu điện (vị trí A) và phải đi qua các con đường để phát thư rồi quay lại bưu điện. Sơ đồ các con đường cần đi qua và độ dài của chúng (tính theo mét) được biểu diễn ở hình vẽ dưới. Độ dài đường đi ngắn nhất của người đó là bao nhiêu mét?

Hình từ đề gốc
Xem trang câu hỏi →
Câu luyện thêm 5Trích từ: Đề Thi Thử Tốt Nghiệp THPT Toán 2025-2026 THPT Xuân Đỉnh - Đề Số 06
Một người đưa thư xuất phát từ bưu điện ở vị trí A, các điểm cần phát thư nằm dọc các con đường cần đi qua. Biết rằng người này phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho tất cả các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại điểm xuất phát. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu?
Hình từ đề gốc
Xem trang câu hỏi →
Câu luyện thêm 6Trích từ: Đề Thi Thử Tốt Nghiệp THPT 2025 Môn Toán Lần 2 Sở GD&ĐT Hậu Giang (Mã Đề 0101)
Trong một lần sáp nhập tỉnh, tỉnh A được thành lập gồm có 6 phường và 55 xã. Ta kí hiệu 6 phường này là 1, 2, 3, 4, 5, 6. Giữa các phường có các con đường mới xây dựng và có thể di chuyển bằng ô tô, được biểu diễn bằng các đoạn thẳng hoặc đoạn cong như hình vẽ. Anh Hoàng ở Phường 2, anh định dùng ô tô để đi tham quan tất cả các con đường nói trên sao cho mỗi con đường chỉ đi đúng một lần rồi trở về Phường 2. Nhưng tiếc rằng hiện tại chắc chắn không có cách nào để đi được như thế.
Hình 1
Gọi là con đường đi trực tiếp từ Phường đến Phường và không giao nhau với các con đường khác, với . Nếu bạn được phép xây dựng thêm duy nhất một con đường thì hãy cho biết giá trị bằng bao nhiêu để anh Hoàng có thể thực hiện được ý định nêu trên?
Xem trang câu hỏi →

Muốn biết hiện tại bạn đạt khoảng bao nhiêu điểm ở môn này? Làm thử đề nhanh 15 phút để hệ thống chấm điểm ngay.

Làm đề nhanh 15 phút ngay