Матрица Татта и связь с размером максимального паросочетания в двудольном графе

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

Определение:

Матрицей Татта (англ. Tutte matrix) для графа [math]G[/math] с [math]n[/math] вершинами называется матрица размера [math]n \times n[/math] [math]A_{ij} = \begin{cases} E_{ij}, & \mathrm{edge}\;(i,j)\;exists\;\mathrm{and}\;i\lt j\\ -E_{ji}, & \mathrm{edge}\;(i,j)\;exists\;\mathrm{and}\;i\gt j\\ 0, & \mathrm{otherwise} \end{cases},[/math] где [math]E_{ij}[/math] — независимые переменные ([math]E_{ij}[/math] не зависят друг от друга, и могут принимать произвольные значения)

Теорема:

В графе [math]G[/math] существует совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для [math]G[/math] не равен нулю тождественно.

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

[math]\triangleright[/math]

[math]\det(A) = \sum\limits_\varphi \operatorname{sign}(\varphi)A_{1\varphi(1)}A_{2\varphi(2)} \ldots A_{n\varphi(n)}[/math] Пусть [math]\Phi = \{\forall\varphi | A_{1\varphi(1)}A_{2\varphi(2)} \ldots A_{n\varphi(n)} \ne 0\}[/math] Любой перестановке [math]\chi \in \Phi[/math] соответствует орграф [math]G_{\chi}[/math], для любой вершины которого [math]\deg^+=\deg^-=1[/math] Если [math]\exists G_\chi :[/math] все циклы в нём чётной длины, то совершенное паросочетание в [math]G[/math] найдено. В противном случае в [math]\forall G_\chi \exists[/math] цикл нечётной длины. Рассмотрим [math]G'_\chi[/math], полученный из [math]G[/math] обратной ориентацией дуг в каком-нибудь цикле нечётной длины. Заметим, что [math]\forall G'_\chi[/math] соответствует [math]\chi' \in \Phi[/math]. При этом [math]\operatorname{sign}(\chi)[/math] = [math]\operatorname{sign}(\chi')[/math], так как одна получается из другой за чётное число транспозиций. Однако [math]\sum\limits_\chi A_{1\chi(1)}A_{2\chi(2)} \ldots A_{n\chi(n)}[/math] = [math]- \sum\limits_{\chi'} A_{1\chi'(1)}A_{2\chi'(2)} \ldots A_{n\chi'(n)}[/math], так как перенаправлено было нечётное число рёбер. Таким образом, для [math]\forall \chi,\chi'[/math] слагаемые, соответствующие им в выражении для [math]\det(A)[/math] сократятся. А так как в нём все слагаемые либо нулевые, либо [math]\in \Phi[/math], то [math]\det(A) = 0[/math]

[math]\triangleleft[/math]

Матрица Эдмондса

Для случая, когда [math]G[/math] — двудольный, существует более простая матрица, аналогичная матрице Татта.

Определение:

Матрицей Эдмондса (англ. Edmonds matrix) для двудольного графа [math]G[/math] с размерами долей [math]n[/math],[math]m[/math] называется матрица размера [math]n \times m[/math] [math] D_{ij} = \begin{cases} E_{ij}, & \mathrm{edge}\;(i,j)\;exists\\ 0, & \mathrm{otherwise} \end{cases},[/math] где [math]E_{ij}[/math] — независимые переменные

Теорема:

Ранг матрицы Эдмондса для графа [math]G[/math] совпадает с размером максимального паросочетания в этом графе

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

[math]\triangleright[/math]

Рангом матрицы называется количество линейно независимых строчек/столбцов в ней. Или, что эквивалентно, размер наибольшего ненулевого минора. Рассмотрим этот максимальный минор [math]A_M[/math]. На нём матрицу Эдмондса легко дополнить до матрицы Татта, причём её определитель, очевидно, останется ненулевым. По ранее доказанной теореме, в графе, соответствующем [math]A_M[/math] существует совершенное паросочетание, то есть покрывающее все его вершины. То есть мощности, равной размеру [math]A_M[/math]. Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем [math]A_M[/math], что невозможно в силу выбора [math]A_M[/math] максимальным.

[math]\triangleleft[/math]

См. также

• Теорема Холла
• Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
• Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
• Связь вершинного покрытия и независимого множества

Источники информации

• Wikipedia — Tutte matrix
• Wikipedia — Edmonds matrix
• MAXimal::algo::Матрица Татта