E066. Матрица Татта

Источник: e-maxx.ru/algo, страница PDF 200.

Матрица Татта — это изящный подход к решению задачи о паросочетании в произвольном (не обязательно двудольном) grafoе. Правда, в простом виде Algoritmo не выдаёт сами рёбра, Entradaящие в паросочетание, а только размер максимального паросочетания в grafoе. Ниже мы сначала рассмотрим результат, полученный Таттом (Tutte) для проверки существования

совершенного паросочетания (т.е. паросочетания, содержащего

рёбер, и потому насыщающего все

вершин). После этого мы рассмотрим результат, полученный позже Ловасом (Lovasz), который уже позволяет искать размер максимального паросочетания, а не только ограничивается случаем совершенного паросочетания. Затем приводится результат Рабина (Rabin) и Вазирани (Vazirani), которые указали Algoritmo восстановления самого паросочетания (как набора Entradaящих в него рёбер).

Definición

Пусть дан grafo

с

vertexми (

— чётно).

Тогда матрицей Татта (Tutte) называется следующая матрица

:

где

(

) — это либо независимая переменная, соответствующая ребру между vertexми

и

,

либо тождественный ноль, если ребра между этими vertexми нет.

Таким образом, в случае полного grafoа с

vertexми матрица Татта содержит

независимых переменных, если же в grafoе какие-то рёбра отсутствуют, то соответствующие elementы матрицы Татта превращаются в нули. Вообще, number переменных в матрице Татта совпадает с numberм рёбер grafoа. Матрица Татта антисимметрична (кососимметрична).

Теорема Татта

Рассмотрим определитель

матрицы Татта. Это, вообще говоря, многочлен относительно переменных .

Теорема Татта гласит: в grafoе

существует совершенное паросочетание тогда и только тогда, когда

многочлен

не равен нулю тождественно (т.е. имеет хотя бы одно слагаемое с ненулевым коэффициентом). Напомним, что паросочетание называется совершенным, если оно насыщает все вершины, т.е.

его мощность равна

. Канадский математик Вильям Томас Татт (William Thomas Tutte) первым указал на тесную связь между паросочетаниями в grafoах и определителями матриц (1947 г.). Более простой вид этой связи позже обнаружил Эдмондс (Edmonds) в случае двудольных grafoов (1967 г.). Рандомизированные Algoritmoы для нахождения величины максимального паросочетания и самих рёбер этого паросочетания были предложены позже, соответственно, Ловасом (Lovasz) (в 1979 г.), и Рабином (Rabin) и Вазирани (Vazirani) (в 1984 г.).

Практическое применение: рандомизированный Algoritmo

Непосредственно применять теорему Татта даже в задаче проверки существования совершенного паросочетания нецелесообразно. Причиной этого является то, что при символьном вычислении определителя (т.е. в

виде многочленов над переменными

) промежуточные результаты являются многочленами, содержащими

переменных. Поэтому вычисление определителя матрицы Татта в символьном виде потребует неоправданно много времени. Венгерский математик Ласло Ловас (Laszlo Lovasz) был первым, указавшим возможность Applications здесь рандомизированного Algoritmoа для упрощения вычислений.

Идея очень проста: заменим все переменные

случайными числами:

Тогда, если полином

был тождественно нулевым, после такой замены он и будет оставаться нулевым; если же он был отличным от нуля, то при такой случайной numberвой замене вероятность того, что он обратится в ноль, достаточно мала. Понятно, что такой тест (подстановка случайных значений и вычисление определителя

) если и ошибается,

то только в одну сторону: может сообщить об отсутствии совершенного паросочетания, когда на самом деле оно существует. Мы можем повторить этот тест несколько раз, подставляя в качестве значений переменных новые случайные числа, и с каждым повторным запуском мы получаем всё большую уверенность в том, что тест выдал правильный ответ. На практике в большинстве случаев достаточно одного теста, чтобы определить, есть ли в grafoе совершенное паросочетание или нет; несколько таких тестов дают уже весьма высокую вероятность. Для оценки вероятности ошибки можно использовать лемму Шварца-Зиппеля (Schwartz–Zippel), которая

гласит, что вероятность обращения в ноль ненулевого полинома

-ой степени при подстановке в качестве

значений переменных случайных чисел, каждое из которых может принимать

вариантов значения, — эта

вероятность удовлетворяет неравенству: НаEjemplo, при использовании стандартной функции случайных чисел C++

получаем, что эта вероятность

при

составляет около процента.

Asymptotic complexity решения получается равной

