Quay lại
Đáp án
Câu 1 [1041699]: Một máy bay không người lái (drone) được dùng để phun thuốc diệt côn trùng trên các khu vực cánh đồng được kết nối với nhau. Mỗi khu vực là một đỉnh và các lối đi giữa các khu vực là các cạnh. Drone cần bay qua tất cả các lối đi để phun thuốc đều khắp, bắt đầu và kết thúc tại điểm sạc. Trên hình vẽ mô tả, drone bắt đầu tại điểm sạc S đi đến các khu vực được kí hiệu K1, K2, K3, K4, K5. Có bao nhiêu lộ trình để drone bay qua tất cả các lối đi đúng một lần và quay về điểm sạc S?
Điền đáp án: 0.
Tính bậc của các đỉnh:

Có bốn đỉnh bậc lẻ là
Một chu trình đóng đi qua mỗi cạnh đúng một lần (bắt đầu và kết thúc tại ) tồn tại chỉ khi mọi đỉnh có bậc chẵn (điều kiện của chu trình Euler).
Vì ở đây có đỉnh lẻ, không tồn tại chu trình như vậy.
Vậy số lộ trình thỏa yêu cầu là 0.
Câu 2 [1041700]: Trong thiết kế bảng mạch in, đôi khi cần định tuyến một đường mạch điện đi qua một tập hợp các điểm tiếp xúc (P1, P2, P3, P4, P5) mà mỗi điểm phải được ghé thăm đúng một lần. Đường mạch bắt đầu và kết thúc tại cùng một điểm kết nối. Trên đồ thị điểm bắt đầu là P0.
a) Có bao nhiêu chu trình để đường mạch đi qua tất cả 6 cạnh đúng một lần và quay về P0?
b) Có bao nhiêu chu trình để đường mạch đi qua tất cả 6 điểm tiếp xúc đúng một lần và quay về P0?
a) Điền đáp án: 0.
Tính bậc của các đỉnh:

Không tồn tại chu trình Euler vì bậc các đỉnh đều là bậc lẻ
b) Điền đáp án: 6.
Có 6 chu trình là





Câu 3 [1041701]: Một công ty muốn thiết lập một hệ thống liên lạc nội bộ giữa các phòng ban. Mỗi phòng ban cần có thể liên lạc trực tiếp hoặc gián tiếp với mọi phòng ban khác và có một đường dẫn đi qua tất cả các phòng ban đúng một lần để kiểm tra hệ thống định kỳ (tham khảo hình vẽ). Có bao nhiêu lộ trình di chuyển từ phòng IT đến kiểm tra hệ thống bằng cách đi qua tất cả 6 phòng ban đúng một lần và quay về phòng IT?
Điền đáp án: 2
Có đúng 2 lộ trình là

Câu 4 [1041702]: Một kỹ sư kiểm tra chất lượng cần kiểm tra 5 giai đoạn sản xuất khác nhau (A, B, C, D, E) trong một nhà máy. Mỗi giai đoạn chỉ cần kiểm tra đúng một lần. Anh ta bắt đầu từ văn phòng (VP) của mình và muốn quay trở lại đó sau khi kiểm tra xong tất cả các giai đoạn. Hình vẽ sau thể hiện đường đi giữa văn phòng và 5 điểm sản xuất. Có bao nhiêu lộ trình mà kỹ sư có thể thực hiện?
Điền đáp án: 4.




Câu 5 [1041703]: Một công ty muốn lắp đặt hệ thống đèn chiếu sáng cho một công viên với nhiều lối đi. Để tiết kiệm năng lượng và giảm chi phí bảo trì, họ muốn có một công nhân kiểm tra và thay thế bóng đèn bị hỏng bằng cách đi từ trạm điều khiển trung tâm qua mỗi đoạn đường có đèn để lắp đèn và quay về trạm điều khiển trung tâm. Ở đồ thị dưới đây, vị trí của trạm điều khiển trung tâm là 1, còn lại là các điểm lắp đèn.
a) Với mục tiêu tiết kiệm chi phí, liệu có thể tìm được một lộ trình tối ưu để công nhân đi qua tất cả các đoạn đường có đèn chỉ một lần và trở lại trạm điều khiển (giao lộ 1) hay không? Tại sao?
b) Nếu câu a không tồn tại thì số lượng đoạn đường tối thiểu cần di chuyển ít nhất 2 lần là bao nhiêu?
a) Điền đáp án: 0.
Ta tìm bậc của các đỉnh:

