Изменения

Перейти к: навигация, поиск
Нет описания правки
==Матрица Татта==
{{Определение
|definition = '''Матрицей Татта''' (англ. '''Tutte matrix''') для графа <tex>G</tex> с <tex>n</tex> вершинами называется матрица размера <tex>n \times n</tex>.
<mathtex>A_{ij} = \begin{cases} E_{ij}, & \;\;\mboxmathrm{edge}\;(i,j)~exist \mbox;exists\;\mathrm{ and } \;i<j\\ -E_{ji}, & \;\;\mboxmathrm{edge}\;(i,j)~exist \mbox;exists\;\mathrm{ and } \;i>j\\ 0, & \;\;\;\;\mboxmathrm{otherwise} \end{cases},</mathtex>где <tex>E_{ij}</tex> {{--- }} независимые переменные}} {{Определение|definition = '''Совершенным паросочетанием''' в графе (<tex>GE_{ij}</tex> называется паросочетаниене зависят друг от друга, покрывающее все вершины <tex>G</tex>.и могут принимать произвольные значения)
}}
{{Теорема
|statement = В графе <tex>G</tex> существует [[Паросочетания:_основные_определения,_теорема_о_максимальном_паросочетании_и_дополняющих_цепях | совершенное паросочетание ]] тогда и только тогда, когда определитель матрицы Татта для <tex>G</tex> не равен нулю тождественно.
|proof =
<tex>\det(A_{ij}A) = \sum\limits_\phi varphi \operatorname{sign}(\phivarphi)E_A_{1\phivarphi(1)}E_A_{2\phivarphi(2)}...E_\ldots A_{n\phivarphi(n)}</tex>
<br>
Пусть <tex>\Phi = \{\forall\phi varphi | A_{1\phivarphi(1)}A_{2\phivarphi(2)}...\ldots A_{n\phivarphi(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>\operatorname{sign}(\chi)</tex> = <tex>\operatorname{sign}(\chi')</tex>, так как одна получается из другой за чётное число транспозиций. Однако <tex>\sum\limits_\chi A_{1\chi(1)}A_{2\chi(2)}...\ldots A_{n\chi(n)}</tex> = <tex>- \sum\limits_{\chi'} A_{1\chi'(1)}A_{2\chi'(2)}...\ldots A_{n\chi'(n)}</tex>, так как перенаправлено было нечётное число рёбер.Таким образом, для <tex>\forall \chi,\chi'</tex> слагаемые, соответствующие им в выражении для <tex>\det(A_{ij}A)</tex> сократятся. А так как в нём все слагаемые либо нулевые, либо <tex>\in \Phi</tex>, то <tex>\det(A_{ij}A) = 0</tex>
}}
==Матрица Эдмондса==
Для случая, когда <tex>G</tex> {{- --}} [[Основные_определения_теории_графов#.D0.A7.D0.B0.D1.81.D1.82.D0.BE_.D0.B8.D1.81.D0.BF.D0.BE.D0.BB.D1.8C.D0.B7.D1.83.D0.B5.D0.BC.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B | двудольный]], существует более простая матрица, аналогичная матрице Татта.
{{Определение
|definition = '''Матрицей Эдмондса''' (англ. '''Edmonds matrix''') для двудольного графа <tex>G</tex> с размерами долей <tex>n</tex>,<tex>m</tex> называется матрица размера <tex>n \times m</tex><mathtex> D_{ij} = \left\{ \begin{array}{llcases} E_{ij} , & \mboxmathrm{edge}\;(i,j)\;exists \\ 0 , & \;elsemathrm{otherwise} \end{arraycases},\right.</mathtex> где <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> максимальным.
}}
 
==См. также==
* [[Теорема Татта о существовании полного паросочетания]]
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Декомпозиция Эдмондса-Галлаи]]
 
==Источники информации==
*[https://en.wikipedia.org/wiki/Tutte_matrix Wikipedia {{---}} Tutte matrix]
*[https://en.wikipedia.org/wiki/Edmonds_matrix Wikipedia {{---}} Edmonds matrix]
*[http://e-maxx.ru/algo/tutte_matrix MAXimal::algo::Матрица Татта]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]
Анонимный участник

Навигация