Теорема. Предположим, что при поиске пути расширения из узла u графа G относительно совпадающего M мы обнаруживаем расцветку b. Тогда существует дополнительный путь от u в G относительно M, если только один из u (vb, если u является базисом b) в G / b относительно M / b.
Показать Например, если G = (V, E) является графом, M совпадает с G, и цветение ba (схема с 2m + 1 ребрами, m из которых находится в M), то следующее может быть неверным: является расширяющим путем в G относительно M, если в G / b есть один путь относительно M / b. Сравните с приведенной выше теоремой.
Это восьмой вопрос из главы 10 «Комбинаторной оптимизации: алгоритмы и сложность». Христос Х. Пападимитриу
Я не совсем уверен, в чем разница между эти двое. Любые советы будут оценены.