Пусть задан ориентированный граф G(V, E) и s, t ∈ V . Покажите, что минимальное число ребер в пути из s в t совпадает с максимальным значением φ(t) − φ(s) среди всех функций φ : V → Z, таких, что выполнено: φ(w) − φ(v) ≤ 1 для всех ребер (v, w) ∈ E.

задан 27 Июн '19 4:29

1

Если из v в w имеется путь длиной a (произведение a рёбер), то ф(w)-ф(v)<=a, что легко доказывается индукцией по a. С другой стороны, если в качестве ф(v) взять расстояние от v до s в графе, то условие ф(w)-ф(v)<=1 выполнено очевидным образом, и при этом ф(t)-ф(s)=a-0=a.

(27 Июн '19 9:25) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×629
×219

задан
27 Июн '19 4:29

показан
323 раза

обновлен
27 Июн '19 9:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru