108
правок
Изменения
создание статьи
{{Определение
|definition = Матрицей Татта (W.D.Tutte) для орграфа <tex>G</tex> с <tex>n</tex> вершинами называется матрица размера <tex>n \times n</tex>
<tex>A_{ij} =
\begin{cases}
E_{ij}\text{, edge $(i,j)$ exists;}\\
- E_{ij}\text{, edge $(j,i)$ exists;}\\
0\text{, else.}
\end{cases}
</tex> где <tex>E_{ij}</tex> - независимые переменные
}}
Заметим, что для неориентированного графа <tex>G</tex> матрицей Татта называется матрица орграфа <tex>G'</tex>, полученного из <tex>G</tex> произвольной ориентацией рёбер.
{{Определение
|definition = Совершенным паросочетанием в графе <tex>G</tex> называется паросочетание, покрывающее все вершины <tex>G</tex>
}}
{{Теорема
|statement = В графе <tex>G</tex> существует совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для <tex>G</tex> не равен нулю
|proof =
<tex>det(A_{ij}) = \sum\limits_\phi sign(\phi)E_{1\phi(1)}E_{2\phi(2)}...E_{n\phi(n)}</tex>
<br>
Пусть <tex>\Phi = \{\forall\phi | A_{1\phi(1)}A_{2\phi(2)}...A_{n\phi(n)} \ne 0\}</tex>
<br>
Любой перестановке <tex>\chi \in \Phi</tex> соответствует орграф <tex>G_{\chi}</tex>, для любой вершины которого <tex>deg^+=deg^-=1</tex>
<br>
Если <tex>\exists G_\chi :</tex> все циклы в нём чётной длины, то совершенное паросочетание в <tex>G</tex> найдено.
<br>
В противном случае в <tex>\forall G_\chi \exists</tex> цикл нечётной длины. Рассмотрим <tex>G'_\chi</tex>, полученный из <tex>G</tex> обратной ориентацией дуг в каком-нибудь цикле нечётной длины. Заметим, что <tex>\forall G'_\chi</tex> соответствует <tex>\chi' \in \Phi</tex>. При этом <tex>sign(\chi)</tex> = <tex>sign(\chi')</tex>, так как одна получается из другой за чётное число транспозиций. Однако <tex>\sum\limits_\chi A_{1\chi(1)}A_{2\chi(2)}...A_{n\chi(n)}</tex> = <tex>- \sum\limits_{\chi'} A_{1\chi'(1)}A_{2\chi'(2)}...A_{n\chi'(n)}</tex>, так как перенаправлено было нечётное число рёбер.
Таким образом, для <tex>\forall \chi,\chi'</tex> слагаемые, соответствующие им в выражении для <tex>det(A_{ij})</tex> сократятся. А так как в нём все слагаемые либо нулевые, либо <tex>\in \Phi</tex>, то <tex>det(A_{ij}) = 0</tex>
}}
Для случая, когда <tex>G</tex> - двудольный, существует более простая форма записи матрицы Татта.
{{Определение
|definition = Матрицей Эдмондса для двудольного графа <tex>G</tex> с размерами долей <tex>n</tex>,<tex>m</tex> называется матрица размера <tex>n \times m</tex>
<tex>D_{ij} =
\begin{cases}
E_{ij}\text{, edge $(i,j)$ exists;}\\
0\text{, else.}
\end{cases}
</tex> где <tex>E_{ij}</tex> - независимые переменные
}}
{{Теорема
|statement = Ранг матрицы Эдмондса для графа <tex>G</tex> совпадает с размером максимального паросочетания в этом графе
|proof = Рангом матрицы называется количество линейно независимых строчек/столбцов в ней. Или, что эквивалентно, размер наибольшего ненулевого минора.
Рассмотрим этот максимальный минор <tex>A_M</tex>. На нём матрицу Эдмондса легко дополнить до матрицы Татта, причём её определитель, очевидно, останется ненулевым. По ранее доказанной теореме, в графе, соответствующем <tex>A_M</tex> существует совершенное паросочетание, то есть покрывающее все его вершины. То есть мощности, равной размеру <tex>A_M</tex>.
Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем <tex>A_M</tex>, что невозможно в силу выбора <tex>A_M</tex> максимальным.
}}
|definition = Матрицей Татта (W.D.Tutte) для орграфа <tex>G</tex> с <tex>n</tex> вершинами называется матрица размера <tex>n \times n</tex>
<tex>A_{ij} =
\begin{cases}
E_{ij}\text{, edge $(i,j)$ exists;}\\
- E_{ij}\text{, edge $(j,i)$ exists;}\\
0\text{, else.}
\end{cases}
</tex> где <tex>E_{ij}</tex> - независимые переменные
}}
Заметим, что для неориентированного графа <tex>G</tex> матрицей Татта называется матрица орграфа <tex>G'</tex>, полученного из <tex>G</tex> произвольной ориентацией рёбер.
{{Определение
|definition = Совершенным паросочетанием в графе <tex>G</tex> называется паросочетание, покрывающее все вершины <tex>G</tex>
}}
{{Теорема
|statement = В графе <tex>G</tex> существует совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для <tex>G</tex> не равен нулю
|proof =
<tex>det(A_{ij}) = \sum\limits_\phi sign(\phi)E_{1\phi(1)}E_{2\phi(2)}...E_{n\phi(n)}</tex>
<br>
Пусть <tex>\Phi = \{\forall\phi | A_{1\phi(1)}A_{2\phi(2)}...A_{n\phi(n)} \ne 0\}</tex>
<br>
Любой перестановке <tex>\chi \in \Phi</tex> соответствует орграф <tex>G_{\chi}</tex>, для любой вершины которого <tex>deg^+=deg^-=1</tex>
<br>
Если <tex>\exists G_\chi :</tex> все циклы в нём чётной длины, то совершенное паросочетание в <tex>G</tex> найдено.
<br>
В противном случае в <tex>\forall G_\chi \exists</tex> цикл нечётной длины. Рассмотрим <tex>G'_\chi</tex>, полученный из <tex>G</tex> обратной ориентацией дуг в каком-нибудь цикле нечётной длины. Заметим, что <tex>\forall G'_\chi</tex> соответствует <tex>\chi' \in \Phi</tex>. При этом <tex>sign(\chi)</tex> = <tex>sign(\chi')</tex>, так как одна получается из другой за чётное число транспозиций. Однако <tex>\sum\limits_\chi A_{1\chi(1)}A_{2\chi(2)}...A_{n\chi(n)}</tex> = <tex>- \sum\limits_{\chi'} A_{1\chi'(1)}A_{2\chi'(2)}...A_{n\chi'(n)}</tex>, так как перенаправлено было нечётное число рёбер.
Таким образом, для <tex>\forall \chi,\chi'</tex> слагаемые, соответствующие им в выражении для <tex>det(A_{ij})</tex> сократятся. А так как в нём все слагаемые либо нулевые, либо <tex>\in \Phi</tex>, то <tex>det(A_{ij}) = 0</tex>
}}
Для случая, когда <tex>G</tex> - двудольный, существует более простая форма записи матрицы Татта.
{{Определение
|definition = Матрицей Эдмондса для двудольного графа <tex>G</tex> с размерами долей <tex>n</tex>,<tex>m</tex> называется матрица размера <tex>n \times m</tex>
<tex>D_{ij} =
\begin{cases}
E_{ij}\text{, edge $(i,j)$ exists;}\\
0\text{, else.}
\end{cases}
</tex> где <tex>E_{ij}</tex> - независимые переменные
}}
{{Теорема
|statement = Ранг матрицы Эдмондса для графа <tex>G</tex> совпадает с размером максимального паросочетания в этом графе
|proof = Рангом матрицы называется количество линейно независимых строчек/столбцов в ней. Или, что эквивалентно, размер наибольшего ненулевого минора.
Рассмотрим этот максимальный минор <tex>A_M</tex>. На нём матрицу Эдмондса легко дополнить до матрицы Татта, причём её определитель, очевидно, останется ненулевым. По ранее доказанной теореме, в графе, соответствующем <tex>A_M</tex> существует совершенное паросочетание, то есть покрывающее все его вершины. То есть мощности, равной размеру <tex>A_M</tex>.
Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем <tex>A_M</tex>, что невозможно в силу выбора <tex>A_M</tex> максимальным.
}}
