{"event_info":{"picture":"https://img.loigiaihay.com/picture/event/2023/0804/-0_10.png","title":"Bài 10. Bài toán tìm đường đi tối ưu trong một vài trường hợp đơn giản Chuyên đề học tập Toán 11 kết nối tri thức","display_type":1,"cat_id":1572,"cat_title":"Chuyên đề học tập Toán 11 - Kết nối tri thức","alias":"bai-10-bai-toan-tim-duong-di-toi-uu-trong-mot-vai-truong-hop-don-gian-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"","content_box_above":"","type":"event","page_builder":"","item_id":32767,"item_type":2},"list_articles":[{"article_id":145629,"cat_id":1572,"publish_time":1691222340,"type_ex":0,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_93.png","title":"Giải mục 1 trang 46 Chuyên đề học tập Toán 11 - Kết nối tri thức","label":"Câu hỏi mục 1 trang 46","alias":"giai-muc-1-trang-46-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.","display_type":1,"article_type":1,"content":"<style>\r\n.method-close-icon{position: relative;float: right;top: 6px;transform: rotate(270deg);-ms-transform:rotate(270deg);-moz-transform:rotate(270deg);-webkit-transform:rotate(270deg);-o-transform:rotate(270deg);}\r\n.method-open-icon{position: relative;float: right;top: 6px;}\r\n</style>\r\n<p><strong style=\"font-size: 16px;\">Lời giải chi tiết</strong></p><p>a) Hai đường đi từ A đến F, chẳng hạn là ABEF và ACEF.</p>\r\n<p>Độ dài của đường đi ABEF là AB + BE + EF = 3 + 2 + 8 = 13.</p>\r\n<p> Độ dài của đường đi ACEF là AC + CE + EF = 1 + 5 + 8 = 14.</p>\r\n<p>Do đó, đường đi ABEF có độ dài ngắn hơn đường đi ACEF.</p>\r\n<p>b) I(B) và I(C) lần lượt là các khoảng cách ngắn nhất để đi từ A đến B và C.</p>\r\n<p>Ta có I(B) = AB = 3, I(C) = AC = 1.</p>"},{"article_id":145632,"cat_id":1572,"publish_time":1691222580,"type_ex":0,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_94.png","title":"Giải mục 2 trang 47, 48, 49 Chuyên đề học tập Toán 11 - Kết nối tri thức","label":"Câu hỏi mục 2 trang 47, 48, 49 ","alias":"giai-muc-2-trang-47-48-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.","display_type":1,"article_type":1,"content":"<style>\r\n.method-close-icon{position: relative;float: right;top: 6px;transform: rotate(270deg);-ms-transform:rotate(270deg);-moz-transform:rotate(270deg);-webkit-transform:rotate(270deg);-o-transform:rotate(270deg);}\r\n.method-open-icon{position: relative;float: right;top: 6px;}\r\n</style>\r\n<p><strong style=\"font-size: 16px;\">Lời giải chi tiết</strong></p><p>Đồ thị Hình 2.32 chỉ có hai đỉnh bậc lẻ là A và D nên ta có thể tìm được một đường đi Euler từ A đến D (đường đi này đi qua mỗi cạnh đúng một lần).</p>\r\n<p> Một đường đi Euler từ A đến D là AFEABEDBCD và tổng độ dài của nó là</p>\r\n<p>10 + 9 + 7 + 2 + 8 + 16 + 15 + 3 + 4 = 74.</p>\r\n<p>Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ D đến A theo thuật toán gắn nhãn vĩnh viễn.</p>\r\n<p>Đường đi ngắn nhất từ D đến A là DCBA và có độ dài là 4 + 3 + 2 = 9.</p>\r\n<p> Vậy một chu trình cần tìm là AFEABEDBCDCBA và có độ dài là 74 + 9 = 83.</p>"},{"article_id":145635,"cat_id":1572,"publish_time":1691222760,"type_ex":0,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_95.png","title":"Giải bài 2.15 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức","label":"Bài 2.15 trang 49 ","alias":"giai-bai-215-trang-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Tìm đường đi ngắn nhất từ A đến D trong đồ thị có trọng số trên Hình 2.33.","display_type":1,"article_type":1,"content":"<style>\r\n.method-close-icon{position: relative;float: right;top: 6px;transform: rotate(270deg);-ms-transform:rotate(270deg);-moz-transform:rotate(270deg);-webkit-transform:rotate(270deg);-o-transform:rotate(270deg);}\r\n.method-open-icon{position: relative;float: right;top: 6px;}\r\n</style>\r\n<p><strong style=\"font-size: 16px;\">Lời giải chi tiết</strong></p><p>Đầu tiên, ta gắn nhãn đỉnh A là I(A) = 0 và gắn cho ba đỉnh kề với A là B, F và D các nhãn tạm thời I(A) + 4, I(A) + 3 và I(A) + 20. Chọn số nhỏ nhất trong chúng và viết I(F) = 3. Đỉnh F bây giờ được gắn nhãn vĩnh viễn là 3.</p>\r\n<p> Tiếp theo, ta gắn cho các đỉnh kề với F là B, C và E các nhãn tạm thời I(F) + 6, I(F) + 5 và I(F) + 15 (B hiện có hai nhãn tạm thời là 4 và 9). Nhãn tạm thời nhỏ nhất trong các nhãn đã gán (ở B, C, E) hiện nay là 4 (tại B), nên ta viết I(B) = 4. Đỉnh B được gắn nhãn vĩnh viễn là 4.</p>\r\n<p>Bây giờ ta xét các đỉnh kề với B (mà chưa được gắn nhãn vĩnh viễn) là C và E. Ta gắn cho đỉnh C nhãn tạm thời là I(B) + 11 (hiện C có hai nhãn tạm thời là 8 và 15), gắn cho đỉnh E nhãn tạm thời là I(B) + 9 (E hiện có hai nhãn tạm thời là 18 và 13. Nhãn tạm thời nhỏ nhất bây giờ là 8 (tại C), do đó ta viết I(C) = 8.</p>\r\n<p>Bây giờ ta xét các đỉnh kề với C (mà chưa được gắn nhãn vĩnh viễn) là E và D. Ta gắn nhãn cho đỉnh E tạm thời là I(C) + 2 (hiện E có ba nhãn tạm thời là 18, 13 và 10), gắn cho đỉnh D nhãn tạm thời là I(C) + 10. Nhãn tạm thời nhỏ nhất bây giờ là 10 (tại E), do đó ta viết I(E) = 10.</p>\r\n<p>Xét đỉnh kề với E là D, ta gắn cho D nhãn tạm thời I(E) + 7 (hiện D có hai nhãn tạm thời là 18 và 17). Vậy đỉnh D sẽ được gắn nhãn vĩnh viễn là 17 hay I(D) = 17.</p>\r\n<p> Vì I(D) = 17 nên đường đi ngắn nhất từ A đến D có độ dài là 17.</p>\r\n<p style=\"text-align: center;\"> <img src=\"https://img.loigiaihay.com/picture/2023/0805/1691222955.png\"   /></p>\r\n<p>Để tìm một đường đi ngắn nhất từ A đến D như vậy, ta sẽ lần ngược từ điểm cuối D. Ta chỉ cần giới hạn ở việc xét những cạnh mà độ dài là hiệu của các nhãn gắn tại đầu các mút của nó, đó là DE, EC, CF và FA (do I(D) – I(E) = 17 = 10 = 7, I(E) – I(C) = 10 – 8 = 2, I(C) – I(F) = 8 – 3 = 5 và I(F) – I(A) = 3 – 0 = 3).</p>\r\n<p>Khi đó ta có thể kết luận, đường đi ngắn nhất từ A đến D phải đi qua các cạnh DE, EC, CF và FA.</p>\r\n<p> Vậy, đường đi ngắn nhất (trong trường hợp này là duy nhất) từ A đến D là</p>\r\n<p align=\"center\">\\(A \\to F \\to C \\to E \\to D.\\)</p>"},{"article_id":145637,"cat_id":1572,"publish_time":1691223060,"type_ex":0,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_97.png","title":"Giải bài 2.16 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức","label":"Bài 2.16 trang 49 ","alias":"giai-bai-216-trang-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Tìm đường đi ngắn nhất từ đỉnh S đến  mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.","display_type":1,"article_type":1,"content":"<style>\r\n.method-close-icon{position: relative;float: right;top: 6px;transform: rotate(270deg);-ms-transform:rotate(270deg);-moz-transform:rotate(270deg);-webkit-transform:rotate(270deg);-o-transform:rotate(270deg);}\r\n.method-open-icon{position: relative;float: right;top: 6px;}\r\n</style>\r\n<p><strong style=\"font-size: 16px;\">Lời giải chi tiết</strong></p><p>Đầu tiên ta gắn nhãn đỉnh S là I(S) = 0 và gắn cho ba đỉnh kề với S là A, B và C các nhãn tạm thời là I(S) + 2, I(S) + 1 và I(S) + 7. Chọn số nhỏ nhất trong chúng và viết I(B) = 1. Đỉnh B bây giờ được gắn nhãn vĩnh viễn là 1.</p>\r\n<p>Tiếp theo ta gắn nhãn cho các đỉnh kề với B là A, C, D, E và F các nhãn tạm thời là I(B) + 6 (hiện A có 2 nhãn tạm thời là 2 và 7), I(B) + 5 (hiện C có hai nhãn tạm thời là 7 và 6), I(B) + 12, I(B) + 15, I(B) + 9. Nhãn tạm thời nhỏ nhất trong các nhãn đã gắn (tại A, C, D, E, F) hiện nay là 2 (tại A), nên ta viết I(A) = 2. Điểm A được gắn nhãn vĩnh viễn là 2.</p>\r\n<p>Bây giờ ta xét các đỉnh kề với A mà chưa được gắn nhãn vĩnh viễn là D và E. Ta gắn cho đỉnh D nhãn tạm thời I(A) + 5 (hiện D có hai nhãn tạm thời là 13 và 7), gắn cho đỉnh E nhãn tạm thời I(A) + 8 (hiện E có hai nhãn tạm thời là 16 và 10). Nhãn tạm thời nhỏ nhất trong các nhãn đã gắn (tại D và E) là 7 (tại D), nên ta viết I(D) = 7. Đỉnh D được gắn nhãn vĩnh viễn là 7.</p>\r\n<p>Ta xét đỉnh E (chưa được gắn nhãn vĩnh viễn) kề với D, ta gắn nhãn tạm thời I(D) + 2 (hiện E có ba nhãn tạm thời là 16, 10 và 9). Vậy đỉnh E sẽ được gắn nhãn vĩnh viễn là 9 hay I(E) = 9.</p>\r\n<p>Tiếp tục ta xét các đỉnh kề với E mà chưa được gắn nhãn vĩnh viễn là C và F. Ta gắn cho đỉnh C nhãn tạm thời I(E) + 10 (hiện C có ba nhãn tạm thời là 7, 6 và 19), gắn cho F nhãn tạm thời I(E) + 6 (hiện F có hai nhãn tạm thời là 10 và 15). Nhãn tạm thời nhỏ nhất trong các nhãn đã gắn (ở C, F) hiện nay là 6 (tại C), nên ta viết I(C) = 6. Đỉnh C được gắn nhãn vĩnh viễn là 6.</p>\r\n<p>Xét đỉnh kề với C là F, ta gắn cho F nhãn tạm thời I(C) + 14 (hiện F có ba nhãn tạm thời là 10, 15 và 20) nên I(F) = 10. Đỉnh F được gắn nhãn vĩnh viễn là 10.</p>\r\n<p style=\"text-align: center;\"> <img src=\"https://img.loigiaihay.com/picture/2023/0805/1691223263.png\"   /></p>\r\n<p>Vậy, đường đi ngắn nhất từ đỉnh S đến đỉnh A là SA = 2.</p>\r\n<p>Đường đi ngắn nhất từ đỉnh S đến đỉnh B là SB = 1.</p>\r\n<p>Đường đi ngắn nhất từ đỉnh S đến đỉnh C có độ dài là I(C) = 6 và có đường đi là</p>\r\n<p align=\"center\">S → B → C.</p>\r\n<p>Đường đi ngắn nhất từ đỉnh S đến đỉnh D có độ dài là I(D) = 7 và đường đi là</p>\r\n<p align=\"center\">S → A → D.</p>\r\n<p>Đường đi ngắn nhất từ đỉnh S đến đỉnh E có độ dài là I(E) = 9 và đường đi là</p>\r\n<p align=\"center\">S → A → D → E.</p>\r\n<p>Đường đi ngắn nhất từ đỉnh S đến đỉnh F có độ dài là I(F) = 10 và đường đi là</p>\r\n<p align=\"center\">S → B → F.</p>"},{"article_id":145638,"cat_id":1572,"publish_time":1691223300,"type_ex":0,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_98.png","title":"Giải bài 2.17 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức","label":"Bài 2.17 trang 49 ","alias":"giai-bai-217-trang-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.","display_type":1,"article_type":1,"content":"<style>\r\n.method-close-icon{position: relative;float: right;top: 6px;transform: rotate(270deg);-ms-transform:rotate(270deg);-moz-transform:rotate(270deg);-webkit-transform:rotate(270deg);-o-transform:rotate(270deg);}\r\n.method-open-icon{position: relative;float: right;top: 6px;}\r\n</style>\r\n<p><strong style=\"font-size: 16px;\">Lời giải chi tiết</strong></p><p>Vì đồ thị Hình 2.35 là liên thông và các đỉnh đều có bậc chẵn (ở đây chỉ có đỉnh A và đỉnh F có bậc là 2, các đỉnh còn lại đều có bậc 4) nên đồ thị này có chu trình Euler.</p>\r\n<p>Một chu trình Euler xuất phát từ đỉnh A là ABCDBEDFECA và tổng độ dài của nó là</p>\r\n<p align=\"center\">3 + 5 + 8 + 6 + 4 + 2 + 3 + 9 + 7 + 4 = 51.</p>\r\n<p>Vậy một chu trình cần tìm là ABCDBEDFECA và có độ dài là 51.</p>"},{"article_id":145639,"cat_id":1572,"publish_time":1691223480,"type_ex":0,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_99.png","title":"Giải bài 2.18 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức","label":"Bài 2.18 trang 49 ","alias":"giai-bai-218-trang-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.36.","display_type":1,"article_type":1,"content":"<style>\r\n.method-close-icon{position: relative;float: right;top: 6px;transform: rotate(270deg);-ms-transform:rotate(270deg);-moz-transform:rotate(270deg);-webkit-transform:rotate(270deg);-o-transform:rotate(270deg);}\r\n.method-open-icon{position: relative;float: right;top: 6px;}\r\n</style>\r\n<p><strong style=\"font-size: 16px;\">Lời giải chi tiết</strong></p><p>Đồ thị Hình 2.36 chỉ có hai đỉnh bậc lẻ là C và E nên ta có thể tìm được một đường đi Euler từ C đến E (đường đi này đi qua mỗi cạnh đúng một lần).</p>\r\n<p>Một đường đi Euler từ đỉnh C đến đỉnh E là CABCEBDE và tổng độ dài của nó là</p>\r\n<p align=\"center\">2 + 1 + 4 + 10 + 5 + 3 + 6 = 31.</p>\r\n<p>Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ E đến C theo thuật toán gắn nhãn vĩnh viễn.</p>\r\n<p>Đường đi ngắn nhất từ E đến C là EBAC và có độ dài là 5 + 1 + 2 = 8.</p>\r\n<p>Vậy một chu trình cần tìm là CABCEBDEBAC và có độ dài là 31 + 8 = 39.</p>"}],"most_views":[{"article_id":145638,"cat_id":1572,"publish_time":1691223300,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_98.png","title":"Giải bài 2.17 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức","alias":"giai-bai-217-trang-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.","display_type":1},{"article_id":145632,"cat_id":1572,"publish_time":1691222580,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_94.png","title":"Giải mục 2 trang 47, 48, 49 Chuyên đề học tập Toán 11 - Kết nối tri thức","alias":"giai-muc-2-trang-47-48-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.","display_type":1},{"article_id":145637,"cat_id":1572,"publish_time":1691223060,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_97.png","title":"Giải bài 2.16 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức","alias":"giai-bai-216-trang-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Tìm đường đi ngắn nhất từ đỉnh S đến  mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.","display_type":1},{"article_id":145639,"cat_id":1572,"publish_time":1691223480,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_99.png","title":"Giải bài 2.18 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức","alias":"giai-bai-218-trang-49-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.36.","display_type":1},{"article_id":145629,"cat_id":1572,"publish_time":1691222340,"is_hot":0,"is_link":0,"thumbnail":"https://img.loigiaihay.com/picture/article/2023/0805/resize_1-0_93.png","title":"Giải mục 1 trang 46 Chuyên đề học tập Toán 11 - Kết nối tri thức","alias":"giai-muc-1-trang-46-chuyen-de-hoc-tap-toan-11-ket-noi-tri-thuc","introtext":"Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.","display_type":1}],"list_sub_event":[],"top_banner":"","cfg_info":{"last_cfg_time":"1521866679","ad.popup_frequency":"0","ad.adsense.detail_bottom.unit_id":"ca-app-pub-8529835372050931/9927553003","ad.adsense.popup.unit_id":"ca-app-pub-8529835372050931/2161779402","current.force.update.version":"181","support.email":"loigiaihay.com@gmail.com","support.fanpage":"https://www.facebook.com/Loigiaihay/","popup_rating_after":"86400","admob.app_id":"ca-app-pub-8529835372050931~4358271409","admob.unit.article_detail_bottom":"ca-app-pub-8529835372050931/1883637630","admob.unit.article_detail_top":"ca-app-pub-8529835372050931/8604898230","admob.unit.event_article_top":"ca-app-pub-8529835372050931/7406887709","admob.unit.interestial":"ca-app-pub-8529835372050931/2741937409","ios_appstore_link":"https://itunes.apple.com/us/app/loigiaihay/id1209891610?mt=8","android_appstore_link":"https://play.google.com/store/apps/details?id=com.tp.loigiaihay","min_version":"2.1.3","latest_version":"1.3.9","force_update":false},"popup_ads":[]}