Ответ:
1. Граф по весовой матрице
Вершины графа: А, Б, В, Г, Д, Е. Рёбра и их веса: А–В (3), А–Д (11), А–Е (13), Б–Г (6), Б–Д (9), В–Е (2), Г–Д (12), Д–Е (5).
2. Циклы с мощностью рёбер 3
Цикл мощности 3 должен содержать три вершины и три ребра. В данном графе такой цикл один:
- А–Д–Е–А: веса рёбер 11, 5 и 13.
Других простых циклов с тремя рёбрами нет, поскольку среди остальных троек вершин отсутствует хотя бы одно необходимое ребро.
3. Кратчайший путь между А и Б
Из вершины А в Б можно попасть, например, по пути А–Д–Б:
\(11+9=20\).
Для сравнения, путь А–Е–Д–Б имеет длину \(13+5+9=27\), а путь А–В–Е–Д–Б — \(3+2+5+9=19\). Следовательно, путь через В и Е короче:
А–В–Е–Д–Б: \(3+2+5+9=19\).
Ответ: кратчайший путь А–В–Е–Д–Б, его длина равна 19.
