Разрывающее множество вершин на неориентированном графе: различия между версиями

• Если существует вершина степени 2 с двумя соседями <math>v_1 \;</math> и <math>v_2 \;</math>, где <math>v_1 \notin Y \;</math> или <math>v_2 \notin Y \;</math>, то удалить v и соединить <math>v_1 \;</math> и <math>v_2 \;</math>. Если при этом создается второе параллельное ребро между <math>v_1 \;</math> и <math>v_2 \;</math>, удалить вершину <math>v_1 \;</math> плюс <math>v_2 \;</math>, не принадлежащую к Y, и добавить ее к любому разрывающему множеству вершин для сокращенного экземпляра. Наконец, исчерпывающим образом для каждого множества вершин S сокращенного графа, размер которого не превышает k — |X|, проверить, можно ли добавить S к X для образования разрывающего множества вершин входного графа. Если такое множество вершин существует, вывести его вместе с X в качестве нового разрывающего множества вершин размера k.