Quảng cáo
1 câu trả lời 359
a) Tất cả các đường đi từ A đến T (đi qua mỗi đỉnh nhiều nhất một lần) là: ABDT, ACDT, ACET, ACDET, ACEDT, ABDET, ABDCET.
Ta có:
⦁ lABDT = wAB + wBD + wDT = 4 + 7 + 3 = 14;
⦁ lACDT = wAC + wCD + wDT = 2 + 6 + 3 = 11;
⦁ lACET = wAC + wCE + wET = 2 + 12 + 5 = 19;
⦁ lACDET = wAC + wCD + wDE + wET = 2 + 6 + 4 + 5 = 17;
⦁ lACEDT = wAC + wCE + wED + wDT = 2 + 12 + 4 + 3 = 21;
⦁ lABDET = wAB + wBD + wDE + wET = 4 + 7 + 4 + 5 = 20;
⦁ lABDCET = wAB + wBD + wDC + wCE + wET = 4 + 7 + 6 + 12 + 5 = 34.
b) Vì 11 < 14 < 17 < 19 < 20 < 21 < 34.
Nên lACDT < lABDT < lACDET < lACET < lABDET < lACEDT < lABDCET.
Vậy đường đi ngắn nhất từ A đến T là ACDT (có độ dài bằng 11).
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
135949 -
Hỏi từ APP VIETJACK
Đã trả lời bởi chuyên gia
76973 -
Đã trả lời bởi chuyên gia
72601 -
Đã trả lời bởi chuyên gia
48019

