Giải bài tập Toán 11 Chuyên đề 2. Làm quen với một vài yếu tố của lý thuyết đồ thị | Cánh Diều
Hướng dẫn giải chi tiết từng bước bài tập Toán 11 Chuyên đề 2. Làm quen với một vài yếu tố của lý thuyết đồ thị | Chuyên đề học tập Cánh diều
Giải bài tập Bài 1. Một vài yếu tố của Lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton
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. Hoạt động 1 trang 36 Chuyên đề Toán 11
Luyện tập 1 trang 36 Chuyên đề Toán lớp 11
Có năm thành phố A, B, C, D, E sao cho hai thành phố bất kì trong chúng đều có đúng một đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó. Luyện tập 1 trang 36 Chuyên đề Toán lớp 11
Hoạt động 2 trang 36 Chuyên đề Toán lớp 11
Quan sát đồ thị ở Hình 4 và cho biết. Với mỗi cặp đỉnh của đồ thị, có nhiều nhất bao nhiêu cạnh nối chúng. Có hay không một đỉnh được nối với chính nó bởi một cạnh của đồ thị. Hoạt động 2 trang 36 Chuyên đề Toán lớp 11
Luyện tập 2 trang 37 Chuyên đề Toán lớp 11
Cho hai ví dụ về đồ thị đơn. Luyện tập 2 trang 37 Chuyên đề Toán lớp 11
Hoạt động 3 trang 37 Chuyên đề Toán lớp 11
Quan sát đồ thị ở Hình 6 và đếm số cạnh của đồ thị nhận đỉnh P làm đầu mút. Hoạt động 3 trang 37 Chuyên đề Toán lớp 11
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? Luyện tập 3 trang 37 chuyên đề Toán lớp 11
Hoạt động 4 trang 38 chuyên đề Toán lớp 11
Quan sát đồ thị Hình 7 và cho biết. Tổng các bậc của năm đỉnh trong đồ thị đó. Số cạnh của đồ thị đó. 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ị đó. Hoạt động 4 trang 38 chuyên đề Toán lớp 11
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. Luyện tập 4 trang 38 chuyên đề Toán lớp 11
Hoạt động 5 trang 38 chuyên đề Toán lớp 11
Quan sát đồ thị Hình 7 và cho biết. Hai đỉnh A, B có được nối với nhau bằng một cạnh hay không. Dãy các cạnh kế tiếp nhau AB, BC, CD, DE có đặc điểm gì. Hoạt động 5 trang 38 chuyên đề Toán lớp 11
Luyện tập 5 trang 39 chuyên đề Toán lớp 11
Trong đồ thị ở Hình 8, hãy tìm. Một đường đi từ đỉnh A đến đỉnh F. Một chu trình có đỉnh E là đỉnh đầu và đỉnh cuối. Luyện tập 5 trang 39 chuyên đề Toán lớp 11
Hoạt động 6 trang 39 chuyên đề Toán lớp 11
Quan sát đồ thị Hình 8 và cho biết hai đỉnh bất kì của đồ thị có được nối với nhau bằng một đường đi hay không? Hoạt động 6 trang 39 chuyên đề Toán lớp 11
Luyện tập 6 trang 39 chuyên đề Toán lớp 11
Cho ví dụ về một đồ thị liên thông và một đồ thị không liên thông. Luyện tập 6 trang 39 chuyên đề Toán lớp 11
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. Đường đi trên có đi qua tất cả các cạnh của đồ thị hay không? Đường đi trên đi qua mỗi cạnh bao nhiêu lần? Hoạt động 7 trang 40 chuyên đề Toán lớp 11
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. Luyện tập 7 trang 40 chuyên đề Toán lớp 11
Luyện tập 8 trang 41 chuyên đề Toán lớp 11
Chứng minh rằng đồ thị ở Hình 11a không có chu trình Euler. Luyện tập 8 trang 41 chuyên đề Toán lớp 11
Hoạt động 8 trang 41 chuyên đề Toán lớp 11
Quan sát đường đi màu đỏ trên đồ thị ở Hình 13 và cho biết đường đi đó có đi qua tất cả các đỉnh của đồ thị hay không và mỗi đỉnh đi qua bao nhiêu lần. Hoạt động 8 trang 41 chuyên đề Toán lớp 11
Luyện tập 9 trang 42 chuyên đề Toán lớp 11
Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15. Luyện tập 9 trang 42 chuyên đề Toán lớp 11
Luyện tập 10 trang 42 chuyên đề Toán lớp 11
Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton. Luyện tập 10 trang 42 chuyên đề Toán lớp 11
Luyện tập 11 trang 43 chuyên đề Toán lớp 11
Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton. Luyện tập 11 trang 43 chuyên đề Toán lớp 11
Bài 1 trang 43 Chuyên đề Toán 11
Có sáu thành phố A, B, C, D, E, G sao cho hai thành phố bất kì trong chúng đều có đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó. Bài 1 trang 43 Chuyên đề Toán 11
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. Hai đỉnh cùng có bậc là 1. Hai đỉnh cùng có bậc là 2. Bài 2 trang 43 Chuyên đề Toán 11
Bài 3 trang 43 Chuyên đề Toán 11
Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Euler (nếu có) của đồ thị ở Hình 20. Bài 3 trang 43 Chuyên đề Toán 11
Bài 4 trang 43 Chuyên đề Toán 11
Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Hamilton (nếu có) của đồ thị ở Hình 21. Bài 4 trang 43 Chuyên đề Toán 11
Bài 5 trang 43 Chuyên đề Toán 11
Một cuộc họp có 6 người tham dự. Hai người bất kì trong họ hoặc quen nhau hoặc không quen nhau. Chứng minh rằng có 3 người trong 6 người đó đôi một quen nhau hoặc đôi một không quen nhau. Bài 5 trang 43 Chuyên đề Toán 11
Giải bài tập Bài 2. Một vài ứng dụng của lí thuyết đồ thị
Khởi động trang 44 Chuyên đề Toán 11
Như chúng ta đã biết, Lí thuyết đồ thị ra đời trong quá trình khái quát, mô phỏng những vấn đề của khoa học và thực tiễn thành những mô hình toán học. Khởi động trang 44 Chuyên đề Toán 11
Hoạt động 1 trang 44 Chuyên đề Toán 11
Giả sử ba địa điểm A, B, C được nối với nhau theo những con đường AB, BC, CA với độ dài lần lượt là 15 km, 20 km, 16 km. Sử dụng đồ thị để mô tả tình huống đó. Hoạt động 1 trang 44 Chuyên đề Toán 11
Luyện tập 1 trang 44 Chuyên đề Toán 11
Hãy cho ví dụ về đồ thị có trọng số. Luyện tập 1 trang 44 Chuyên đề Toán 11
Hoạt động 2 trang 44 Chuyên đề Toán 11
Giả sử có sáu địa điểm A, B, C, D, E, F được nối với nhau theo những con đường với độ dài (đơn vị: kilômét) được mô tả bằng đồ thị có trọng số ở Hình 24. Người giao hàng cần đi giao hàng tại sáu địa điểm trên. Hoạt động 2 trang 44 Chuyên đề Toán 11
Luyện tập 2 trang 46 Chuyên đề Toán 11
Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2. Luyện tập 2 trang 46 Chuyên đề Toán 11
Luyện tập 3 trang 47 Chuyên đề Toán 11
Hexane C6H14 có năm đồng phân. Vẽ đồ thị tương ứng với năm đồng phân đó. Luyện tập 3 trang 47 Chuyên đề Toán 11
Bài 1 trang 49 Chuyên đề Toán 11
Hình 31 biểu diễn mạng lưới máy chủ và tốc độ truyền dữ liệu (đơn vị: Megabit/ giây, kí hiệu là Mbps) giữa một số thành phố. Vẽ một đồ thị sử dụng điểm, đường để biểu diễn mạng lưới đó. Bài 1 trang 49 Chuyên đề Toán 11
Bài 2 trang 49 Chuyên đề Toán 11
Có bốn địa điểm với độ dài quãng đường giữa các địa điểm (đơn vị: kilômét) mô tả trong Hình 32. Bài 2 trang 49 Chuyên đề Toán 11
Bài 3 trang 49 Chuyên đề Toán 11
Giả sử chi phí di chuyển giữa các địa điểm được mô tả ở Hình 33 (đơn vị: nghìn đồng). Ta nên chọn theo chu trình nào đi qua tất cả các địa điểm để tổng chi phí di chuyển là thấp nhất? Bài 3 trang 49 Chuyên đề Toán 11
Bài 4 trang 49 Chuyên đề Toán 11
Sử dụng thuật toán láng giềng gần nhất, hãy giải bài toán người giao hàng đối với đồ thị ở Hình 34, số ghi trên mỗi cạnh của đồ thị mô tả độ dài quãng đường giữa các địa điểm (đơn vị: kilômét). Bài 4 trang 49 Chuyên đề Toán 11
Bài 5 trang 49 Chuyên đề Toán 11
Một nhân viên của bảo tàng nghệ thuật đang có kế hoạch giới thiệu nội dung cuộc triển lãm của bảo tàng đến ba trường học trong khu vực. Người đó muốn đến từng trường và quay trở lại bảo tàng sau khi thăm cả ba trường. Bài 5 trang 49 Chuyên đề Toán 11