Дискретные математики: проверить связь графика после удаления вершины? Эффективный путь?

Question

Во-первых: я признаю, что его часть конкурса программирования (где бездельники на карту, чтобы выиграть или что-то)

Я пришел к следующему выводу после прочтения проблемы & попытался следующий алгоритм.

неориентированный связный граф n вершин,

count = 0 
For i=1 to n: 
    remove(ith vertex) 
    check for connectivity of graph with remaining vertices 
    if connected 
    then increment count 
    attach the removed vertex back 
print count 

Я реализовал это двумя способами: (1) БРВ (2) Disjoint-Set Союз, но ни один из алгоритмов достаточно эффективными, чтобы получить AC , Существуют ли еще лучшие способы сделать это? Я не нуждаюсь в подробных объяснениях, мало слов сделаю, отдохну, я выясню или умру, пытаясь: p. Спасибо!

Answer 1

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

Более умный подход может заключаться в создании остовного дерева. Каждый лист на этом дереве можно удалить, не отсоединяя остальную часть графика, так как остальная часть дерева все еще соединяет все остальное. Построение одного дерева позволяет пропустить листья от индивидуального обследования. Вы даже можете построить больше деревьев, чтобы попытаться получить некоторые из других узлов (не-листья), чтобы они были листьями (которые затем можно пропустить). BFS с нескольких узлов может начать работу.

Кроме того, когда вы имитируете удаление 1 узла, вам нужно только проверить, все ли его соседи все еще связаны друг с другом. Если соседи подключены, то остальная часть графика также связана. Если граф плотный, это должно ограничивать работу на узел.

Answer 2

Вершина, удаление которой приводит к отключению графика, называется точкой сочленения. Все articulation points in a graph can be found in linear time.