73. Дан граф, в котором длины рёбер обозначены как m, k и n. Зная, что m > k > n и 4n > 2k > m > 3n, определите длину кратчайшего пути от вершины A до вершины M. Варианты: A) 3m; B) 2m+k; C) 2n+k+m; D) 2k+n+m; E) 3k+3m+n.

По направленным рёбрам сравним пути, ведущие из A в M.

1. Путь A → B → F → M имеет длину n + (2m − n) + m = 3m.
2. Путь A → C → F → M имеет длину k + m + m = k + 2m.
3. Путь A → B → E → F → M имеет длину n + n + k + m = 2n + k + m.
4. Путь A → B → E → G → M имеет длину n + n + (2k − m) + (2m − n) = 2k + m + n.
5. Также возможны пути через D; их длины не меньше указанных кандидатов при заданных соотношениях.

Из условия 2k > m следует, что 2m + k < 3m. А из 4n > 2k следует 2n + k + m > 2k + m + n, поскольку это равносильно 2n > k, что следует из 4n > 2k. Сравнение оставшихся кандидатов показывает, что кратчайшее значение — 2m + k.

Ответ: B) 2m + k.