Khám phá 1
1. Nội dung câu hỏi
a) Nếu coi mỗi vùng đất của thành phố Königsberg là một đỉnh, mỗi cây cầu là một cạnh nối hai đỉnh thì ta được một đồ thị G như Hình 1.
Câu hỏi của người dân thành phố trở thành: có hay không cách vẽ bằng một nét bút liền (không nhấc bút) đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, sao cho điểm kết thúc trùng với điểm xuất phát?
Hãy thử vẽ và đưa ra dự đoán của mình.
b) Nếu không có cây cầu nối giữa A và D nhưng có thêm một cây cầu nối B và C thì ta có đồ thị H như Hình 2. Có thể vẽ một nét liền đi qua tất cả các cạnh của đồ thị này, mỗi cạnh đúng một lần không?
2. Phương pháp giải
Quan sát hình vẽ và suy luận để trả lời
3. Lời giải chi tiết
a) Sau khi thử vẽ, ta dự đoán: không có cách vẽ bằng một nét bút liền (không nhấc bút) đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, sao cho điểm kết thúc trùng với điểm xuất phát.
b) Ta có thể vẽ một nét liền đi qua tất cả các cạnh của đồ thị này, mỗi cạnh đúng một lần bằng cách lần lượt vẽ các cạnh m, s, r, n, CB, BD, DC.
Chú ý: Ta có thể bắt đầu vẽ từ đỉnh khác và có thể thay đổi thứ tự các cạnh (đường cong) trong khi vẽ miễn là cách vẽ đó thỏa mãn yêu cầu bài toán.
Khám phá 2
1. Nội dung câu hỏi
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?
2. Phương pháp giải
- Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.
- Bậc của một đỉnh A trong đồ thị G là số cạnh của đồ thị nhận đỉnh A làm đầu mút, kí hiệu là \(d(A)\)
- Đỉnh có bậc là số chẵn gọi là đỉnh bậc chẵn, đỉnh có bậc là một số lẻ là đỉnh bậc lẻ.
3. Lời giải chi tiết
a) Một chu trình Euler của đồ thị G là: AB, a, b, BC, CD, DE, EA.
Ta có d(A) = 2; d(B) = 4; d(C) = 2; d(D) = 2; d(E) = 4.
Vậy đồ thị đã cho không có đỉnh nào là đỉnh bậc lẻ.
b) Đồ thị S không có chu trình Euler vì nếu một đường đi bắt đầu và kết thúc tại cùng một đỉnh thì cạnh CD bắt buộc phải đi qua ít nhất hai lần; nếu một đường đi bắt đầu tại đỉnh này và kết thúc tại đỉnh kia thì không được gọi là chu trình.
Tương tự như vậy, đồ thị T không có chu trình Euler.
Đồ thị S có: d(A) = 2; d(B) = 2; d(C) = 3; d(D) = 1.Suy ra đồ thị S có hai đỉnh bậc lẻ là C, D.
Đồ thị T có: d(A) = 3; d(B) = 2; d(C) = 3; d(D) = 2.Suy ra đồ thị T có hai đỉnh bậc lẻ là A, C.
Vậy cả hai đồ thị S và T đều có đỉnh bậc lẻ.
Khám phá 3
1. Nội dung câu hỏi
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ẻ?
2. Phương pháp giải
- Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.
- Đỉnh có bậc là số chẵn gọi là đỉnh bậc chẵn, đỉnh có bậc là một số lẻ là đỉnh bậc lẻ.
3. Lời giải chi tiết
Một đường đi Euler (từ A đến D) trên đồ thị G là: ACBDAD.
Một đường đi Euler (từ E đến F) trên đồ thị H là: EABFCDEF.
Đồ thị G có: d(A) = 3; d(B) = 2; d(C) = 2; d(D) = 3.Suy ra đồ thị G có hai đỉnh bậc lẻ là A, D.
Đồ thị H có: d(A) = 2; d(B) = 2; d(C) = 2; d(D) = 2; d(E) = 3; d(F) = 3.Suy ra đồ thị H có hai đỉnh bậc lẻ là E, F.
Vậy đồ thị G có 2 đỉnh bậc lẻ, đồ thị H có 2 đỉnh bậc lẻ.
Thực hành 1
1. Nội dung câu hỏi
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.
2. Phương pháp giải
Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.
3. Lời giải chi tiết
a) Đồ thị G:
Ta có d(A) = d(B) = d(C) = d(D) = d(E) = 4.
Vậy đồ thị G có chu trình Euler vì các đỉnh của đồ thị G đều có bậc chẵn.
Chẳng hạn, bắt đầu từ đỉnh A, ta có thể đi theo chu trình Euler: ABECAEDCBDA.
b) Đồ thị H:
Ta có d(A) = d(D) = 4; d(B) = d(C) = 3; d(E) = 2.
Vậy đồ thị H không có chu trình Euler vì hai đỉnh B, C có bậc lẻ.
Thực hành 2
1. Nội dung câu hỏi
Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
2. Phương pháp giải
Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần.
Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.
3. Lời giải chi tiết
Ta có d(A) = d(B) = d(C) = d(D) = 4 và d(E) = d(F) = 3.
Suy ra đồ thị H có đúng 2 đỉnh bậc lẻ là E, F.
Do đó đồ thị H có đường đi Euler.
Chẳng hạn, bắt đầu từ đỉnh E, ta có thể đi theo đường đi Euler: EAabADcdDFCBEF.
Vận dụng 1
1. Nội dung câu hỏi
Hãy giải đáp câu hỏi của người dân Königsberg ở Hoạt động khởi động (còn gọi là bài toán Bảy cây cầu).
2. Phương pháp giải
Kiểm tra xem đồ chu trình có là chu trình Euler không.
Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.
3. Lời giải chi tiết
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.
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.
Bài 19: Carboxylic acid
Bài 12: Tiết 2: Thực hành: Tìm hiểu về dân cư Ô-xtrây-li-a - Tập bản đồ Địa lí 11
Tải 10 đề kiểm tra 45 phút (1 tiết) - Chương VI - Hóa học 11
Chủ đề 5. Hoạt động phát triển cộng đồng
Review Unit 7
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