4551
правка
Разрывающее множество вершин на неориентированном графе: различия между версиями
Перейти к навигации
Перейти к поиску
м
Разрывающее множество вершин на неориентированном графе (посмотреть исходный код)
Версия от 17:46, 13 июля 2016
, 13 июля 2016→Основные результаты
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
Подпрограмма сжатия | Подпрограмма сжатия, представленная в [6, 10], работает следующим образом: | ||
1 Рассмотрим все возможные разбиения (X, Y), имеющие размер (k + 1), для разрывающего множества вершин F с <math>|X| \le k \;</math> в предположении, что множество X полностью содержится в новом разрывающем множестве F' размера k и что <math>Y \cap F' = \empty \;</math>. | 1 Рассмотрим все возможные разбиения (X, Y), имеющие размер (k + 1), для разрывающего множества вершин F с <math>|X| \le k \;</math> в предположении, что множество X полностью содержится в новом разрывающем множестве F' размера k и что <math>Y \cap F' = \empty \;</math>. | ||