(с использованием, наEjemplo, Algoritmoа Гаусса), умноженное

на количество итераций теста. Стоит отметить, что по асимптотике такое Solución значительно отстаёт от решения Algoritmoом Эдмондса сжатия цветков, однако в некоторых случаях более предпочтительно из-за простоты реализации. Восстановить само совершенное паросочетание как набор рёбер является более сложной задачей. Самым простым, хотя и медленным, вариантом будет восстановление этого паросочетания по одному ребру: перебираем первое edge ответа, выбираем его так, чтобы в оставшемся grafoе существовало совершенное паросочетание, и т.д.

Prueba теоремы Татта

Чтобы хорошо понять Prueba этой теоремы, сначала рассмотрим более простой результат, — полученный Эдмондсом для случая двудольных grafoов.

Теорема Эдмондса

Рассмотрим двудольный grafo, в каждой доле которого по

вершин. Составим матрицу

, в которой, по

аналогии с матрицей Татта,

является отдельной независимой переменной, если edge

присутствует в grafoе,

и является тождественным нулём в противном случае. Эта матрица похожа на матрицу Татта, однако матрица Эдмондса имеет вдвое меньшую разность, и каждому ребру здесь соответствует только одна ячейка матрицы.

Докажем следующую теорему: определитель

отличен от нуля тогда и только тогда, когда в

двудольном grafoе существует совершенное паросочетание. Prueba. Распишем определитель согласно его определению, как сумма по всем перестановкам:

Заметим, что поскольку все ненулевые elementы матрицы

— различные независимые переменные, то в этой

сумме все ненулевые слагаемые различны, а потому никаких сокращений в процессе суммирования не происходит. Осталось заметить, что любое ненулевое слагаемое в этой сумме означает непересекающийся по vertexм набор рёбер, т.е. некоторое совершенное паросочетание. И наоборот, любому совершенному паросочетанию соответствует ненулевое слагаемое в этой сумме. Вкупе с вышесказанным это доказывает теорему.

Свойства антисимметричных матриц

Для доказательства теоремы Татта необходимо воспользоваться несколькими известными фактами линейной алгебры о свойствах антисимметричных матриц. Во-первых (этот факт нам не пригодится, но он интересен сам по себе), если антисимметричная матрица имеет нечётный размер, то её определитель всегда равен нулю (теорема Якоби (Jacobi)). Для этого достаточно

заметить, что антисимметричная матрица удовлетворяет равенству

, и теперь получаем цепочку равенств:

откуда и следует, что при нечётных

определитель необходимо должен быть равен нулю. Во-вторых, оказывается, что в случае антисимметричных матриц чётного размера их определитель всегда можно записать как квадрат некоторого полинома относительно переменных-elementов этой матрицы (полином называется пфаффианом (pfaffian), а результат принадлежит Мьюру (Muir)): В-третьих, этот пфаффиан представляет собой не произвольный многочлен, а сумму вида: Таким образом, каждое слагаемое в пфаффиане — это произведение таких

elementов матрицы, что их индексы

в совокупности представляют собой разбиение множества

на

пар. Перед каждым слагаемым имеется

свой коэффициент, но его вид нас здесь не интересует.

Prueba теоремы Татта

Воспользовавшись вторым и третьим свойством из предыдущего пункта, мы получаем, что определитель матрицы Татта представляет собой квадрат от суммы слагаемых такого вида, что каждое слагаемое — произведение elementов матрицы, индексы которых не повторяются и покрывают все номера от

до

. Таким образом, снова, как и в доказательстве теоремы Эдмондса, каждое ненулевое слагаемое этой суммы соответствует совершенному паросочетанию в grafoе, и наоборот.

Теорема Ловаса: обобщение для поиска

размера максимального паросочетания

Формулировка

Ранг матрицы Татта совпадает с удвоенной величиной максимального паросочетания в данном grafoе.

Применение

Для Applications этой теоремы на практике можно воспользоваться тем же самым приёмом рандомизации, что и в вышеописанном Algoritmoе для матрицы Татта, а именно: подставить вместо переменных случайные значения, и find ранг полученной numberвой матрицы. Ранг матрицы, опять же, ищется за

с помощью

модифицированного Algoritmoа Гаусса, см. здесь. Впрочем, следует отметить, что приведённая в предыдущем Algoritmoе лемма Шварца-Зиппеля неприменима в явном виде, и интуитивно кажется, что вероятность ошибки здесь становится выше. Однако утверждается (см. работы Ловаса (Lovasz)), что и здесь вероятность ошибки (т.е. того, что ранг полученной матрицы окажется меньше, чем удвоенный размер максимального паросочетания) не превосходит

