34. В весовой матрице между населёнными пунктами A, B, C, D, E, F и G указана длина существующих дорог (отсутствие значения в ячейке означает отсутствие прямой дороги между пунктами). Определите соответствие: 1. Длина кратчайшего пути между пунктами A и F; 2. Количество рёбер в графе. Варианты: A) 1 — a; 2 — e; B) 1 — b; 2 — d; C) 1 — c; 2 — d; D) 1 — b; 2 — e; E) 1 — a; 2 — c. a. 8; b. 22; c. 7; d. 12; e. 11.

По матрице дороги имеют веса: A–C = 1, A–E = 2, A–F = 12, A–G = 5, B–D = 7, B–G = 9, C–D = 4, C–F = 7, D–F = 6, E–G = 3, F–G = 4.

Кратчайший путь A–F: прямой путь имеет длину 12; через G получаем A–G–F длиной 5 + 4 = 9; через C — A–C–F длиной 1 + 7 = 8. Следовательно, кратчайшая длина равна 8.

В списке указано 11 рёбер, считая каждую неориентированную дорогу один раз.

Итак, 1 — a (8), 2 — e (11).

Ответ: вариант A.