Матрица Татта и связь с размером максимального паросочетания в двудольном графе
Версия от 22:30, 22 ноября 2018; 188.242.29.236 (обсуждение)
Матрица Татта
Определение: |
Матрицей Татта (англ. Tutte matrix) для графа где — независимые переменные ( не зависят друг от друга, и могут принимать произвольные значения) | с вершинами называется матрица размера
Теорема: |
В графе совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для не равен нулю тождественно. существует |
Доказательство: |
|
Матрица Эдмондса
Для случая, когда двудольный, существует более простая матрица, аналогичная матрице Татта.
—Определение: |
Матрицей Эдмондса (англ. Edmonds matrix) для двудольного графа где — независимые переменные | с размерами долей , называется матрица размера
Теорема: |
Ранг матрицы Эдмондса для графа максимального паросочетания в этом графе совпадает с размером |
Доказательство: |
Рангом матрицы называется количество линейно независимых строчек/столбцов в ней. Или, что эквивалентно, размер наибольшего ненулевого минора. Рассмотрим этот максимальный минор Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем . На нём матрицу Эдмондса легко дополнить до матрицы Татта, причём её определитель, очевидно, останется ненулевым. По ранее доказанной теореме, в графе, соответствующем существует совершенное паросочетание, то есть покрывающее все его вершины. То есть мощности, равной размеру . , что невозможно в силу выбора максимальным. |
См. также
- Теорема Холла
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества