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

Корректность подпрограммы сжатия следует из ее прямолинейной природы и из корректности двух правил редукции данных, доказать которую несложно. Сложнее всего доказать, что время выполнения подпрограммы сжатия составляет <math>O(c^k \cdot m) \;</math>: существует <math>2^k + 1 \;</math> разбиений множества F на вышеупомянутые подмножества (X, Y); можно показать, что для каждого разбиения сокращенный граф после выполнения правил редукции данных имеет не более <math>d \cdot k \;</math> вершин для константного значения d; в противном случае для этого разбиения не существует разрывающего множества вершин  размера k. Таким образом, время выполнения составляет <math>O(c^k \cdot m) \;</math>. Более детальное доказательство границы размера <math>d \cdot k \;</math> см. в [6, 10].