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