Матрица Татта и связь с размером максимального паросочетания в двудольном графе — различия между версиями
(→Матрица Эдмондса) |
м (rollbackEdits.php mass rollback) |
||
(не показано 13 промежуточных версий 5 участников) | |||
Строка 1: | Строка 1: | ||
==Матрица Татта== | ==Матрица Татта== | ||
{{Определение | {{Определение | ||
− | |definition = '''Матрицей Татта''' (англ. | + | |definition = '''Матрицей Татта''' (англ. ''Tutte matrix'') для графа <tex>G</tex> с <tex>n</tex> вершинами называется матрица размера <tex>n \times n</tex> |
− | <tex>A_{ij} = | + | |
− | + | <tex>A_{ij} = \begin{cases} | |
− | + | E_{ij}, & \mathrm{edge}\;(i,j)\;exists\;\mathrm{and}\;i<j\\ | |
− | + | -E_{ji}, & \mathrm{edge}\;(i,j)\;exists\;\mathrm{and}\;i>j\\ | |
− | + | 0, & \mathrm{otherwise} \end{cases},</tex> | |
− | + | где <tex>E_{ij}</tex> {{---}} независимые переменные (<tex>E_{ij}</tex> не зависят друг от друга, и могут принимать произвольные значения) | |
− | </tex> где <tex>E_{ij}</tex> - независимые переменные | ||
− | |||
− | |||
− | { | ||
− | |||
}} | }} | ||
{{Теорема | {{Теорема | ||
− | |statement = В графе <tex>G</tex> существует совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для <tex>G</tex> не равен нулю | + | |statement = В графе <tex>G</tex> существует [[Паросочетания:_основные_определения,_теорема_о_максимальном_паросочетании_и_дополняющих_цепях | совершенное паросочетание]] тогда и только тогда, когда определитель матрицы Татта для <tex>G</tex> не равен нулю тождественно. |
|proof = | |proof = | ||
− | <tex>det( | + | <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\ | + | Пусть <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)} | + | В противном случае в <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( | + | Таким образом, для <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 = '''Матрицей Эдмондса''' (англ. | + | |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} |
− | + | E_{ij}, & \mathrm{edge}\;(i,j)\;exists\\ | |
− | + | 0, & \mathrm{otherwise} | |
− | + | \end{cases},</tex> | |
− | + | где <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::Матрица Татта] | ||
+ | |||
+ | [[Категория: Алгоритмы и структуры данных]] | ||
+ | [[Категория: Задача о паросочетании]] |
Текущая версия на 19:21, 4 сентября 2022
Матрица Татта
Определение: |
Матрицей Татта (англ. Tutte matrix) для графа где — независимые переменные ( не зависят друг от друга, и могут принимать произвольные значения) | с вершинами называется матрица размера
Теорема: |
В графе совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для не равен нулю тождественно. существует |
Доказательство: |
|
Матрица Эдмондса
Для случая, когда двудольный, существует более простая матрица, аналогичная матрице Татта.
—Определение: |
Матрицей Эдмондса (англ. Edmonds matrix) для двудольного графа где — независимые переменные | с размерами долей , называется матрица размера
Теорема: |
Ранг матрицы Эдмондса для графа максимального паросочетания в этом графе совпадает с размером |
Доказательство: |
Рангом матрицы называется количество линейно независимых строчек/столбцов в ней. Или, что эквивалентно, размер наибольшего ненулевого минора. Рассмотрим этот максимальный минор Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем . На нём матрицу Эдмондса легко дополнить до матрицы Татта, причём её определитель, очевидно, останется ненулевым. По ранее доказанной теореме, в графе, соответствующем существует совершенное паросочетание, то есть покрывающее все его вершины. То есть мощности, равной размеру . , что невозможно в силу выбора максимальным. |