Giải Chuyên đề Toán 11 Bài tập cuối chuyên đề 2
Bài 1 trang 67 Chuyên đề Toán 11: Số đỉnh, số cạnh của đồ thị ở Hình 1 lần lượt là
A. 3 đỉnh, 8 cạnh.
B. 4 đỉnh, 8 cạnh.
C. 3 đỉnh, 9 cạnh.
D. 4 đỉnh, 9 cạnh.
Lời giải:
Đáp án đúng là: D
Gọi các đỉnh của đồ thị ở Hình 1 là: A, B, C, D (hình vẽ). Do đó đồ thị có 4 đỉnh.
Các cạnh của đồ thị ở Hình 1 là: AB, BC, CA, a, b, c, d, g, h. Do đó đồ thị có 9 cạnh.
Vậy ta chọn phương án D.
Bài 2 trang 67 Chuyên đề Toán 11: Tổng tất cả bậc của các đỉnh của đồ thị ở Hình 1 là
A. 20.
B. 18.
C. 12.
D. 9.
Lời giải:
Đáp án đúng là: B
Gọi các đỉnh của đồ thị ở Hình 1 là: A, B, C, D (hình vẽ).
Ta có d(A) = d(B) = d(C) = 4 và d(D) = 6.
Tổng tất cả bậc của các đỉnh của đồ thị ở Hình 1 là: 4 + 4 + 4 + 6 = 18.
Vậy ta chọn phương án B.
Bài 3 trang 67 Chuyên đề Toán 11: Đồ thị ở Hình 2 có bao nhiêu đỉnh bậc lẻ?
A. 6.
B. 7.
C. 8.
D. 9.
Lời giải:
Đáp án đúng là: C
Gọi tên các đỉnh của đồ thị ở Hình 2 như hình vẽ.
Ta có:
⦁ d(A) = d(B) = d(C) = d(D) = 2;
⦁d(E) = d(F) = d(G) = d(H) = d(I) = d(J) = d(K) = d(L) = 3;
⦁ d(M) = d(N) = d(P) = 4.
Suy ra các đỉnh E, F, G, H, I, J, K, L có bậc lẻ.
Vậy đồ thị ở Hình 2 có 8 đỉnh bậc lẻ.
Do đó ta chọn phương án C.
Bài 4 trang 67 Chuyên đề Toán 11: Cho đồ thị ở Hình 3, phát biểu nào sau đây đúng?
A. Đồ thị có chu trình Euler.
B. Đồ thị đường đi Euler xuất phát từ đỉnh A.
C. Đồ thị đường đi Euler xuất phát từ đỉnh E.
D. Đồ thị không có đường đi Euler.
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.
A. AEC.
B. AEFC.
C. AC.
D. AFC.
Lời giải:
Đáp án đúng là: B
– Gán nhãn cho A bằng 0 (tức là, nA = 0), các đỉnh khác bằng ∞. Khoanh tròn đỉnh A.
– Tại các đỉnh kề với A, gồm E, F, B, ta có:
⦁ nE = nA + wAE = 0 + 2 = 2.Vì 2 < ∞ nên ta đổi nhãn của E thành 2.
⦁ nF = nA + wAF = 0 + 4 = 4.Vì 4 < ∞ nên ta đổi nhãn của F thành 4.
⦁ nB = nA + wAB = 0 + 2,5 = 2,5.Vì 2,5 < ∞ nên ta đổi nhãn của B thành 2,5.
Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là E nên ta khoanh tròn đỉnh E (đỉnh gần A nhất, chỉ tính các đỉnh khác A).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh E gồm D, C, F, ta có:
⦁ nD = nE + wED = 2 + 3 = 5.Vì 5 < ∞ nên ta đổi nhãn của D thành 5.
⦁ nC = nE + wEC = 2 + 5 = 7.Vì 7 < ∞ nên ta đổi nhãn của C thành 7.
⦁ nF = nE + wEF = 2 + 1 = 3.Vì 3 < 4 (4 là nhãn hiện tại của F) nên ta đổi nhãn của F thành 3.
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 A thứ hai).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh B chỉ có F, ta có:
nF = nB + wBF = 2,5 + 1,5 = 4.Vì 4 > 3 (3 là nhãn hiện tại của F) nên ta giữ nguyên nhãn của F là 3.
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 A thứ ba).
– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh F chỉ có C, ta có:
nC = nF + wFC = 3 + 2 = 5.Vì 5 < 7 (7 là nhãn hiện tại của C) 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à C, D (đều có nhãn là 5), nhưng do ta cần tìm đường đi ngắn nhất từ A đến C nên ta ưu tiên khoanh tròn đỉnh C (đỉnh gần A thứ tư).
– Nhìn lại các bước trên, ta thấy:
nC = 5 = nF + wFC
= nE + wEF + wFC
= nA + wAE + wEF + wFC
= wAE + wEF + wFC
= lAEFC.
Vậy AEFC là đường đi ngắn nhất từ A đến C, với độ dài bằng 5.
Do đó ta chọn phương án B.
Lời giải:
Trong tập hợp số V, các cặp số là bội của 3 là:
• (1 và 2); (1 và 5);
• (2 và 4); (2 và 7);
• (3 và 6);
• (4 và 5);
• (5 và 7).
Ta vẽ đồ thị G có 7 đỉnh A1; A2; A3; A4; A5; A6; A7 biểu diễn bảy số trong tập hợp số V.
Hai đỉnh biểu diễn hai số m và n được nối bằng một cạnh nếu m + n là bội của 3.
Ta có đồ thị G như sau:
Lời giải
a) Đồ thị G:
Ta có d(A) = d(B) = d(C) = d(D) = 5.
Suy ra 4 đỉnh của đồ thị G đều có bậc lẻ.
Vậy đồ thị G không có chu trình Euler và cũng không có đường đi Euler.
b) Đồ thị H:
Ta có d(A) = d(C) = d(M) = d(P) = 3 và d(B) = d(N) = 2.
Suy ra đồ thị H có 4 đỉnh bậc lẻ.
Vậy đồ thị H không có chu trình Euler và cũng không có đường đi Euler.
Lời giải:
a) Đồ thị G:
Đồ thị G có các đỉnh A, B, I có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh AB, AD, BC, EI, FI.
Do đó ta có một chu trình Hamilton h của đồ thị G là: CBADEIFC.
b) Đồ thị H:
Đồ thị H có các đỉnh M, N, P có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh MA, MB, NA, NB, PA, PB.
Ta thấy chu trình Hamilton h (nếu có) đi qua ba cạnh MA, NA, PA nối với đỉnh A nên chu trình Hamilton h không tồn tại.
Đồ thị H có đường đi Hamilton, chẳng hạn MANBP.
Vậy đồ thị G không có chu trình Hamilton và cũng không có đường đi Hamilton; đồ thị H không có chu trình Hamilton và có đường đi Hamilton.
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:
– 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.
Xem thêm các bài giải Chuyên đề học tập Toán lớp 11 Chân trời sáng tạo hay, chi tiết khác:
Bài 2: Đường đi Euler và đường đi Hamilton
Bài 3: Bài toán tìm đường đi ngắn nhất
