Матрица Татта и связь с размером максимального паросочетания в двудольном графе — различия между версиями
Gaudima (обсуждение | вклад) |
|||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 42: | Строка 42: | ||
Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем <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/Tutte_matrix Wikipedia {{---}} Tutte matrix] | ||
*[https://en.wikipedia.org/wiki/Edmonds_matrix Wikipedia {{---}} Edmonds matrix] | *[https://en.wikipedia.org/wiki/Edmonds_matrix Wikipedia {{---}} Edmonds matrix] | ||
− | *[http://e-maxx.ru/algo/tutte_matrix | + | *[http://e-maxx.ru/algo/tutte_matrix MAXimal::algo::Матрица Татта] |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о паросочетании]] | [[Категория: Задача о паросочетании]] |
Версия 22:32, 22 ноября 2018
Матрица Татта
Определение: |
Матрицей Татта (англ. Tutte matrix) для графа где — независимые переменные ( не зависят друг от друга, и могут принимать произвольные значения) | с вершинами называется матрица размера
Теорема: |
В графе совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для не равен нулю тождественно. существует |
Доказательство: |
|
Матрица Эдмондса
Для случая, когда двудольный, существует более простая матрица, аналогичная матрице Татта.
—Определение: |
Матрицей Эдмондса (англ. Edmonds matrix) для двудольного графа где — независимые переменные | с размерами долей , называется матрица размера
Теорема: |
Ранг матрицы Эдмондса для графа максимального паросочетания в этом графе совпадает с размером |
Доказательство: |
Рангом матрицы называется количество линейно независимых строчек/столбцов в ней. Или, что эквивалентно, размер наибольшего ненулевого минора. Рассмотрим этот максимальный минор Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем . На нём матрицу Эдмондса легко дополнить до матрицы Татта, причём её определитель, очевидно, останется ненулевым. По ранее доказанной теореме, в графе, соответствующем существует совершенное паросочетание, то есть покрывающее все его вершины. То есть мощности, равной размеру . , что невозможно в силу выбора максимальным. |
См. также
- Теорема Татта о существовании полного паросочетания
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Декомпозиция Эдмондса-Галлаи