Câu hỏi:
13/07/2024 4,327
Quảng cáo
Trả lời:
Giải bởi Vietjack
– Gán nhãn cho M bằng 0 (tức là, nM = 0), các đỉnh khác bằng ∞. Khoanh tròn đỉnh M.
– Tại các đỉnh kề với M, gồm A, B, C, ta có:
⦁ nA = nM + wMA = 0 + 3 = 3. Vì 3 < ∞ nên ta đổi nhãn của A thành 3.
⦁ nB = nM + wMB = 0 + 4 = 4. Vì 4 < ∞ nên ta đổi nhãn của B thành 4.
⦁ nC = nM + wMC = 0 + 5 = 5. Vì 5 < ∞ nên ta đổi nhãn của C thành 5.
Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là A nên ta khoanh tròn đỉnh A (đỉnh gần M nhất, chỉ tính các điểm khác M).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với A gồm D, E, ta có:
⦁ nD = nA + wAD = 3 + 8 = 11. Vì 11 < ∞ nên ta đổi nhãn của D thành 11.
⦁ nE = nA + wAE = 3 + 10 = 13.Vì 13 < ∞ nên ta đổi nhãn của E thành 13.
Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là B nên ta khoanh tròn đỉnh B (đỉnh gần M thứ hai).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với B gồm D, F, ta có:
⦁ nD = nB + wBD = 4 + 8 = 12. Vì 12 > 11 (11 là nhãn hiện tại của D) nên ta giữ nguyên nhãn của D là 11.
⦁ nF = nB + wBF = 4 + 6 = 10. Vì 10 < ∞ nên ta đổi nhãn của F thành 10.
Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là C nên ta khoanh tròn đỉnh C (đỉnh gần M thứ ba).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với C gồm E, F, ta có:
⦁ nE = nC + wCE = 5 + 6 = 11. Vì 11 < 13 (13 là nhãn hiện tại của E) nên ta đổi nhãn của E thành 11.
⦁ nF = nC + wCF = 5 + 8 = 13. Vì 13 > 10 (10 là nhãn hiện tại của F) nên ta giữ nguyên nhãn của F là 10.
Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là F nên ta khoanh tròn đỉnh F (đỉnh gần M thứ tư).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với F chỉ có N, ta có:
nN = nF + wFN = 10 + 12 = 22. Vì 22 < ∞ nên ta đổi nhãn của N thành 22.
Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là D, E nên ta tùy ý khoanh tròn đỉnh E (đỉnh gần M thứ năm).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với E chỉ có N, ta có:
nN = nE + wEN = 11 + 7 = 18. Vì 18 < 22 (22 là nhãn hiện tại của N) nên ta đổi nhãn của N thành 18.
Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là D nên ta tùy ý khoanh tròn đỉnh D (đỉnh gần M thứ sáu).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với D chỉ còn N, ta có:
nN = nD + wDN = 11 + 9 = 20. Vì 20 > 18 (18 là nhãn hiện tại của N) nên ta giữ nguyên nhãn của N là 18.
Lúc này, ta thấy chỉ còn đỉnh N chưa được khoanh tròn nên ta khoanh tròn đỉnh N (đỉnh gần M thứ bảy).
– Nhìn lại các bước trên, ta thấy:
nN = 18 = nE + wEN = nC + wCE + wEN = nM + wMC + wCE + wEN
= wMC + wCE + wEN = lMCEN.
Vậy MCEN là đường đi ngắn nhất từ đỉnh M đến N, với độ dài bằng 18.
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
Sách thầy cô Vietjack biên soạn:
- Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
- Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
– Hình 7a:
Gọi tên các đỉnh của đồ thị ở Hình 7a như hình vẽ.
Ta có d(A) = d(B) = d(C) = d(D) = d(E) = d(F) = 2 và d(M) = d(N) = d(P) = d(Q) = d(R) = d(S) = 4.
Suy ra đồ thị ở Hình 7a có tất cả các đỉnh đều có bậc chẵn.
Do đó đồ thị ở Hình 7a có chu trình Euler.
Nói cách khác, ta có thể vẽ Hình 7a bằng một nét liền, không nhấc bút khỏi giấy, không vẽ lại đoạn đường nào hai lần.
Chẳng hạn, ta có cách vẽ như sau: NAMSERQCPNBPQDRSFMN.
– Hình 7b:
Gọi tên các đỉnh của đồ thị ở Hình 7b như hình vẽ.
Ta có:
⦁ d(M) = d(U) = 1;
⦁ d(A) = d(B) = d(C) = d(D) = d(E) = d(F) = d(G) = d(H) = d(I) = d(J) = d(K) = d(L) = 2;
⦁ d(N) = d(P) = d(Q) = d(R) = d(S) = d(T) = 4.
Suy ra đồ thị ở Hình 7b có đúng 2 đỉnh bậc lẻ là M và U.
Do đó đường đi Euler đi từ đỉnh M đến đỉnh U.
Nói cách khác, ta có thể vẽ Hình 7b bằng một nét liền, không nhấc bút khỏi giấy, không vẽ lại đoạn đường nào hai lần.
Chẳng hạn, ta có cách vẽ như sau: MNBCTDANPFGSHEPQJKRLIQRSTU.
– Hình 7c:
Gọi tên các đỉnh của đồ thị ở Hình 7b như hình vẽ.
Ta có:
⦁ d(E) = 1;
⦁ d(A) = d(B) = d(G) = 4;
⦁ d(F) = d(C) = d(D) = 3.
Suy ra đồ thị ở Hình 7c có 4 đỉnh bậc lẻ.
Do đó đồ thị ở Hình 7c không có đường đi Euler và cũng không có chu trình Euler.
Nói cách khác, ta không thể vẽ Hình 7c bằng một nét liền, không nhấc bút khỏi giấy, không vẽ lại đoạn đường nào hai lần.
Lời giải
Đáp án đúng là: C
Ta có d(A) = d(B) = d(C) = 2 và d(E) = d(F) = 3.
Suy ra đồ thị ở Hình 2 có đúng hai đỉnh bậc lẻ là đỉnh E và đỉnh F.
Do đó đồ thị ở Hình 2 có đường đi Euler xuất phát từ đỉnh E đến đỉnh F (hoặc từ đỉnh F đến đỉnh E) nhưng không có chu trình Euler.
Vậy ta chọn phương án C.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
10 Bài tập Nhận biết góc phẳng của góc nhị diện và tính góc phẳng nhị diện (có lời giải)
-
Bài tập Hình học không gian lớp 11 cơ bản, nâng cao có lời giải (P11)
-
Bài tập Xác suất ôn thi THPT Quốc gia có lời giải (P1)
-
Bài tập Lượng giác lớp 11 cơ bản, nâng cao có lời giải (P1)
-
12 câu Trắc nghiệm Toán 11 Kết nối tri thức Giá trị lượng giác của góc lượng giác có đáp án
-
38 câu trắc nghiệm Toán 11 Kết nối tri thức Lôgarit có đáp án
-
10 Bài tập Biểu diễn góc lượng giác trên đường tròn lượng giác (có lời giải)
-
33 câu trắc nghiệm Toán 11 Kết nối tri thức Bài 29: Công thức cộng xác suất có đáp án