Удалить минимальное количество вершин, чтобы отключить граф

9

Рассмотрим неориентированный граф с источником и вершиной стока. Мы хотели бы удалить минимальное количество вершин в этом графе, чтобы разъединить любой путь между источником и приемником.

Можем ли мы сделать это, используя, скажем, алгоритм максимального потока, минимального разреза?

babysnow
источник
4
Это должно работать (я предполагаю, что все края имеют одинаковую емкость).
А.Шульц

Ответы:

3

(Этот ответ был первоначально дан как часть вопроса, с целью его проверки.)

Моя интуиция подсказывает мне, что мы можем использовать алгоритм максимального потока, минимального разреза для решения этой проблемы:

  1. Замените каждый из ненаправленных ребер парой направленных ребер.
  2. Замените каждую вершину двумя вершинами и соединенными ребром. все входящие ребра будут связаны с , все исходящие ребра будут связаны с .vvinvoutvvinvvout
  3. Попробуйте найти минимальный разрез . Ребра относятся к вершинам, которые нам нужно удалить.MM
FrankW
источник
Мне не ясно, почему это будет гарантировано работать. Что если минимальный разрез модифицированного графа включает в себя некоторые ребра, которые не находятся между некоторыми и , но являются направленным ребром из шага 1 решения? Почему вы думаете, что каждый минимальный срез вершины исходного графа будет соответствовать одному к одному с минимальным срезом модифицированного графа? Я думаю, что доказательства нужны. vinvout
DW
Чтобы поддержать ответ от FrankW, пожалуйста, перейдите по ссылкам ниже, есть статья Абдола-Хоссейна Исфаханяна, поддерживающая замену неориентированного ребра двумя направленными ребрами. - networkx.github.io/documentation/latest/reference/generated/… - cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
Паван Путтасвами
1
@pawanp, я не слежу за тобой. Конечно, вы можете заменить ненаправленное ребро двумя направленными ребрами. Вопрос не в том, сможете ли вы это сделать, а в том, перечислил ли после применения алгоритма FrankW, гарантированно ли вывод будет правильным решением исходной проблемы. Я не понимаю, насколько важна справочная страница библиотеки NetworkX. Что касается статьи: она имеет 14 страниц, с 11 различными алгоритмами, большинство из которых не имеют доказательств правильности. Можете ли вы более конкретно указать, какую именно часть вы считаете здесь уместной?
DW