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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
|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}
+
<math>A_{ij} = \begin{cases} E_{ij}\;\;\mbox{edge}\;(i,j)~exist \mbox{ and } i<j\\
  E_{ij}, & \mathrm{edge}\;(i,j)\;exists\;\mathrm{and}\;i<j\\
+
-E_{ji}\;\;\mbox{edge}\;(i,j)~exist \mbox{ and } i>j\\
  -E_{ji}, & \mathrm{edge}\;(i,j)\;exists\;\mathrm{and}\;i>j\\
+
0\;\;\;\;\mbox{otherwise} \end{cases},</math>
  0, & \mathrm{otherwise} \end{cases},</tex>
 
 
где <tex>E_{ij}</tex> {{---}} независимые переменные (<tex>E_{ij}</tex> не зависят друг от друга, и могут принимать произвольные значения)
 
где <tex>E_{ij}</tex> {{---}} независимые переменные (<tex>E_{ij}</tex> не зависят друг от друга, и могут принимать произвольные значения)
 
}}
 
}}
Строка 13: Строка 12:
 
|statement = В графе <tex>G</tex> существует [[Паросочетания:_основные_определения,_теорема_о_максимальном_паросочетании_и_дополняющих_цепях | совершенное паросочетание]] тогда и только тогда, когда определитель матрицы Татта для <tex>G</tex> не равен нулю тождественно.
 
|statement = В графе <tex>G</tex> существует [[Паросочетания:_основные_определения,_теорема_о_максимальном_паросочетании_и_дополняющих_цепях | совершенное паросочетание]] тогда и только тогда, когда определитель матрицы Татта для <tex>G</tex> не равен нулю тождественно.
 
|proof =  
 
|proof =  
<tex>\det(A) = \sum\limits_\varphi \operatorname{sign}(\varphi)A_{1\varphi(1)}A_{2\varphi(2)} \ldots A_{n\varphi(n)}</tex>
+
<tex>det(A) = \sum\limits_\phi sign(\phi)A_{1\phi(1)}A_{2\phi(2)}...A_{n\phi(n)}</tex>
 
<br>
 
<br>
Пусть <tex>\Phi = \{\forall\varphi | A_{1\varphi(1)}A_{2\varphi(2)} \ldots A_{n\varphi(n)} \ne 0\}</tex>
+
Пусть <tex>\Phi = \{\forall\phi | A_{1\phi(1)}A_{2\phi(2)}...A_{n\phi(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>\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 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)</tex> сократятся. А так как в нём все слагаемые либо нулевые, либо <tex>\in \Phi</tex>, то <tex>\det(A) = 0</tex>
+
Таким образом, для <tex>\forall \chi,\chi'</tex> слагаемые, соответствующие им в выражении для <tex>det(A)</tex> сократятся. А так как в нём все слагаемые либо нулевые, либо <tex>\in \Phi</tex>, то <tex>det(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 | двудольный]], существует более простая матрица, аналогичная матрице Татта.
+
Для случая, когда <tex>G</tex> {{---}} двудольный, существует более простая матрица, аналогичная матрице Татта.
 
{{Определение
 
{{Определение
 
|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} = \begin{cases}
+
<math> D_{ij} = \left\{ \begin{array}{ll}
   E_{ij}, & \mathrm{edge}\;(i,j)\;exists\\
+
   E_{ij} & \mbox{edge}\;(i,j)\;exists \\
   0, & \mathrm{otherwise}
+
   0 & \;else
\end{cases},</tex>  
+
\end{array},\right.</math>  
 
где <tex>E_{ij}</tex> {{---}} независимые переменные
 
где <tex>E_{ij}</tex> {{---}} независимые переменные
 
}}
 
}}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: