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

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

Версия 22:32, 22 ноября 2018

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

Определение:
Матрицей Татта (англ. 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]

См. также

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