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

Материал из Викиконспекты
Перейти к: навигация, поиск
(создание статьи)
 
Строка 1: Строка 1:
 +
==Матрица Татта==
 
{{Определение
 
{{Определение
 
|definition = Матрицей Татта (W.D.Tutte) для орграфа <tex>G</tex> с <tex>n</tex> вершинами называется матрица размера <tex>n \times n</tex>
 
|definition = Матрицей Татта (W.D.Tutte) для орграфа <tex>G</tex> с <tex>n</tex> вершинами называется матрица размера <tex>n \times n</tex>
Строка 10: Строка 11:
 
}}
 
}}
 
Заметим, что для неориентированного графа <tex>G</tex> матрицей Татта называется матрица орграфа <tex>G'</tex>, полученного из <tex>G</tex> произвольной ориентацией рёбер.
 
Заметим, что для неориентированного графа <tex>G</tex> матрицей Татта называется матрица орграфа <tex>G'</tex>, полученного из <tex>G</tex> произвольной ориентацией рёбер.
 
 
{{Определение
 
{{Определение
 
|definition = Совершенным паросочетанием в графе <tex>G</tex> называется паросочетание, покрывающее все вершины <tex>G</tex>
 
|definition = Совершенным паросочетанием в графе <tex>G</tex> называется паросочетание, покрывающее все вершины <tex>G</tex>
Строка 30: Строка 30:
 
}}
 
}}
  
Для случая, когда <tex>G</tex> - двудольный, существует более простая форма записи матрицы Татта.
+
==Матрица Эдмондса==
 +
Для случая, когда <tex>G</tex> - двудольный, существует более простая матрица, аналогичная матрице Татта.
 
{{Определение
 
{{Определение
 
|definition = Матрицей Эдмондса для двудольного графа <tex>G</tex> с размерами долей <tex>n</tex>,<tex>m</tex> называется матрица размера <tex>n \times m</tex>
 
|definition = Матрицей Эдмондса для двудольного графа <tex>G</tex> с размерами долей <tex>n</tex>,<tex>m</tex> называется матрица размера <tex>n \times m</tex>

Версия 21:06, 14 декабря 2010

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

Определение:
Матрицей Татта (W.D.Tutte) для орграфа [math]G[/math] с [math]n[/math] вершинами называется матрица размера [math]n \times n[/math] [math]A_{ij} = \begin{cases} E_{ij}\text{, edge $(i,j)$ exists;}\\ - E_{ij}\text{, edge $(j,i)$ exists;}\\ 0\text{, else.} \end{cases} [/math] где [math]E_{ij}[/math] - независимые переменные

Заметим, что для неориентированного графа [math]G[/math] матрицей Татта называется матрица орграфа [math]G'[/math], полученного из [math]G[/math] произвольной ориентацией рёбер.

Определение:
Совершенным паросочетанием в графе [math]G[/math] называется паросочетание, покрывающее все вершины [math]G[/math]


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

[math]det(A_{ij}) = \sum\limits_\phi sign(\phi)E_{1\phi(1)}E_{2\phi(2)}...E_{n\phi(n)}[/math]
Пусть [math]\Phi = \{\forall\phi | A_{1\phi(1)}A_{2\phi(2)}...A_{n\phi(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]sign(\chi)[/math] = [math]sign(\chi')[/math], так как одна получается из другой за чётное число транспозиций. Однако [math]\sum\limits_\chi A_{1\chi(1)}A_{2\chi(2)}...A_{n\chi(n)}[/math] = [math]- \sum\limits_{\chi'} A_{1\chi'(1)}A_{2\chi'(2)}...A_{n\chi'(n)}[/math], так как перенаправлено было нечётное число рёбер.

Таким образом, для [math]\forall \chi,\chi'[/math] слагаемые, соответствующие им в выражении для [math]det(A_{ij})[/math] сократятся. А так как в нём все слагаемые либо нулевые, либо [math]\in \Phi[/math], то [math]det(A_{ij}) = 0[/math]
[math]\triangleleft[/math]

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

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

Определение:
Матрицей Эдмондса для двудольного графа [math]G[/math] с размерами долей [math]n[/math],[math]m[/math] называется матрица размера [math]n \times m[/math] [math]D_{ij} = \begin{cases} E_{ij}\text{, edge $(i,j)$ exists;}\\ 0\text{, else.} \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]