Форум » Анализ информационных моделей » задание 1 №4440 » Ответить
задание 1 №4440
Пичугина: Ответ сайта - 49, мой - 43. Почему нельзя проделать путь 5-3-6-1, так ведь дороги будут 11+13+19=43? Как я понимаю, ответ сайта для случая 7-3-6-1 с использованием дорог 17+13+19, но ведь это длиннее...
Ответов - 4
Danov: Из рисунка графа видно, что между узлами А и Е ровно 6 путей из 3х дорог и нет путей из 2х или 1го пути. Выбранный путь 5-3-6-1 имеет короткий путь в одну дорогу 5-1, чего на рисунке графа нет. Поэтому это решение не соответствует пути А-Е на графе.
Dharma: Дорогой из А в Е может быть как 1) 1-3-6-8 =49, так и 2) 2-1-3-6 = 55. Как определить, какой из путей подойдёт? Оба вписываются в схему, оба нам известны. Среди них мы не можем выбрать минимальный, т.к. тут разные оконечные точки. Ведь если предположить, что перый путь Б-Ж-Е-Д, то второй может быть вполне А-Б-Ж-Е
Danov: Этот граф - КУБ. Предложено найти путь по главной диагонали, из трех взаимно перпендикулярных ребер. Таких путей всего 6. Но для многих нет данных. А для тех что есть легко находится минимальный. Обычно в этой задаче ошибаются, выбирая два параллельных ребра. В итоге между вершинами можно провести путь в 1 ребро, что не соответствует рисунку.
Danov: Этот граф - КУБ. Предложено найти путь по главной диагонали, из трех взаимно перпендикулярных ребер. Таких путей всего 6. Но для многих нет данных. А для тех что есть легко находится минимальный. Обычно в этой задаче ошибаются, выбирая два параллельных ребра. В итоге между вершинами можно провести путь в 1 ребро, что не соответствует рисунку.
полная версия страницы