Всем привет, меня зовут Елена и мы продолжаем разбирать задачи из ЕГЭ по информатике. В прошлой статье мы рассмотрели азы теории графов, научились решать задачи на сопоставление двух информационных моделей - графа и таблицы. В конце были приведены задачи для самостоятельного разбора. Все ли удалось?) Если есть какие-то вопросы по задачам, пишите в комментарии, дам подсказку или разберу сложную задачу подробно. В этой статье опишу алгоритм, позволяющий решать остальные задачи первого типа, подробно рассмотрим его работу на примере...

Из этой статьи вы узнаете об нахождении кратчайшего пути, проходя все точки графа и возвращаясь в исходную точку. Для решения задачи вам потребуется нарисованный граф и длины рёбер. Возьмём любую вершину, допустим “E“. Находим кратчайшее ребро, исходящее из этой точки. Как мы видим это ребро с длиной 3, но для нахождения кратчайшего пути в графе, мы не должны «перерезать» его, так как две стороны треугольника короче трёх. Поэтому мы это ребро забываем (сразу можно вычеркнуть рёбра со значениями 6, 8, 4, 2)...