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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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 MAXimal::algo::Матрица Татта]
+
*[http://e-maxx.ru/algo/tutte_matrix E-maxx {{---}} Матрица Татта]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о паросочетании]]
 
[[Категория: Задача о паросочетании]]

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

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

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

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