Блог

Учитывая неориентированный граф, G, существует ли какой-либо стандартный алгоритм для нахождения значения k, где (k-1) представляет количество вершин, удаление которых приводит к графу, который все еще связан, а удаление k-й вершины делает граф разъединенным?

Спасибо! Переход

Я не знаю ни о каком стандартном алгоритме, но для того, чтобы граф обладал этим свойством, каждая пара вершин должна иметь > = k независимых путей между ними (это простое доказательство от противного, чтобы увидеть, что это так).

Таким образом, потенциальным алгоритмом было бы проверить, что для всех пар вершин в вашем графике существует по крайней мере K независимых путей. Чтобы найти это, вы можете использовать алгоритм максимального потока. К сожалению, выполнение этого тривиально, вероятно, займет много времени. Поток сети Форда-Фулкерсона занимает O (EV) времени (на графике, который вы бы использовали для этого), и существует O (V ^ 2) пар узлов для проверки. Таким образом, в наихудшем случае время составляет ок. O(V ^ 5).