Cтраница 2
Приведенное выше доказательство теоремы Кенига можно приспособить для обоснования других минимаксных теорем, включая теорему о максимальном потоке и минимальном разрезе ( см. упр. [16]
Мы воспроизводим доказательство теоремы Кенига для двудольных графов, данное в разд. Будем удалять из Н ребра до тех пор, пока т ( Н) остается неизменным. Заметим, что при удалении из Н ребер свойство сбалансированности сохраняется. Пусть Н обозначает полученный таким образом гиперграф. [17]
Это равенство выражает теорему Кенига. [18]
Теорема, аналогичная теореме Кенига. [19]
Это предложение называется теоремой Кенига. [20]
Таким образом, из теоремы Кенига о реберной раскраске вытекает приведенный выше результат. [21]
Этот результат известен как теорема Кенига. [22]
Формула ( 10) и теорема Кенига имеют особую важность для твердых тел. Однако выражению для живой силы твердого тела можно придать особый вид, благодаря чему этот случай заслуживает того, чтобы рассмотреть его независимым путем. [23]
В теории двудольных графов фундаментальную роль играет теорема Кенига, которую здесь мы приведем в матричной интерпретации. [24]
Теорема Монтера о вершинном разделении является обобщением теоремы Кенига о паросоче-гании ( теорема 7.9.4) для двудольных графов. [25]
Теорема Менгера о вершинном разделении является обобщением теоремы Кенига о паросо-четании ( теорема 7.9.4) для двудольных графов. При анализе теорем о паросочетаниях мы использовали понятие дефицита для двудольного графа Как будет показано, это понятие можно распространить на случай связывающих простых цепей в произвольном ориентированном или неориентированном графе G. Если граф G ориентированный, то нужно рассматривать только ориентированные цепи. [26]
Это важное для решения задач соотношение называется теоремой Кенига; доказательство теоремы дается в теоретической физике. [27]
Мы докажем теорему Дилуорса, предполагая, что теорема Кенига верна. Доказательство обратного утверждения оставим в качестве упражнения читателю. [28]
Таким образом, мы получаем теорему, аналогичную теореме Кенига для кинетической энергии. [29]
Теоремы 7.1.2 и 7.1.3 утверждают значительно больше, чем теорема Кенига; из них вытекают более глубокие результаты - минимаксные формулы для задачи о взвешенном паросочетаний и для задачи о взвешенном вершинном покрытии. Предполагаем, что граф G - двудольный. Будем искать в нем паросочетание наибольшего веса. [30]