4551
правка
Разрывающее множество вершин на неориентированном графе: различия между версиями
Перейти к навигации
Перейти к поиску
м
Разрывающее множество вершин на неориентированном графе (посмотреть исходный код)
Версия от 17:49, 13 июля 2016
, 13 июля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
• Если существует вершина степени 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, и добавить ее к любому разрывающему множеству вершин для сокращенного экземпляра. | • Если существует вершина степени 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 сокращенного графа, размер которого не превышает k — |X|, проверим, можно ли добавить S к X для образования разрывающего множества вершин входного графа. Если такое множество вершин существует, вывести его вместе с X в качестве нового разрывающего множества вершин размера k. | ||