Имеется граф G=(V,E), заданный списком смежности
a0 b0 a1 b1 am-1 bm-1 и количеством вершин n

надо найти наименьшее возможное множество ребер, помечая которые будет гарантировано, что любой путь из вершины Vo в вершину Vn-1 будет содержать хотя бы одно помеченное ребро, за полиномиальное время n и m.
То есть для такого графа это будет одно ребро (обозначено *), связывающее треугольники.

     /|
Vo /__|__*______ Vn-1
            |  /
            |/

У меня тут возник вопрос,на основе какого алгоритма надо делать этот поиск, имененная задача о потоке что-ли

Здравствуйте, axelk, Вы писали:

A>Имеется граф G=(V,E), заданный списком смежности
A>a0 b0 a1 b1 am-1 bm-1 и количеством вершин n

A>надо найти наименьшее возможное множество ребер, помечая которые будет гарантировано, что любой путь из вершины Vo в вершину Vn-1 будет содержать хотя бы одно помеченное ребро, за полиномиальное время n и m.
A>То есть для такого графа это будет одно ребро (обозначено *), связывающее треугольники.

Судя по описанию — стандартная задача о максимальном потоке/минимальном разрезе. Решается алгоритмом Форда-Фалкерсона.

Здравствуйте, Mikhail Adigeyev, Вы писали:

A>>надо найти наименьшее возможное множество ребер, помечая которые будет гарантировано, что любой путь из вершины Vo в вершину Vn-1 будет содержать хотя бы одно помеченное ребро, за полиномиальное время n и m.
A>>То есть для такого графа это будет одно ребро (обозначено *), связывающее треугольники.

MA>Судя по описанию — стандартная задача о максимальном потоке/минимальном разрезе. Решается алгоритмом Форда-Фалкерсона.

тут задача несколько другая, граф неорентиронанный и ребра не имеют меток, что в принципе делает пробленмым применение алгоритма Ф-Ф, у меня первая мысль была наити все кратчайшие пути между этими вершинами и затем выделить из них повторяющееся подмножество, но тогда получается O(n^3) да и ИМХО это несколько громоздкое решение

A>тут задача несколько другая, граф неорентиронанный
Что мешает для каждого ребра добавать ему обратное?

A> и ребра не имеют меток,
Меток.. о чем это?

A> что в принципе делает пробленмым применение алгоритма Ф-Ф, у меня первая мысль была наити все кратчайшие пути между этими вершинами и затем выделить из них повторяющееся подмножество, но тогда получается O(n^3) да и ИМХО это несколько громоздкое решение

IMHO, так вообще ничего не получится

Даже если ты и найдешь все кратчайшие пути, то что делать с ними дальше
непонятно... Ясно, что искомое множество в общем случае не есть их пересечение,
да и вообще метрические свойства графа тут непричем.

Делать нужно вот что: построить сеть, в которой все ребра имеют пропускную
способность 1. Далее найти в ней максимальный поток. Чем искать -- дело
вкуса и времени. Можно Ф-Ф (как и было замечено выше), можно push-relabel,
что быстрее...

После этого нужно построить минимальный разрез. Для этого нужно определить
множество вершин, доступных из исходной веришины в остаточной сети. Точнее,
это будет первая половина разреза, вторая -- ее дополнение. Искомые ребра
соединяют эти половины. Так кажется...

Здравствуйте, Max2, Вы писали:

M>Делать нужно вот что: построить сеть, в которой все ребра имеют пропускную
M>способность 1. Далее найти в ней максимальный поток. Чем искать -- дело
M>вкуса и времени. Можно Ф-Ф (как и было замечено выше), можно push-relabel,
M>что быстрее...

а может подскажете если знаете ссылку на описание алгоритма push-relabel, что-то я в замешательстве

A>а может подскажете если знаете ссылку на описание алгоритма push-relabel, что-то я в замешательстве
Простейшие варианы изложены в Коремене (Алгоритмы: построение и анализ)
(generic preflow push и lift-to-front). Более извращенные вариации
тоже существуют, попробую вспомнить, откуда ps-ки брал...

Здравствуйте, Max2, Вы писали:

M>Простейшие варианы изложены в Коремене (Алгоритмы: построение и анализ)
нашел я электронный вариант Кормена, оказывается это и есть та книга, рекомендованная преподом, я ее только ее обложку увидел, зелененькую с листиками Хорошая вещь, если бы не авторские права можно было бы выложить здесь в качестве faq

Здравствуйте, axelk, Вы писали:

A>нашел я электронный вариант Кормена, оказывается это и есть та книга, рекомендованная преподом, я ее только ее обложку увидел, зелененькую с листиками Хорошая вещь, если бы не авторские права можно было бы выложить здесь в качестве faq

А где нашел — в Интернете?
Если можно, ссылочку...