E-maxx_algo - Страница 21
Тогава ако полиномът
е идентично нула, след такава замяна ще остане нула; ако
ако беше ненулево, тогава с такова заместване на случайно число вероятността да се превърне в
нула, достатъчно малка.
Ясно е, че такъв тест (заместване на случайни стойности и изчисляване на детерминанта
), ако е погрешно,
тогава само в една посока: той може да съобщи за липсата на перфектно съвпадение, когато в действителност съществува.
Можем да повторим този тест няколко пъти, като заместим новите произволни числа за стойностите на променливите и с всеки повторен цикъл получаваме все повече увереност, че тестът е дал верния отговор.
На практика в повечето случаи е достатъчен един тест, за да се определи дали графиката има перфектно съвпадение или не; няколко такива теста вече дават много голяма вероятност.
За да се изчисли вероятността от грешка, може да се използва лемата на Schwartz-Zippel, която гласи, че вероятността от ненулев полином от степента да изчезне при заместване на случайни числа като стойности на променливи, всяка от които може да приеме стойности, - тази вероятност удовлетворява неравенството:
Например, когато се използва стандартната функция за произволни числа C++
получаваме, че тази вероятност
е около процент.
Асимптотиката на решението се оказва
(използвайки например алгоритъма на Гаус), умножено по
по броя на итерациите на теста. Трябва да се отбележи, че в асимптотиката такова решение значително изостава от решението на алгоритъма на Edmonds за компресия на цветя, но в някои случаи е по-предпочитано, тъй като
Реконструирането на идеалното съвпадение като набор от ръбове е по-трудна задача. Най-простият, макар и най-бавен вариант е да възстановите това съвпадение по един ръб наведнъж: прегледайте първия ръб на отговора, изберете го така, че да съществува перфектно съвпадение в останалата графика и т.н.
Доказателство за теоремата на Тут
За да разберем добре доказателството на тази теорема, първо разглеждаме по-прост резултат, получен от Едмъндс за случая на двуделни графи.
Помислете за двуделна графика с върхове във всяка част. Нека съставим матрица, в която по аналогия с матрицата на Тут тя е отделна независима променлива, ако в графата има ръб,
и в противен случай е идентична нула.
Тази матрица е подобна на матрицата на Tutt, но матрицата на Edmonds има половината разлика и всеки ръб тук съответства само на една клетка на матрицата.