MAXimal

добавлено: 16 Sep 2010 17:09
редактировано: 2 Nov 2012 18:32

Матрица Татта

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

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

Определение

Пусть дан граф G с n вершинами (n — чётно).

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

\pmatrix{ 0 & x_{12} & x_{13} & \ldots & x_{1(n-[...]

где x_{ij} (1 \le i < j \le n) — это либо независимая переменная, соответствующая ребру между вершинами i и j, либо тождественный ноль, если ребра между этими вершинами нет.

Таким образом, в случае полного графа с n вершинами матрица Татта содержит n (n-1) / 2 независимых переменных, если же в графе какие-то рёбра отсутствуют, то соответствующие элементы матрицы Татта превращаются в нули. Вообще, число переменных в матрице Татта совпадает с числом рёбер графа.

Матрица Татта антисимметрична (кососимметрична).

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

Рассмотрим определитель \det(A) матрицы Татта. Это, вообще говоря, многочлен относительно переменных x_{ij}.

Теорема Татта гласит: в графе G существует совершенное паросочетание тогда и только тогда, когда многочлен \det(A) не равен нулю тождественно (т.е. имеет хотя бы одно слагаемое с ненулевым коэффициентом). Напомним, что паросочетание называется совершенным, если оно насыщает все вершины, т.е. его мощность равна n/2.

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

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

Непосредственно применять теорему Татта даже в задаче проверки существования совершенного паросочетания нецелесообразно. Причиной этого является то, что при символьном вычислении определителя (т.е. в виде многочленов над переменными x_{ij}) промежуточные результаты являются многочленами, содержащими O(n^2) переменных. Поэтому вычисление определителя матрицы Татта в символьном виде потребует неоправданно много времени.

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

Идея очень проста: заменим все переменные x_{ij} случайными числами:

x_{ij} = {\rm rand}().

Тогда, если полином \det(A) был тождественно нулевым, после такой замены он и будет оставаться нулевым; если же он был отличным от нуля, то при такой случайной числовой замене вероятность того, что он обратится в ноль, достаточно мала.

Понятно, что такой тест (подстановка случайных значений и вычисление определителя \det(A)) если и ошибается, то только в одну сторону: может сообщить об отсутствии совершенного паросочетания, когда на самом деле оно существует.

Мы можем повторить этот тест несколько раз, подставляя в качестве значений переменных новые случайные числа, и с каждым повторным запуском мы получаем всё большую уверенность в том, что тест выдал правильный ответ. На практике в большинстве случаев достаточно одного теста, чтобы определить, есть ли в графе совершенное паросочетание или нет; несколько таких тестов дают уже весьма высокую вероятность.

Для оценки вероятности ошибки можно использовать лемму Шварца-Зиппеля (Schwartz–Zippel), которая гласит, что вероятность обращения в ноль ненулевого полинома P k-ой степени при подстановке в качестве значений переменных случайных чисел, каждое из которых может принимать s вариантов значения, — эта вероятность удовлетворяет неравенству:

{\rm Pr}[P(r_1,\ldots,r_k)=0] \le \frac{k}{s}.

Например, при использовании стандартной функции случайных чисел C++ \rm rand() получаем, что эта вероятность при n=300 составляет около процента.

Асимптотика решения получается равной O(n^3) (с использованием, например, алгоритма Гаусса), умноженное на количество итераций теста. Стоит отметить, что по асимптотике такое решение значительно отстаёт от решения алгоритмом Эдмондса сжатия цветков, однако в некоторых случаях более предпочтительно из-за простоты реализации.

Восстановить само совершенное паросочетание как набор рёбер является более сложной задачей. Самым простым, хотя и медленным, вариантом будет восстановление этого паросочетания по одному ребру: перебираем первое ребро ответа, выбираем его так, чтобы в оставшемся графе существовало совершенное паросочетание, и т.д.

Доказательство теоремы Татта

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

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

Рассмотрим двудольный граф, в каждой доле которого по n вершин. Составим матрицу B n \times n, в которой, по аналогии с матрицей Татта, b_{ij} является отдельной независимой переменной, если ребро (i,j) присутствует в графе, и является тождественным нулём в противном случае.

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

Докажем следующую теорему: определитель \det(B) отличен от нуля тогда и только тогда, когда в двудольном графе существует совершенное паросочетание.

Доказательство. Распишем определитель согласно его определению, как сумма по всем перестановкам:

\det(B) = \sum_{\pi \in S_n} {\rm sgn}(\pi) \cdot[...]

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

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

Для доказательства теоремы Татта необходимо воспользоваться несколькими известными фактами линейной алгебры о свойствах антисимметричных матриц.

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

\det(A) = \det(A^T) = \det(-A) = (-1)^n \det(A),

откуда и следует, что при нечётных n определитель необходимо должен быть равен нулю.

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

\det(A) = {\rm Pf}^2(A).

В-третьих, этот пфаффиан представляет собой не произвольный многочлен, а сумму вида:

{\rm Pf}(A) = \frac{ 1 }{ 2^n n! } \sum_{\pi \in [...]

Таким образом, каждое слагаемое в пфаффиане — это произведение таких n/2 элементов матрицы, что их индексы в совокупности представляют собой разбиение множества n на n/2 пар. Перед каждым слагаемым имеется свой коэффициент, но его вид нас здесь не интересует.

Доказательство теоремы Татта

Воспользовавшись вторым и третьим свойством из предыдущего пункта, мы получаем, что определитель \det(A) матрицы Татта представляет собой квадрат от суммы слагаемых такого вида, что каждое слагаемое — произведение элементов матрицы, индексы которых не повторяются и покрывают все номера от 1 до n. Таким образом, снова, как и в доказательстве теоремы Эдмондса, каждое ненулевое слагаемое этой суммы соответствует совершенному паросочетанию в графе, и наоборот.

Теорема Ловаса: обобщение для поиска размера максимального паросочетания

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

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

Применение

Для применения этой теоремы на практике можно воспользоваться тем же самым приёмом рандомизации, что и в вышеописанном алгоритме для матрицы Татта, а именно: подставить вместо переменных случайные значения, и найти ранг полученной числовой матрицы. Ранг матрицы, опять же, ищется за O (n^3) с помощью модифицированного алгоритма Гаусса, см. здесь.

Впрочем, следует отметить, что приведённая выше лемма Шварца-Зиппеля неприменима в явном виде, и интуитивно кажется, что вероятность ошибки здесь становится выше. Однако утверждается (см. работы Ловаса (Lovasz)), что и здесь вероятность ошибки (т.е. того, что ранг полученной матрицы окажется меньше, чем удвоенный размер максимального паросочетания) не превосходит \frac{n}{s} (где s, как и выше, обозначает размер множества, из которого выбираются случайные числа).

Доказательство

Доказательство будет вытекать из теоремы линейной алгебры, известной как теорема Фробениуса (Frobenius). Пусть дана антисимметричная матрица A размера n \times n, и пусть множества S и T — любые два подмножества множества \{ 1, \ldots, n \}, причём размеры этих множеств совпадают и равны рангу матрицы A. Обозначим через A_{XY} матрицу, полученную из матрицы A только строками с номерами из множества X и столбцами с номерами из множества Y (где X и Y — некоторые подмножества множества \{ 1, \ldots, n \}). Тогда выполняется:

\det(A_{SS}) \cdot \det(A_{TT}) = \det(A_{ST}) \c[...]

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

С одной стороны, рассмотрим в графе G некоторое максимальное паросочетание, и обозначим множество насыщаемых им вершин через U. Тогда, согласно теореме Татта, определитель \det(A_{UU}) отличен от нуля. Следователь, ранг матрицы Татта — как минимум 2|U|, т.е. не меньше удвоенной величины максимального паросочетания.

Покажем теперь обратное неравенство. Обозначим ранг матрицы A через r. Это означает, что нашлась такая подматрица A_{ST}, где |S| = |T| = r, определитель которой отличен от нуля. Легко заметить, что A_{TS} также будет отлично от нуля. Но по приведённой выше теореме Фробениуса это означает, что обе матрицы A_{SS} и A_{TT} имеют ненулевой определитель. Отсюда следует, что r чётно (потому что, как было отмечено выше, антисимметричная матрица нечётной размерности всегда имеет нулевой определитель). Таким образом, мы можем применить к подматрице A_{SS} (или A_{TT}) теорему Татта. Следовательно, в подграфе, индуцированном множеством вершин S (или множеством вершин T), имеется совершенное паросочетание (и величина его равна r/2). Таким образом, ранг матрицы Татта не может быть больше удвоенной величины максимального паросочетания.

Объединяя два доказанных неравенства, мы получаем утверждение теоремы: ранг матрицы Татта совпадает с удвоенной величиной максимального паросочетания.

Алгоритм Рабина-Вазирани нахождения максимального паросочетания

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

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

Пусть в графе существует совершенное паросочетание. Тогда его матрица Татта невырождена, т.е. \det(A) \ne 0. Сгенерируем по ней, как было описано выше, случайную числовую матрицу B. Тогда, с высокой вероятностью, (B^{-1})_{ji} \ne 0 тогда и только тогда, когда ребро (i,j) входит в какое-либо совершенное паросочетание.

(Здесь через B^{-1} обозначена матрица, обратная к B. Предполагается, что определитель матрицы B отличен от нуля, поэтому обратная матрица существует.)

Применение

Эту теорему можно применять для восстановления самих рёбер максимального паросочетания. Сначала придётся выделить подграф, в котором содержится искомое максимальное паросочетание (это можно сделать параллельно с алгоритмом поиска ранга матрицы).

После этого задача сводится к поиску совершенного паросочетания по данной числовой матрице, полученной из матрицы Татта. Здесь мы уже применяем теорему Рабина-Вазирани, — находим обратную матрицу (что можно сделать модифицированным алгоритмом Гаусса за O (n^3)), находим в ней любой ненулевой элемент, удаляем из графа, и повторяем процесс. Асимптотика такого решения будет не самой быстрой — O (n^4), зато взамен получаем простоту решения (по сравнению, например, с алгоритмом Эдмондса сжатия цветков).

Доказательство теоремы

Вспомним известную формулу для элементов обратной матрицы B^{-1}:

(B^{-1})_{ji} = \frac{ {\rm adj}(B)_{i,j} }{ \det[...]

где через {\rm adj}(B)_{i,j} обозначено алгебраическое дополнение, т.е. это число (-1)^{i+j}, умноженное на определитель матрицы, получаемой из B удалением i-й строки и j-го столбца.

Отсюда сразу получаем, что элемент (B^{-1})_{ji} отличен от нуля тогда и только тогда, когда матрица B с вычеркнутыми i-ой строкой и j-ым столбцом имеет ненулевой определитель, что, применяя теорему Татта, означает с высокой вероятностью, что в графе без вершин i и j по-прежнему существует совершенное паросочетание.

Литература