Матрица Татта и связь с размером максимального паросочетания в двудольном графе
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Матрица Татта
Определение: |
Матрицей Татта (англ. Tutte matrix) для графа где — независимые переменные ( не зависят друг от друга, и могут принимать произвольные значения) | с вершинами называется матрица размера
Теорема: |
В графе совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для не равен нулю тождественно. существует |
Доказательство: |
|
Матрица Эдмондса
Для случая, когда двудольный, существует более простая матрица, аналогичная матрице Татта.
—Определение: |
Матрицей Эдмондса (англ. Edmonds matrix) для двудольного графа где — независимые переменные | с размерами долей , называется матрица размера
Теорема: |
Ранг матрицы Эдмондса для графа максимального паросочетания в этом графе совпадает с размером |
Доказательство: |
Рангом матрицы называется количество линейно независимых строчек/столбцов в ней. Или, что эквивалентно, размер наибольшего ненулевого минора. Рассмотрим этот максимальный минор Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем . На нём матрицу Эдмондса легко дополнить до матрицы Татта, причём её определитель, очевидно, останется ненулевым. По ранее доказанной теореме, в графе, соответствующем существует совершенное паросочетание, то есть покрывающее все его вершины. То есть мощности, равной размеру . , что невозможно в силу выбора максимальным. |
См. также
- Теорема Татта о существовании полного паросочетания
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Декомпозиция Эдмондса-Галлаи