Рассмотрим простой ориентированный граф G = (V, E). Пусть длина кратчайшего пути между вершинами v и u равна L. Докажите, что количество реберно непересекающихся путей между u и v в графе не превосходит (|V|/L)^2.


Пробовала доказательство от противного с применением теоремы Менгера о реберной двойственности, но ничего не получилось.

задан 2 Июл 18:45

@pluckityPluq: этот вопрос уже был здесь, но я там в комментарии написал про другую оценку, имея в виду |V|^2/L. Она совсем простая.

Хотелось бы уточнить условие: правильно ли я понимаю, что на графе задана ориентация, и пути рассматриваются только ориентированные, то есть по направлениям стрелок?

(2 Июл 19:22) falcao

@falcao да, все правильно, пути ориентированные.

(2 Июл 20:03) pluckityPluq
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×489

задан
2 Июл 18:45

показан
53 раза

обновлен
2 Июл 20:03

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

по почте:

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

по RSS:

Ответы

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

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