Không tồn tại chu trình Euler vì có đỉnh bậc lẻ.
b) Điền đáp án: 2.
Câu 6 [680753]: Một trò chơi điện tử quy định như sau: Có 4 trụ với số lượng các thử thách trên đường đi giữa các cặp trụ được mô tả trong hình bên. Người chơi xuất phát từ một trụ nào đó, đi qua tất cả các trụ còn lại, mỗi khi đi qua một trụ thì trụ đó sẽ bị phá hủy và không thể quay trở lại trụ đó được nữa, nhưng người chơi vẫn phải trở về trụ ban đầu. Tổng số thử thách của đường đi thoả mãn điều kiện trên nhận giá trị nhỏ nhất là bao nhiêu?
Nội dung kiến thức: Chuyên đề toán 11 (Làm quen với một vài yếu tố của lí thuyết đồ thị).
Mức độ: Vận dụng.
Lời giải chi tiết:
Ta sử dụng thuật toán láng giếng gần nhất.
TH1: Xuất phát từ A
Từ A đến D : 9
Từ D đến B: 11
Từ B đến C: 12
Từ C về A: 11
Tổng số thử thách là 43.
TH2: Xuất phát từ B
Từ B đến A : 10
Từ A đến D: 9
Từ D đến C: 14
Từ C về B: 12
Tổng số thử thách là 45.
TH3: Xuất phát từ C
Từ C đến A : 11
Từ A đến D: 9
Từ D đến B: 11
Từ B về C: 12
Tổng số thử thách là 43.
TH4: Xuất phát từ D
Từ D đến A : 9
Từ A đến B: 10
Từ B đến C: 12
Từ C về D: 14
Tổng số thử thách là 45.
Số thử thách nhỏ nhất là 43.
Điền đáp án:
Câu 7 [779852]: Giả sử 4 thành phố A, B, C, D với khoảng cách (đơn vị: km) giữa các thành phố được cho bởi bảng sau:

Quãng đường ngắn nhất để đi qua tất cả các thành phố đúng một lần rồi quay lại thành phố xuất phát là bao nhiêu kilômét?
Cần tìm quãng đường ngắn nhất để đi qua tất cả các thành phố đúng một lần rồi quay lại thành phố xuất phát, do đó ta cần tìm chu trình Hamilton.
Đồ thị có 4 đỉnh, các đỉnh đều có bậc nên đồ thị có chu trình Hamilton.
Sử dụng thuật toán láng giềng gần nhất.
Giả sử đỉnh bắt đầu là đỉnh A, ta có: Từ A, đỉnh gần nhất là B,
Từ B, đỉnh chưa đến gần nhất là C,
Từ C, đỉnh chưa đến gần nhất là D,
Đến đây, không còn đỉnh nào chưa đến, vì vậy quay về A,
Tổng quãng đường theo chu trình ABCDA là
Tương tự bắt đầu với những đỉnh khác, ta có bảng sau:
Vậy quãng đường ngắn nhất để đi qua tất cả các thành phố đúng một lần rồi quay lại thành phố xuất phát là 85 km với chu trình ABCDA.
Câu 8 [1041704]: Một công ty viễn thông muốn xây dựng một mạng lưới cáp quang kết nối 6 thành phố T1 , T2, T3, T4, T5, T6. Để tiết kiệm chi phí, công ty cần tìm cách nối cáp sao cho tổng chiều dài cáp sử dụng là nhỏ nhất nhưng vẫn đảm bảo tất cả các thành phố đều được kết nối với nhau (có thể gián tiếp). Khoảng cách (đơn vị: km) giữa các cặp thành phố có thể nối trực tiếp được cho như sau:

a) Vẽ đồ thị biểu diễn các thành phố và khoảng cách giữa các thành phố.
b) Xác định các đoạn cáp quang cần xây dựng để tổng chiều dài cáp là nhỏ nhất. Tổng chiều dài cáp tối thiểu là bao nhiêu?
a) Điền đáp án:

b) Điền đáp án: 33.
Đoạn chiều dài để dây cáp nhỏ nhất là
Tổng chiểu dài cáp tối thiểu là
Câu 9 [1041705]: Một xe thu gom hàng tái chế cần đi qua tất cả các con đường trong một khu vực nhỏ để thu gom rác. Ngoài ra, có 3 trạm tái chế lớn cần được ghé thăm đúng một lần để dỡ hàng đặc biệt và 1 trạm tái chế nhỏ có thể đi qua nhiều lần. Xe bắt đầu và kết thúc hành trình tại bãi chứa. Trên đồ thị, bãi chứa là điểm B, các trạm tái chế lớn bao gồm S1, S2, S3 và trạm nhỏ là S4; trọng số trên đồ thị là khoảng cách giữa các điểm tính bằng kilomet. Hãy xác định quãng đường ngắn nhất mà xe gom rác đó đi được theo đơn vị kilomet.
Điền đáp án: 16.
Quãng đường ngắn nhất là
Tổng độ dài quãng đường là
Câu 10 [1041706]: Một tàu vũ trụ thám hiểm được giao nhiệm vụ hạ cánh và thu thập dữ liệu từ 5 hành tinh mới được phát hiện trong một hệ mặt trời xa xôi: Tàu có khả năng di chuyển giữa các hành tinh theo những tuyến đường đã được thiết lập. Chi phí nhiên liệu (đơn vị: đơn vị năng lượng) để di chuyển giữa các hành tinh được cho trong bảng dưới đây (giả định các tuyến đường là hai chiều):

Tàu vũ trụ phải xuất phát từ một hành tinh bất kỳ, sau đó hạ cánh thăm dò mỗi hành tinh đúng một lần duy nhất. Sau khi thăm dò xong hành tinh cuối cùng, tàu không cần quay trở lại hành tinh xuất phát. Tàu sẽ chọn lịch trình di chuyển (thứ tự các hành tinh sẽ thăm) sao cho tổng chi phí nhiên liệu là nhỏ nhất. Tổng chi phí nhiên liệu nhỏ nhất đó là bao nhiêu đơn vị nhiên liệu?
Điền đáp án: 34.

Ta sử dụng thuật toán láng giềng gần nhất
TH1: Bắt đầu kéo từ
Đoạn đường ngắn nhất là
Chi phí nhiên liệu là
TH2: Bắt đầu kéo từ
Đoạn đường ngắn nhất là
Chi phí nhiên liệu là
TH3: Bắt đầu kéo từ
Đoạn đường ngắn nhất là
Chi phí nhiên liệu là
TH4: Bắt đầu kéo từ
Đoạn đường ngắn nhất là
Chi phí nhiên liệu là
TH5: Bắt đầu kéo từ
Đoạn đường ngắn nhất là
Chi phí nhiên liệu là
Vậy tổng chi phí nhỏ nhất là 34 đơn vị.
Câu 11 [693539]: Một mạng cáp quang dùng để kết nối giữa năm thị trấn. Bảng số liệu bên dưới cho biết về chi phí để lắp đặt (đơn vị: triệu đồng).

Chi phí lắp đặt tối thiểu để kết nối tất cả các thị trấn là bao nhiêu triệu đồng (hai thị trấn bất kỳ có thể kết nối qua một thị trấn trung gian)?
Điền đáp án:
Ta mô phỏng bài toán trên dưới dạng đồ thị với năm thị trấn là năm đỉnh, chi phí để lắp đặt giữa các thị trấn là trọng số của các cạnh. Yêu cầu của bài toán là tìm cây khung nhỏ nhất.
Ta tìm cây khung nhỏ nhất bằng cách lần lượt thêm vào các cạnh có trọng số từ nhỏ đến lớn (hai đỉnh của cạnh được thêm vào sau không tạo thành chu trình):
Cạnh BC: 10 triệu đồng.
Cạnh AE: 16 triệu đồng.
Cạnh EC: 20 triệu đồng.
Cạnh AC: 25 triệu đồng (loại vì tạo thành chu trình).
Cạnh BD: 27 triệu đồng.
Chi phí lắp đặt tối thiểu để kết nối tất cả các thị trấn là: (triệu đồng).
Câu 12 [1041707]: Một nông trại có 5 khu vực cần nối ống nước. Giữa các khu có thể kéo ống với chi phí đã được xác định giống như đồ thị sau (đơn vị tính bằng triệu đồng). Các đường ống phải đi qua tất cả các khu. Chi phí thấp nhất mà chủ nông trại phải chi ra bằng bao nhiêu nghìn đồng?
Điền đáp án: 8000.
Ta sử dụng thuật toán láng giềng gần nhất
TH1: Bắt đầu kéo từ Khu E
Đoạn đường ngắn nhất là
Chi phí là triệu.
TH2: Bắt đầu kéo từ Khu C
Đoạn đường ngắn nhất là
Chi phí là triệu.
TH3: Bắt đầu kéo từ Khu D
Đoạn đường ngắn nhất là
Chi phí là triệu.
TH4: Bắt đầu kéo từ Khu A
Đoạn đường ngắn nhất là
Chi phí là triệu.
TH5: Bắt đầu kéo từ Khu B
Đoạn đường ngắn nhất là
Chi phí là triệu.
Vậy tổng chi phí nhỏ nhất là 8 triệu= 8000 nghìn đồng
Câu 13 [696318]: Một xe vận tải đang ở kho hàng và cần giao cho 4 khách hàng tại các địa điểm khác nhau. Các khoảng cách giữa các địa điểm được ghi lại như sau:

