Giải Chuyên đề Toán 11 Bài 1: Một vài yếu tố của lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton
I. Bài toán bảy cây cầu của Euler
II. Một số khái niệm cơ bản
Hoạt động 1 trang 36 Chuyên đề Toán 11: Đọc tên các đỉnh, các cạnh của đồ thị ở Hình 2c.
Lời giải:
Ở đồ thị Hình 2c có:
+ Các đỉnh là: A, B, C, D.
+ Các cạnh là: AB, AC, AD, BA, BD, CA, CD.
Lời giải:
Sử dụng điểm để biểu diễn vị trí thành phố, đoạn thẳng biểu diễn đường đi giữa hai thành phố, ta có mô hình như hình dưới đây.
Hoạt động 2 trang 36 Chuyên đề Toán lớp 11: Quan sát đồ thị ở Hình 4 và cho biết:
a) Với mỗi cặp đỉnh của đồ thị, có nhiều nhất bao nhiêu cạnh nối chúng;
b) Có hay không một đỉnh được nối với chính nó bởi một cạnh của đồ thị.
Lời giải:
Quan sát đồ thị Hình 4 ta thấy:
a) Với mỗi cặp đỉnh của đồ thị, có nhiều nhất một cạnh nối chúng.
b) Không có đỉnh nào được nối với chính nó bởi một cạnh của đồ thị.
Luyện tập 2 trang 37 Chuyên đề Toán lớp 11: Cho hai ví dụ về đồ thị đơn.
Lời giải:
Các đồ thị ở hai hình sau là đồ thị đơn.
Lời giải:
Các cạnh của đồ thị nhận đỉnh P làm đầu mút là PQ, PT, PS. Vậy có 3 cạnh của đồ thị nhận đỉnh P làm đầu mút.
Luyện tập 3 trang 37 chuyên đề Toán lớp 11: Có bao nhiêu đỉnh bậc lẻ trong đồ thị ở Hình 5a?
Lời giải:
Quan sát Hình 5a ta thấy d(A) = 2, d(B) = 3, d(C) = 2, d(D) = 2 và d(E) = 3 nên B, E là các đỉnh bậc lẻ. Vậy có hai đỉnh bậc lẻ trong đồ thị ở Hình 5a.
Hoạt động 4 trang 38 chuyên đề Toán lớp 11: Quan sát đồ thị Hình 7 và cho biết:
a) Tổng các bậc của năm đỉnh trong đồ thị đó;
b) Số cạnh của đồ thị đó;
c) Tổng các bậc của năm đỉnh trong đồ thị gấp bao nhiêu lần số cạnh của đồ thị đó.
Lời giải
Quan sát đồ thị Hình 7 ta thấy:
a) d(A) = 2, d(B) = 3, d(C) = 2, d(D) = 4, d(E) = 1.
Do đó, tổng các bậc của năm đỉnh trong đồ thị đó là 2 + 3 + 2 + 4 + 1 = 12.
b) Số cạnh của đồ thị đó là 6.
c) Ta có: 6 . 2 = 12 nên tổng các bậc của năm đỉnh trong đồ thị gấp hai lần số cạnh của đồ thị đó.
Luyện tập 4 trang 38 chuyên đề Toán lớp 11: Cho ví dụ về một đồ thị có số lẻ đỉnh bậc chẵn.
Lời giải:
Đồ thị trên có 5 đỉnh A, B, C, D, E với d(A) = d(B) = d(C) = d(D) = d(E) = 2.
Hoạt động 5 trang 38 chuyên đề Toán lớp 11: Quan sát đồ thị Hình 7 và cho biết:
a) Hai đỉnh A, B có được nối với nhau bằng một cạnh hay không;
b) Dãy các cạnh kế tiếp nhau AB, BC, CD, DE có đặc điểm gì.
Lời giải:
Quan sát đồ thị Hình 7 ta thấy:
a) Hai đỉnh A, B có được nối với nhau bằng một cạnh của đồ thị.
b) Dãy các cạnh kế tiếp nhau AB, BC, CD, DE có những tính chất sau: không có cạnh nào xuất hiện hai lần, đỉnh cuối của cạnh bất kì là đỉnh đầu của cạnh tiếp theo và không có đỉnh nào được đi qua hai lần. Dãy các cạnh kế tiếp nhau AB, BC, CD, DE được gọi là một đường đi từ đỉnh A đến đỉnh E.
Luyện tập 5 trang 39 chuyên đề Toán lớp 11: Trong đồ thị ở Hình 8, hãy tìm:
a) Một đường đi từ đỉnh A đến đỉnh F;
b) Một chu trình có đỉnh E là đỉnh đầu và đỉnh cuối.
Lời giải:
a) Một đường đi từ đỉnh A đến đỉnh F là ADE (hoặc có thể chọn ABCDF hoặc ABCEF).
b) Một chu trình có đỉnh E là đỉnh đầu và đỉnh cuối là ECDFE (hoặc có thể chọn EFDCE).
Lời giải:
Quan sát đồ thị Hình 8 ta thấy hai đỉnh bất kì của đồ thị đều được nối với nhau bằng một đường đi.
Lời giải
+) Ví dụ về đồ thị liên thông:
Ở hình trên, hai đỉnh bất kì của đồ thị đều được nối với nhau bằng một đường đi. Vậy đồ thị đó là đồ thị liên thông.
+) Ví dụ về đồ thị không liên thông:
Ở hình trên, mỗi đỉnh thuộc khối bên trên đều không thể nối được với mỗi đỉnh thuộc khối bên dưới bằng một đường đi. Vậy đồ thị đó là đồ thị không liên thông.
III. Đường đi Euler. Đường đi Hamilton
Hoạt động 7 trang 40 chuyên đề Toán lớp 11: Quan sát đồ thị ở Hình 10 và đường đi CABDCB, cho biết:
a) Đường đi trên có đi qua tất cả các cạnh của đồ thị hay không?
b) Đường đi trên đi qua mỗi cạnh bao nhiêu lần?
Lời giải:
Quan sát đồ thị ở Hình 10 ta thấy:
a) Đường đi CABDCB đi qua tất cả các cạnh của đồ thị.
b) Đường đi trên đi qua mỗi cạnh đúng một lần.
Luyện tập 7 trang 40 chuyên đề Toán lớp 11: Hãy chỉ ra hai đường đi Euler trong đồ thị ở Hình 11a.
Lời giải:
Hình 11a có đường đi Euler BEDBADCA và đường đi Euler BEDCADBA.
Lời giải:
Ta có d(A) = 3, d(B) = 3 nên đồ thị ở Hình 11a có đỉnh bậc lẻ, do đó theo định lí Euler, đồ thị ở Hình 11a không có chu trình Euler.
Lời giải:
Quan sát đường đi màu đỏ trên đồ thị ở Hình 13 ta thấy đường đi đó đi qua tất cả các đỉnh của đồ thị hay và mỗi đỉnh đi qua đúng một lần.
Lời giải:
Quan sát đồ thị Hình 15, ta thấy rằng hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị này là EACDB và ECDBA.
Lời giải:
Ta có: d(A) = 3, d(B) = 4, d(C) = 3, d(E) = 3, d(F) = 3. Đồ thị G ở Hình 17 gồm 5 đỉnh, mỗi đỉnh của đồ thị đều có bậc không nhỏ hơn . Do đó, theo định lí Dirac, đồ thị G có ít nhất một chu trình Hamilton.
Lời giải:
Đồ thị G ở Hình 19 gồm 6 đỉnh, trong đó các đỉnh A, D, E có bậc 4, các đỉnh B, C có bậc 5 và đỉnh F có bậc 2 nên tổng bậc của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 6. Do đó, theo định lí Ore, đồ thị G có ít nhất một chu trình Hamilton.
Bài tập
Lời giải:
Sử dụng điểm để biểu diễn vị trí thành phố, đoạn thẳng biểu diễn đường đi giữa hai thành phố, ta có mô hình như hình dưới đây.
Bài 2 trang 43 Chuyên đề Toán 11: Hãy vẽ một đồ thị có bốn đỉnh sao cho chỉ có đúng:
a) Hai đỉnh cùng có bậc là 1;
b) Hai đỉnh cùng có bậc là 2.
Lời giải:
a) Đồ thị chỉ có bốn đỉnh và chỉ có đúng hai đỉnh cùng có bậc là 1 (đỉnh A, đỉnh D).
b) Đồ thị chỉ có bốn đỉnh và chỉ có đúng hai đỉnh cùng có bậc là 2 (đỉnh B, đỉnh C).
Lời giải:
Ta có: d(A) = 4, d(B) = 2, d(C) = 4, d(D) = 2, d(E) = 4, d(F) = 2.
Vì đồ thị Hình 20 liên thông và không có đỉnh bậc lẻ nên theo định lí Euler thì đồ thị này có chu trình Euler.
Một chu trình Euler của đồ thị ở Hình 20 là AECFEDACBA.
Lời giải:
Ta có: d(A) = 3, d(B) = 3, d(C) = 4, d(D) = 4, d(E) = 2.
Vì đồ thị ở Hình 21 gồm có 5 đỉnh nên tổng bậc của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 5. Do đó, theo định lí Ore, đồ thị này có ít nhất một chu trình Hamilton.
Một chu trình Hamilton của đồ thị này là ABCEDA.
Lời giải:
Gọi 6 người bất kì là A, B, C, D, E, G.
Trong 6 người đó ta chọn ra một người A. Trong 5 người còn lại ta chia thành 2 nhóm:
- Nhóm 1 gồm những người quen A.
- Nhóm 2 gồm những người không quen A.
Có 5 người mà chỉ có 2 nhóm. Do đó, tồn tại ít nhất 3 người thuộc cùng một nhóm. Tức là tồn tại ít nhất 3 người quen A hoặc tồn tại ít nhất 3 người không quen A.
- Nếu tồn tại ít nhất 3 người quen A. Gọi 3 người đó là B, C, D:
+ Nếu trong 3 người B, C, D có 2 người nào đó quen nhau. Giả sử 2 người đó là B và C thì ta có 3 người A, B, C là 3 người đôi một quen nhau.
+ Nếu trong 3 người B, C, D không có 2 người nào đó quen nhau thì 3 người B, C, D là 3 người đôi một không quen nhau.
- Nếu tồn tại 3 người không quen A. Giả sử 3 người đó là D, E, G:
+ Trong 3 người D, E, G nếu có 2 người nào đó không quen nhau. Giả sử 2 người đó là D và E thì 3 người A, D, E là 3 người đôi một không quen nhau.
+ Nếu trong 3 người D, E, G không có 2 người nào không quen nhau thì 3 người D, E, G là 3 người đôi một quen nhau.
Vậy trong 6 người bất kì luôn tồn tại 3 người đôi một quen nhau hoặc 3 người đôi một không quen nhau (đpcm).
Xem thêm các bài giải Chuyên đề học tập Toán lớp 11 Cánh diều hay, chi tiết khác:
Bài 2: Một vài ứng dụng của lí thuyết đồ thị
