Рассмотрим граф $%G$% с двумя выделенными несмежными вершинами $%s$% и $%t$%. Множество вершин $%X$%, не содержащее вершин $%s$% и $%t$%, назовём вершинным разрезом, если после его удаления из графа пути между $%s$% и $%t$% будут отсутствовать.

Рассмотрим наряду с графом $%G$% граф $%H$%, полученный с помощью следующей процедуры. Каждую вершину $%v_i$% графа $%G$% разделим на две вершины $%v_{i1}$% и $%v_{i2}$%, которые дополнительно соединим направленным ребром $%(v_{i1},v_{i2})$% в случае, если $%v_i$% отлична от $%s$% и от $%t$%. Каждое ребро $%\{v_i,v_j\}$% заменим на два ребра $%(v_{i2},v_{j1})$% и $%(v_{j2},v_{i1})$%.

Из получившегося графа $%H$% получим сеть $%H′$%, приписав каждому ребру пропускную способность 1, в качестве истока взяв $%s_2$%, а в качестве стока — $%t_1$%. Доказать, что величина максимального потока в сети $%H′$% равна величине минимального вершинного разреза в графе $%G$%.

задан 26 Мар '16 12:53

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,259
×477
×156
×142
×8

задан
26 Мар '16 12:53

показан
553 раза

обновлен
26 Мар '16 13:10

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

по почте:

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

по RSS:

Ответы

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

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