Vậy khoảng cách tối thiểu để hoàn thành lộ trình giao hàng cho tất cả các khách hàng và quay lại kho hàng là bao nhiêu kilômét?
Dựa vào dữ kiện: “Một xe vận tải đang ở kho hàng và cần giao cho 4 khách hàng tại các địa điểm khác nhau”.
Kết hợp với dữ kiện câu hỏi: “khoảng cách tối thiểu để hoàn thành lộ trình giao hàng cho tất cả các khách hàng và quay lại kho hàng”.
Từ bảng số liệu, ta vẽ được đồ thị

Đồ thị có 5 đỉnh, các đỉnh đều có bậc nên đồ thị có chu trình Hamilton.Ta có các chu trình xuất phát từ O:

Vậy khoảng cách tối thiểu để hoàn thành lộ trình giao hàng cho tất cả các khách hàng và quay lại kho hàng là 48 km với chu trình OBDCAO.
Câu 14 [779854]: Công ty giao hàng nhanh có 4 kho hàng A, B, C và D. Quản lý muốn lên kế hoạch cho xe giao hàng đi qua tất cả các kho hàng đề lấy hàng và quay lại kho hàng ban đầu, với điều kiện là mỗi kho hàng chỉ ghé qua một lần. Khoảng cách giữa các kho hàng (km) được mô tả trong hình vẽ. 

Quãng đường ngắn nhất để xe giao hàng hoàn thành việc lấy hàng ở các kho và quay trở lại kho hàng ban đầu là bao nhiêu kilômét?
Nội dung kiến thức: Chuyên đề toán lớp 11 (Đường đi Euler và đường đi Hamilton).
Mức độ: Vận dụng (8+).
Xe giao hàng đi qua tất cả các kho hàng đề lấy hàng và quay lại kho hàng ban đầu, với điều kiện là mỗi kho hàng chỉ ghé qua một lần nên ta sẽ đi tìm đường đi Hamilton của đồ thị.
Đồ thị gồm 4 đỉnh, mỗi đỉnh của đồ thị đều có bậc là nên đồ thị có chu trình Hamilton.
Xe giao hàng có thể xuất phát từ một trong 4 kho A, B, C, D.
Giả sử xe giao hàng xuất phát từ kho A.Để đi qua tất cả các kho hàng và quay trở về A, xe giao hàng có thể đi theo một trong các đường đi:

