Большая техническая энциклопедия
2 4 7
D L N
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я
МА МГ МЕ МИ МЛ МН МО МУ МЫ МЯ

Минимаксная теорема - кениг

 
Минимаксная теорема Кенига является частным целочисленным случаем более общей теоремы двойственности линейного программирования. Мы представим подход Эдмондса для нахождения граней соответствующего выпуклого политопа, натянутого на двоичные векторы инцидентности всех паросочетаний в графе.
Минимаксная теорема Кенига является непосредственным следствием приведенных нами результатов.
Подобно тому, как минимаксная теорема Кенига для двудольных графов связывает паросочетания и покрытия, 2-паросочетания могут быть связаны с 2-покрытиями в случае графов общего вида. Сумма всех весов называется размером 2-покрытия.
Мы увидим, что соответствующее обобщение минимаксной теоремы Кенига на 2-паросочетания справедливо для всех графов, а не только для двудольных. Будут введены аналоги для элементарных и бикритических графов, базирующиеся на понятии 2-паросочетания. Оперирования с 2-паросочетаниями во многих ситуациях легче, чем с обычными ( 1 -) паросочетаниями, поэтому вполне резонно спросить, например, каким образом могут быть использованы наибольшие 2-паросочетания для получения наибольших 1-паросочетаний. Ответ пока не известен.
Теперь применим теорему о максимальном потоке и минимальном разрезе для получения быстрого доказательства минимаксной теоремы Кенига.
Мы уже применяли успешно такой прием при исследовании двудольных графов с положительным избытком ( см. теорему 1.3.8) и неявно использовали его в первом доказательстве минимаксной теоремы Кенига.
Приводимая в упражнении 3.1.17 минимаксная формула для J ( G), где G - общий граф ( см. Эдмондс ( 1965а)), является аналогом минимаксной теоремы Кенига для двудольных графов.
А. 1. Двудольные графы. один имеет совершенное паросочетание ( G, другой не имеет ( Я. В настоящем разделе чередующиеся цепи будут использованы для получения второго доказательства минимаксной теоремы Кенига, а затем - для описания хорошего алгоритма построения наибольшего паросочетания в двудольном графе. Более сложная задача нахождения хороших алгоритмов построения паросочетаний для общих ( не обязательно двудольных) графов будет содержанием гл.
Гиперграф - это такое обобщение графа, когда ребро может иметь более двух концевых вершин. Задача о паросочетании может быть обобщена на гиперграфы следующим естественным способом: найти максимальное число попарно непересекающихся ребер гиперграфа. Хотя эта задача и является NP-полной, для гиперграфов существуют различные обобщения минимаксной теоремы Кенига. Нами будет представлено краткое обсуждение этой задачи о паросочетании в гиперграфе.
Заметим, что теорема 12.2.3 может служить для получения новых доказательств некоторых предыдущих результатов. Как отмечалось выше, двудольные графы являются совершенными, и поэтому, согласно теореме 12.2.3, таковы и их дополнения. Она, в свою очередь, с помощью тождеств Галлаи ( леммы 1.0.1 и 1.0.2) влечет минимаксную теорему Кенига ( теорема 1.1.1), которая гласит, что дополнения реберных графов двудольных графов являются совершенными.
Несколько совершенных графов. Несколько упомянутых ранее результатов могут быть сформулированы в терминах совершенства определенных графов. Двудольные графы, как легко видеть, совершенны. Из теоремы Кенига о хроматическом индексе двудольных графов ( см. теорему 1.4.15) следует, что реберные графы двудольных графов являются совершенными. Из минимаксной теоремы Кенига ( теорема 1.1.1) вытекает, что дополнение реберного графа для двудольного графа есть совершенный граф.
Оказывается, теорема о максимальном потоке и минимальном разрезе в некотором смысле эквивалентна минимаксной теореме Кенига.
Мы утверждаем, что этот двудольный граф имеет совершенное паросочетание. Так как А есть / - сеть, то существует элемент х ACtsUt. Поскольку ху - ребро графа GO, то, по определению множества Т, оно должно содержать по меньшей мере один из элементов х и у. Но А является ( / - сетью минимальной мощности. Так как это неравенство справедливо для любого Т, то, используя минимаксную теорему Кенига ( теорему 1.1.1), заключаем, что граф Go имеет совершенное паросочетание.
 
Loading
на заглавную 10 самыхСловариО сайтеОбратная связь к началу страницы

© 2008 - 2014
словарь online
словарь
одноклассники
XHTML | CSS
Лицензиар ngpedia.ru
1.8.11