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