Nếu xuất phát từ đỉnh khác thì chỉ là phép thay thế bước đi trong sơ đồ trên.Vậy quãng đường ngắn nhất để xe giao hàng hoàn thành việc lấy hàng ở các kho và quay trở lại kho hàng ban đầu là 15 km.
Câu 15 [779857]: Trường THPT A tổ chức chuyến đi về nguồn cho học sinh tham quan 4 địa điểm A, B, C, D; thời gian (đơn vị: phút) di chuyển qua lại giữa các điểm tham quan được mô tả ở hình bên. Đoàn học sinh của trường sẽ tham quan một địa điểm nào đó đầu tiên, rồi đi qua tất cả các địa điểm còn lại, mỗi khi đã tham quan địa điểm nào rồi thì sẽ không quay lại đó nữa nhưng phải về địa điểm ban đầu để trở về. Hỏi tổng thời gian tham quan các địa điểm thỏa mãn điều kiện trên nhận giá trị nhỏ nhất là bao nhiêu phút?
Nội dung kiến thức: Chuyên đề học tập toán 11 (Đường đi Hamilton).
Mức độ: Vận dụng (8+).
Do đoàn học sinh của trường sẽ tham quan một địa điểm nào đó đầu tiên, rồi đi qua tất cả các địa điểm còn lại, mỗi khi đã tham quan địa điểm nào rồi thì sẽ không quay lại đó nữa nhưng phải về địa điểm ban đầu để trở về nên ta sẽ đi tìm các chu trình Hamilton.
Đồ thị có 4 đỉnh, các đỉnh đều có bậc nên đồ thị có chu trình Hamilton.
Đoàn học sinh của trường có thể xuất phát từ một trong 4 địa điểm A, B, C, D.
Giả sử đoàn học sinh của trường xuất phát từ địa điểm A.Để đi qua tất cả địa điểm và quay trở về A, đoàn học sinh có thể đi theo một trong các đường đi:

Nếu xuất phát từ đỉnh khác thì chỉ là phép thay thế bước đi trong sơ đồ trên.
Vậy tổng thời gian tham quan các địa điểm nhỏ nhất là 99 phút.
Câu 16 [693340]: Biểu đồ thể hiện các con đường nối giữa các thị trấn (đơn vị: km). Cán bộ thanh tra xuất phát từ thị trấn L đi kiểm tra tất cả các tuyến đường nối giữa các thị trấn M, N, O và quay lại L. Chiều dài quãng đường tối thiểu thanh tra cần phải đi là bao nhiêu km?
Điền đáp án:
Nhận thấy đồ thị trên đều là bậc chẵn ( không có đỉnh bậc lẻ).
Đồ thị tồn tại chu trình Euler: chu trình đi qua tất cả các cạnh của đồ thị đúng một lần (quãng đường tối thiểu).
Chiều dài quãng đường tối thiểu thanh tra cần phải đi là tổng độ dài tất cả các quãng đường có trong đồ thị trên:
Câu 17 [779862]: 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. Thời gian di chuyển (đơn vị: phút) giữa các trường học và giữa bảo tàng với mỗi trường học được mô tả trong hình vẽ.Vậy thời gian đi ít nhất để thực hiện chu trình trên là bao nhiêu phút?
Vì nhân viên bảo tàng muốn đến từng trường và quay trở lại bảo tàng sau khi thăm cả ba trường nên ta sẽ đi tìm chu trình Hamilton của đồ thị.
Đồ thị có 4 đỉnh, các đỉnh đều có bậc nên đồ thị có chu trình Hamilton.
Áp dụng thuật toán láng giềng gần nhất, ta có:
Từ viện bảo tàng, thời gian di chuyển đến trường B là ngắn nhất: 19 phút.
Từ trường B, thời gian di chuyến đến trường A là ngắn nhất: 38 phút.
Từ trường A, thời gian di chuyển đến trường C là ngắn nhất: 32 phút.
Đến đây, không còn địa điểm nào nên quay lại viện bảo tàng với thời gian di chuyển: 51 phút.
Do đó, chu trình xuất phát từ viện bảo tàng, qua trường A, trường B, trường C rồi quay lại viện bảo tàng có thời gian đi ít nhất và thời gian đi là (phút).
Câu 18 [1041708]: Một kỹ thuật viên phải kiểm tra hệ thống điều hòa tại 4 tòa nhà chính của một khu chung cư. Anh ta cần đi qua tất cả các đoạn đường ống kết nối giữa các tòa nhà ít nhất một lần để phát hiện rò rỉ và phải ghé thăm tất cả các phòng điều khiển chính (là các đỉnh trên đồ thị) đúng một lần để đọc chỉ số. Anh ta bắt đầu và kết thúc hành trình tại trung tâm bảo trì. Trên đồ thị M là trung tâm bảo trì, 4 tòa nhà được kí hiệu là T1, T2, T3, T4. Trọng số trên đồ thị là thời gian di chuyển (đơn vị phút). Thời gian tối thiểu để kỹ thuật viên hoàn thành nhiệm vụ là bao nhiêu phút?
Điền đáp án: 59.
Đoạn đường ngắn nhất có thể đi là

