Giải chi tiết chuyên đề Toán 11 kết nối mới bài 8 Một vài khái niệm cơ bản
Giải bài 8 Một vài khái niệm cơ bản sách chuyên đề Toán 11 kết nối. Phần đáp án chuẩn, hướng dẫn giải chi tiết cho từng bài tập có trong chương trình học của sách giáo khoa. Hi vọng, các em học sinh hiểu và nắm vững kiến thức bài học.
MỞ ĐẦU
Trước khi vào một hội nghị, các đại biểu bắt tay nhau (hai người bắt tay nhau nhiều nhất 1 lần). Có một đại biểu không bắt tay ai hết và thấy rằng có 4 người bắt tay 4 lần, 5 người bắt tay 5 lần và 6 người bắt tay 6 lần. Nếu hội nghị có đúng 16 đại biểu thì ông ta đã đếm nhầm. Vì sao có thể kết luận như vậy?
Hướng dẫn trả lời:
Vẽ một đồ thị với 16 đỉnh tương ứng với 16 đại biểu tham dự hội nghị.
Nếu hai đại biểu nào bắt tay nhau thì nối hai đỉnh tương ứng bằng một cạnh.
Theo đề bài, ta có một đồ thị 16 đỉnh, trong đó có 1 đỉnh bậc 0; 4 đỉnh bậc 4; 5 đỉnh bậc 5 và 6 đỉnh bậc 6.
Ta có 5 đỉnh bậc 5 mà theo hệ quả của định lí bắt tay: số đỉnh bậc lẻ của mọi đồ thị là một số chẵn.
Do đó mâu thuẫn với hệ quả. Suy ra đại biểu đó đã đếm sai.
1. ĐỒ THỊ
a) Khái niệm đồ thị
Hoạt động 1: Nhận biết khái niệm đồ thị
Có bốn bạn học sinh khối 11 là An, Bình, Cường và Dung, trong đó: An là bạn của Bình và Cường, nhưng không là bạn của Dung; Dung là bạn của Cường, nhưng không là bạn của Bình; Bình là bạn của Cường.
a) Hãy biểu diễn mỗi bạn An, Bình, Cường, Dung bằng một điểm trên mặt phẳng và dùng chữ cái đầu (in hoa) trong tên của họ để đặt tên cho các điểm này.
b) Nếu hai người là bạn của nhau, hãy nối các điểm biểu diễn tương ứng bằng một đoạn thẳng (hay đoạn đường cong).
c) Từ hình vẽ thu được ở HĐ1b, hãy cho biết: ai có nhiều bạn nhất và ai có ít bạn nhất?
Hướng dẫn trả lời:
a) + b)
c) Cường có nhiều bạn nhất; Dung có ít bạn nhất.
Luyện tập 1: Bảng F của giải vô địch bóng đá thế giới World Cup 2018 gồm bốn đội: Đức, Hàn Quốc, Mexico và Thụy Điển. Biểu diễn các đội này bằng các điểm phân biệt kí hiệu lần lượt là D, H, M, T (vẽ sao cho không có ba điểm nào thẳng hàng để dễ quan sát) và nếu hai đội nào đấu với nhau thì ta nối hai điểm tương ứng bằng một đoạn thẳng, ta sẽ được một đồ thị G.
Viết tập hợp các đỉnh và tập hợp các cạnh của đồ thị G.
Hướng dẫn trả lời:
Tập hợp các đỉnh của đồ thị G là: V(G) = {D, H, M, T}
Tập hợp các cạnh của đồ thị G là: E(G) = {DH, DM, DT, HM, HT, MT}
b) Đơn đồ thị và đa đồ thị
Hoạt động 2: Nhận biết khái niệm đơn đồ thị
Xét đồ thị cho trong Hình 2.2.
a) Đồ thị trên có khuyên không?
b) Có hai đỉnh nào của đồ thị được nối với nhau bằng nhiều hơn một cạnh không?
Hướng dẫn trả lời:
a) Đồ thị không có khuyên.
b) Không có hai đỉnh nào của đồ thị được nối với nhau bằng nhiều hơn một cạnh.
Luyện tập 2: Vẽ đồ thị G với các đỉnh và các cạnh như sau:
V(G) = {U, W, X, Z} và E(G) = {UW, WX, WZ, XZ}.
G có phải là một đơn đồ thị không?
Hướng dẫn trả lời:
Đồ thị G không có khuyên và hai đỉnh chỉ được nối bằng nhiều nhất một cạnh nên là đơn đồ thị.
c) Đồ thị đầy đủ
Hoạt động 3: Nhận biết đồ thị đầy đủ
Xét đồ thị nhận được trong Luyện tập 1. Có cặp đỉnh nào của đồ thị này mà không có cạnh nào nối chúng không?
Hướng dẫn trả lời:
Đồ thị Luyện tập 1:
Không có cặp đỉnh nào của đồ thị này mà không có cạnh nào nối chúng.
Luyện tập 3: Vẽ các đồ thị đầy đủ có 5 đỉnh, có 6 đỉnh.
Hướng dẫn trả lời:
Đồ thị đầy đủ có 5 đỉnh:
Đồ thị đầy đủ có 6 đỉnh:
2. BẬC CỦA ĐỈNH
Hoạt động 4: Nhận biết bậc của đỉnh
Cho đồ thị như Hình 2.5. Tìm các đỉnh là đầu mút của: 0 cạnh; 1 cạnh; 2 cạnh; 3 cạnh.
Hướng dẫn trả lời:
Đỉnh là đầu mút của 0 cạnh: G
Đỉnh là đầu mút của 1 cạnh: F
Đỉnh là đầu mút của 2 cạnh: A, B
Đỉnh là đầu mút của 3 cạnh: C, D, E
Luyện tập 4: Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 18 cạnh mà các đỉnh đều có bậc 3 hoặc 4.
Hướng dẫn trả lời:
Gọi x (x > 0) là số đỉnh bậc 3 của đồ thị. Khi đó số đỉnh bậc 4 của đồ thị là 12 - x. Tổng tất cả các bậc của đỉnh là 3x + 4(12 - x).
Vì đồ thị có 28 cạnh nên ta có: 3x + 4(12 - x) = 2.28 ⇔ x = - 8 (không thỏa mãn x > 0).
Vậy không có đơn đồ thị với 12 đỉnh và 18 cạnh mà các đỉnh đều có bậc 3 hoặc 4.
3. ĐƯỜNG ĐI VÀ CHU TRÌNH
a) Khái niệm đường đi và chu trình
Hoạt động 5: Nhận biết khái niệm đường đi và chu trình
Cho đồ thị như Hình 2.7. Bằng cách đi dọc theo các cạnh, với điều kiện không đi qua cạnh nào quá một lần (có thể có cạnh không cần đi qua), hãy chỉ ra các cách để:
a) Đi từ đỉnh A đến đỉnh E.
b) Đi từ đỉnh A và lại quay về đỉnh A.
Hướng dẫn trả lời:
a) Các cách để đi từ đỉnh A đến đỉnh E: ADE; ABDE; ABCDE; ADCBDE; ADBCDE.
b) Các cách để đi từ đỉnh A và lại quay về đỉnh A: ABCDA, ADCBA.
Luyện tập 5: Cho đồ thị đầy đủ có 5 đỉnh như Hình 2.9. Tìm những chu trình sơ cấp xuất phát từ đỉnh A và có: độ dài 4; độ dài 5.
Hướng dẫn trả lời:
Những chu trình sơ cấp xuất phát từ đỉnh A và có độ dài 4: ABCEA, ABECA, ABCDA, ABDCA, ABDEA, ABEDA; ACBDA, ACBEA, ACDBA, ACDEA, ACEBA, ACEDA; ADBCA, ADBEA, ADCBA, ADCEA, ADEBA, ADECA; AEBCA, AEBDA, AECBA, AECDA, AEDBA, AEDCA.
Những chu trình sơ cấp xuất phát từ đỉnh A và có độ dài 5: ABCDEA, ABCEDA, ABDCEA, ABDECA, ABECDA, ABEDCA; ACBDEA, ACBEDA, ACDBEA, ACDEBA, ACEBDA, ACEDBA; ADBCEA, ADBECA, ADCBEA, ADCEBA, ADEBCA, ADECBA; AEBCDA, AEBDCA, AECBDA, AECDBA, AEDBCA, AEDCBA.
b) Tính liên thông của đồ thị
Hoạt động 6: Nhận biết tính liên thông của đồ thị
Trong đồ thị ở Hình 2.10, hãy:
a) Tìm một đường đi từ đỉnh A đến đỉnh E.
b) Có tồn tại một đường đi từ đỉnh A đến đỉnh F hay không?
Hướng dẫn trả lời:
a) Một đường đi từ đỉnh A đến đỉnh E là: ABCDE.
b) Không tồn tại đường đi nào từ đỉnh A đến đỉnh F vì F là đỉnh cô lập.
Luyện tập 6: Chứng minh đồ thị ở Hình 2.12 là liên thông. Hãy chỉ ra một đường đi nối đỉnh 1 và đỉnh 6.
Hướng dẫn trả lời:
Đồ thị Hình 2.12 có 7 đỉnh, mỗi đỉnh có bậc là 4, do đó đồ thị là liên thông.
Một đường đi nối đỉnh 1 và đỉnh 6: 123456.
BÀI TẬP
2.1. Vẽ hình biểu diễn của đồ thị G với tập đỉnh V(G) = {1; 2; 3; 4; 5} và tập cạnh E(G) = {12; 14; 23; 25; 34; 35}. Đồ thị G có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?
Hướng dẫn trả lời:
Đồ thị G không có khuyên, trong đó hai đỉnh được nối bằng nhiều nhất một cạnh nên là một đơn đồ thị.
Đồ thị G có cặp đỉnh 1 và 5; 1 và 3; 2 và 4; 4 và 5 không được nối bằng 1 cạnh nên không là đồ thị đầy đủ.
2.2. Hãy vẽ một đồ thị có 4 đỉnh và:
a) có đúng hai đỉnh cùng bậc và bậc là 1;
b) có đúng hai đỉnh cùng bậc và bậc là 2.
Hướng dẫn trả lời:
a) Đồ thị trên có hai đỉnh A và D cùng có bậc là 1.
b) Đồ thị trên có hai đỉnh B và C cùng có bậc là 2.
2.3. Một đồ thị con của đồ thị G là một đồ thị mà mọi đỉnh của nó đều là đỉnh của G và mọi cạnh của nó cũng là cạnh của G.
Những đồ thị nào trong các hình a), b), c) dưới đây là đồ thị con của đồ thị G?
Hướng dẫn trả lời:
Cả ba đồ thị a), b), c) không là đồ thị con của đồ thị G.
2.4. Chứng minh rằng một đồ thị đầy đủ có n đỉnh thì có $\frac{n(n-1)}{2}$ cạnh.
Hướng dẫn trả lời:
Gọi các đỉnh của đồ thị lần lượt là $A_{1}$,$A_{2}$,$A_{3}$,...,$A_{n}$
Đỉnh $A_{1}$ nối với (n - 1) đỉnh còn lại nên từ đỉnh $A_{1}$ đồ thị có (n - 1) cạnh.
Tương tự, từ đỉnh $A_{2}$ đồ thị có (n - 2) cạnh.
...
Từ đỉnh An đồ thị có n - n cạnh (vì các đỉnh $A_{1}$,$A_{2}$,$A_{3}$,...,$A_{n}$ đều nối với $A_{n}$ rồi).
Do đó, tổng tất cả các cạnh của đồ thị là: $n-1+n-2+n-3+...+n-n=n^{2}-(1+2+3+...+n)$ (1)
Dễ dàng chứng minh được đẳng thức: $1+2+3+...+n=\frac{n(n+1)}{2} (n \in \mathbb{N} ^{*})$ (2)
Từ (1)(2) suy ra: $n^{2}-\frac{n(n+1)}{2}=\frac{n^{2}-n}{2}=\frac{n(n-1)}{2}$ (đcpcm)
2.5. Chứng minh rằng không tồn tại đồ thị với các đỉnh có bậc là 2, 3, 3, 4, 4 và 5.
Hướng dẫn trả lời:
Tổng tất cả các bậc của các đỉnh là: 2 + 3 + 3 + 4 + 4 + 5 = 21
Theo định lí bắt tay, tổng tất cả các bậc của các đỉnh là một số chẵn.
Do đó mâu thuẫn với định lí bắt tay.
Suy ra: Không tồn tại đồ thị với các đỉnh có bậc là 2, 3, 3, 4, 4 và 5.
2.6. Cho đồ thị G như Hình 2.14.
a) Tìm một đường đi từ đỉnh A đến đỉnh B.
b) G có liên thông không?
c) Trong G có chu trình sơ cấp nào không?
Hướng dẫn trả lời:
a) Một đường đi từ đỉnh A đến đỉnh B: ADGB.
b) Đồ thị G có liên thông vì mỗi cặp đỉnh của đồ thị đều có đường đi.
c) Trong G có chu trình sơ cấp. Chẳng hạn chu trình AEHCFBGDA.