(где

, как и выше, обозначает

размер множества, из которого выбираются случайные числа).

Prueba

Prueba будет вытекать из одного свойства, известного из линейной алгебры. Пусть дана

антисимметричная матрица

размера

, и пусть множества

и

— любые два подмножества

множества

, причём размеры этих множеств совпадают. Обозначим через

матрицу, полученную из

только cadenaми с номерами из

и столбцами с номерами из

. Тогда выполняется: Покажем, как это свойство позволяет установить соответствие между рангом матрицы Татта

и

величиной максимального паросочетания.

С одной стороны, рассмотрим в grafoе

некоторое максимальное паросочетание, и обозначим множество

насыщаемых им вершин через

. Тогда определитель

отличен от нуля (по теореме Татта). Следователь, ранг матрицы Татта как минимум не меньше удвоенной величины максимального паросочетания.

В обратную сторону, пусть ранг матрицы

равен

. Это означает, что нашлась такая подматрица

,

где

, определитель которой отличен от нуля. Но по приведённому выше свойству это означает, что

одна из матриц

,

имеет ненулевой определитель, что по теореме Татта означает, что в

подgrafoе, индуцированном множеством вершин

или

, имеется совершенное паросочетание (и величина го

равна

). Следовательно, ранг матрицы не может быть больше величины максимального паросочетания, что и завершает Prueba теоремы.

Algoritmo Рабина-Вазирани нахождения

максимального паросочетания

Этот Algoritmo является дальнейшим обобщением двух предыдущих теорем, и позволяет, в отличие от них, выдавать не только величину максимального паросочетания, но и сами рёбра, Entradaящие в него.

Формулировка теоремы

Пусть в grafoе существует совершенное паросочетание. Тогда его матрица Татта невырождена, т.е. . Сгенерируем по ней, как было описано выше, случайную numberвую матрицу

. Тогда, с

высокой вероятностью,

тогда и только тогда, когда edge

Entradaит в какое-либо

совершенное паросочетание.

(Здесь через

обозначена матрица, обратная к

. Предполагается, что определитель матрицы

отличен от

нуля, поэтому обратная матрица существует.)

Применение

Эту теорему можно применять для восстановления самих рёбер максимального паросочетания. Сначала придётся выделить подgrafo, в котором содержится искомое максимальное паросочетание (это можно сделать параллельно с Algoritmoом поиска ранга матрицы). После этого Tarea сводится к поиску совершенного паросочетания по данной numberвой матрице, полученной из матрицы Татта. Здесь мы уже применяем теорему Рабина-Вазирани, — находим обратную матрицу (что можно

сделать модифицированным Algoritmoом Гаусса за

), находим в ней любой ненулевой element, удаляем из

grafoа, и повторяем процесс. Asymptotic complexity такого решения будет не самой быстрой —

, зато взамен

получаем простоту решения (по сравнению, наEjemplo, с Algoritmoом Эдмондса сжатия цветков).

Prueba теоремы

Вспомним известную формулу для elementов обратной матрицы

:

где через

обозначено алгебраическое дополнение, т.е. это number

, умноженное на

определитель матрицы, получаемой из

удалением

-й строки и

-го столбца.

Отсюда сразу получаем, что element

отличен от нуля тогда и только тогда, когда матрица

с вычеркнутыми

-ой строкой и

-ым столбцом имеет ненулевой определитель, что, применяя теорему Татта, означает с

высокой вероятностью, что в grafoе без вершин

и

по-прежнему существует совершенное паросочетание.

References

● William Thomas Tutte. The Factorization of Linear Graphs [1946]

● Laszlo Lovasz. On Determinants, Matchings and Random Algorithms [1979]

● Laszlo Lovasz, M.D. Plummer. Matching Theory [1986]

● Michael Oser Rabin, Vijay V. Vazirani. Maximum matchings in general graphs

through randomization [1989]

● Allen B. Tucker. Computer Science Handbook [2004]

● Rajeev Motwani, Prabhakar Raghavan. Randomized Algorithms [1995]

● A.C. Aitken. Determinants and matrices [1944]

// C# draft for: Матрица Татта
// Original e-maxx article has no compact code listing in the extracted PDF text.

// C++ source for: Матрица Татта
// Compact code block was not extracted from this article.

// Java draft for: Матрица Татта
// Original e-maxx article has no compact code listing in the extracted PDF text.