Thời gian tối thiểu là
Câu 19 [695297]: Xe xúc tuyết phải dọn tuyết bằng cách lái xe dọc theo tất cả các con đường được hiển thị như hình vẽ (đơn vị: km).

Quãng đường ngắn nhất xe xúc tuyết phải đi bằng bao nhiêu km?
Điền đáp án:
Nhận thấy đây là đồ thị vô hướng có hai đỉnh bậc lẻ Có đường đi Euler.
Để xe xúc tuyết đi được quãng đường ngắn nhất thì xe chỉ đi qua các con đường đúng một lần.
Một trong số các cách đi của xe là:
Quãng đường ngắn nhất xe xúc tuyết phải đi là:
Câu 20 [1041709]: Một công ty cần lắp đặt hệ thống camera an ninh để giám sát 5 vị trí quan trọng trong một tòa nhà. Các vị trí này cần được kết nối với nhau bằng cáp mạng để truyền tín hiệu về trung tâm điều khiển. Chi phí kéo cáp giữa các vị trí là khác nhau. Công ty muốn kết nối tất cả các vị trí với nhau sao cho mạng lưới hoàn chỉnh và tổng chi phí kéo cáp là thấp nhất. Trên đồ thị thể hiện chi phí (đơn vị: triệu đồng) đường nối dây cáp giữa 5 khu vực giám sát an ninh. Hãy xác định số tiền tổi thiểu theo đơn vị triệu đồng mà công ty phải chi trả.
Điền đáp án: 34.
Đoạn đường ngắn nhất là
Chi phí là triệu.
Câu 21 [779864]: Một người đưa thư xuất phát từ bưu điện (vị trí A) và phải đi qua các con đường để phát thư rồi quay lại bưu điện. Sơ đồ các con đường cần đi qua và độ dài của chúng (tính theo mét) được biểu diễn ở hình vẽ dưới. Vậy quãng đường ngắn nhất người đó phải đi là bao nhiêu mét?
Đồ thị trên 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).
Một đường đi Euler từ A đến D là AFEABEDBCD và tổng độ dài của nó là:
Để 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.
Đường đi ngắn nhất từ D đến A là DCBA và có độ dài
Vậy quãng đường ngắn nhất người đó phải đi là
Câu 22 [1041710]: Một công ty an ninh cần thiết kế lộ trình tuần tra cho nhân viên trong một khu dân cư phức tạp. Nhân viên bảo vệ xuất phát từ trạm gác G1 phải đi qua mọi đoạn đường để đảm bảo an ninh và cuối cùng phải quay trở lại trạm gác ban đầu. Mục tiêu là đi qua mỗi đoạn đường đúng một lần nếu có thể hoặc ít nhất là đi lại số đoạn đường ít nhất. Các giao lộ là các đỉnh G1, G2, G3, G4, G5, G6, G7, G8 và khoảng cách giữa các giao lộ (tính theo mét) được cho bởi đồ thị sau:

a) Có thể thiết lập một lộ trình để nhân viên bảo vệ đi qua tất cả các đoạn đường đúng một lần và quay về điểm xuất phát hay không?
b) Tính tổng quãng đường cần thiết để nhân viên bảo vệ hoàn thành nhiệm vụ này và quay về G1 theo đơn vị mét.
a) Điền đáp án: 0.
Ta có bậc của các đỉnh:

Không tồn tại chu trình Euler.
b) Điền đáp án: 1700.
Ta có công thức: Khoảng cách đường đi ngắn nhất giữa chúng =Tổng độ dài tất cả các cạnh + tổng khoảng cách ghép cặp tối thiểu giữa các đỉnh bậc lẻ
Tổng độ dài tất cả các cạnh là

