Khám phá 4
1. Nội dung câu hỏi
Đồ thị ở Hình 15b biểu diễn các điểm vui chơi trong một công viên với những con đường nối giữa chúng như Hình 15a. Có thể đi theo những con đường này để thăm tất cả các điểm vui chơi mỗi điểm đúng một lần hay không? Nếu có, chỉ ra ít nhất một đường đi như vậy.
2. Phương pháp giải
Quan sát hình vẽ để trả lời
3. Lời giải chi tiết
Ta có thể đi theo những con đường này để thăm tất cả các điểm vui chơi mỗi điểm đúng một lần.
Chẳng hạn, ta có thể đi theo một số đường đi như sau: ANMBCPD, NBMADPC, DANMBCP,…
Thực hành 3
1. Nội dung câu hỏi
Hãy chỉ ra rằng mỗi đồ thị sau đây có chu trình Hamilton.
2. Phương pháp giải
Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần.
Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton.
3. Lời giải chi tiết
⦁ Hình 21a:
Đồ thị ở Hình 21a có các đỉnh A, F có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh AB, AD, FD, FC trong đồ thị ở Hình 21a.
Do đó h không thể đi qua các cạnh BD, DC.
Nếu xóa đi hai cạnh này thì đỉnh B, C trở thành có bậc 2.
Vì vậy h phải đi qua cạnh BC.
Khi đó ta được chu trình Hamilton h: ADFCBA.
⦁ Hình 21b:
Đồ thị ở Hình 21b có các đỉnh F, I có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh FE, FB, IA, IC.
Do đó ta được chu trình Hamilton h: AICBFEDA (hoặc AICDEFBA).
Vậy cả hai đồ thị đã cho đều có chu trình Hamilton.
Vận dụng 2
1. Nội dung câu hỏi
Các đỉnh của đồ thị ở Hình 22 biểu thị các điểm du lịch trong một thành phố, các cạnh biểu thị đường đi giữa các điểm du lịch này. Có hay không một cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch?
2. Phương pháp giải
Kiểm tra xem đường đi có là chu trình Hamilton không.
Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần. Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton.
3. Lời giải chi tiết
Đồ thị ở Hình 22 có các đỉnh B, K có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi các các cạnh AB, BC, AK, KI.
Do đó h không thể đi qua các cạnh AI, AD, AD, AE.
Nếu xóa đi bốn cạnh trên thì các đỉnh A, D trở thành bậc 2.
Suy ra h phải đi qua các cạnh AB, AK, DC, DF.
Do đó h không thể đi qua các cạnh CE, CF.
Nếu xóa đi thêm hai cạnh trên thì đỉnh E trở thành bậc 2.
Suy ra h phải đi qua các cạnh EI, EF.
Vì vậy ta được chu trình Hamilton h: ABCDFEIKA.
Vậy có cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch.
Chủ đề 4: Kĩ thuật bắt bóng của thủ môn và chiến thuật phòng thủ
Bài 7. Pháp luật về quản lí vũ khí, vật liệu nổ, công cụ hỗ trợ
Chuyên đề 3: Một số yếu tố vẽ kĩ thuật
Chương 6. Hợp chất carbonyl (Aldehyde - Ketone - Carboxylic acid
Bài giảng ôn luyện kiến thức giữa học kì 2 môn Giáo dục kinh tế và pháp luật lớp 11
SBT Toán Nâng cao Lớp 11
SGK Toán 11 - Kết nối tri thức với cuộc sống
SGK Toán 11 - Cánh Diều
SGK Toán 11 - Chân trời sáng tạo
Chuyên đề học tập Toán 11 - Kết nối tri thức với cuộc sống
Chuyên đề học tập Toán 11 - Cánh Diều
SBT Toán 11 - Kết nối tri thức với cuộc sống
SBT Toán 11 - Cánh Diều
SBT Toán 11 - Chân trời sáng tạo
Tổng hợp Lí thuyết Toán 11
Bài giảng ôn luyện kiến thức môn Toán lớp 11
SBT Toán Lớp 11
SGK Toán Nâng cao Lớp 11
SGK Toán Lớp 11
Quên mật khẩu ?
Hoặc đăng nhập với
Điểm cần để chuộc tội: 0
Bé Cà đang rất bực vì quỹ điểm của bạn đã đạt ngưỡng báo động. Bé Cà đã tắt quyền đặt câu hỏi của bạn. Mau kiếm bù điểm chuộc lỗi với bé Cà
FQA tặng bạn
HSD: -
Xem lại voucher tại Trang cá nhân -> Lịch sử quà tặng
FQA tặng bạn
HSD: -
Xem lại voucher tại Trang cá nhân -> Lịch sử quà tặng
Để nhận quà tặng voucher bạn cần hoàn thành một nhiệm vụ sau