Tính khoảng cách ngắn nhất giữa các đỉnh lẻ :
-
-
-
-
-
-
Các cách ghép đôi 4 đỉnh lẻ:
-
-
-
Trong ba cách, nhỏ nhất là 390 m.
Tổng chiều dài tối thiểu của chu trình là
Câu 23 [779865]: Một người đưa thư xuất phát từ bưu điện ở vị trí A, các điểm cần phát thư nằm dọc các con đường cần đi qua. Biết rằng người này phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho tất cả các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại điểm xuất phát. Độ dài các con đường như hình vẽ (đơn vị độ dài). tổng quãng đường người đưa thư có thể đi ngắn nhất là bao nhiêu?
Theo sơ đồ đường đi thấy có 2 đỉnh bậc lẻ là A và D nên có thể tìm được một đường đi Euler từ A đến D (đường này đi qua mỗi cạnh đúng một lần).
Một đường Euler từ A đến D là AEABEDBCD và có độ dài là
Để 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.
Đường đi ngắn nhất từ D đến A là DBA và có độ dài
Vậy tổng quãng đường ngắn nhất mà người đưa thư có thể đi là
Câu 24 [693312]: Từ kho D xe bưu chính đến lấy thư từ các hộp thư tại E, F, G và H rồi quay lại kho. Sơ đồ bên hiển thị thời gian xe bưu chính di chuyển giữa các hộp thư (đơn vị: phút). Thời gian ngắn nhất để xe bưu chính thực hiện điều đó là bao nhiêu phút?

Điền đáp án:
Cách 1: Tư duy
Cách 2: Kiến thức đồ thị
Áp dụng thuật toán láng giềng gần nhất, ta sẽ ưu tiên cho xe bưu chính di chuyển đến những hộp thư gần nhất và chưa được đi đến trước đó.
Quãng đường đi của xe là:
Thời gian ngắn nhất để xe bưu chính thực hiện điều đó là: 35 phút.
Câu 25 [694725]: Công ty A có kế hoạch tổ chức tour du lịch tâm linh tại tỉnh Bắc Giang đi qua 5 địa điểm: Đền Xương Giang, Chùa Bổ Đà, Chùa Vĩnh Nghiêm, Thiền viện Trúc lâm Phượng Hoàng, Đền Ngọc Lâm. Hành khách sẽ xuất phát từ Đền Xương Giang và đi thăm mỗi địa điểm đúng một lần. Qua khảo sát thực địa, công ty xây dựng được lược đồ như hình (khoảng cách giữa mỗi cặp địa điểm được ghi trên đường nối). Để tiết kiệm chi phí, công ty dự định chọn tuyến đường có tổng độ dài ngắn nhất. Độ dài của tuyến đường này là bao nhiêu km?
Điền đáp án: 64,3.
Ta sử dụng thuật toán láng giếng gần nhất.
+) Tuyến 1: Đền Xương Giang Đền Ngọc Lâm Chùa Bổ Đà Thiền viện Trúc Lâm Phượng Hoàng Chùa Vĩnh Nghiêm.
Độ dài quãng đường là
+) Tuyến 2: Đền Xương Giang Chùa Vĩnh Nghiêm Thiền viện Trúc Lâm Phượng Hoàng Đền Ngọc Lâm Chùa Bổ Đà.
Độ dài quãng đường là
+) Tuyến 3: Đền Xương Giang Chùa Bổ Đà Đền Ngọc Lâm Thiền viện Trúc Lâm Phượng Hoàng Chùa Vĩnh Nghiêm.
Độ dài quãng đường là
+) Tuyến 4: Đền Xương Giang Thiền viện Trúc Lâm Phượng Hoàng Chùa Vĩnh Nghiêm Đền Ngọc Lâm Chùa Bổ Đà.
Độ dài quãng đường là
Câu 26 [695256]: Các khu cắm trại tại một công viên được mô phỏng như hình vẽ bên (đơn vị: mét). Bác bảo vệ đang ở khu cắm tại A và phải kiểm tra tất cả các khu cắm trại B, C, D, E, F và G (không nhất thiết phải theo thứ tự đó). Vậy quãng đường ngắn nhất bác bảo vệ có thể đi và điểm kiểm tra cuối cùng ở khu cắm tại D bằng bao nhiêu mét?
Điền đáp án:
Áp dụng kĩ thuật người láng giềng gần nhất, bác bảo vệ sẽ ưu tiên di chuyển đến những khu cắm trại gần nhất và chưa được đi đến trước đó.
Quãng đường đi của bác bảo vệ là:
Vậy quãng đường ngắn nhất bác bảo vệ có thể đi là: