Теорема - менгер
Cтраница 1
Теорема Менгера о вершинном разделении является обобщением теоремы Кенига о паросо-четании ( теорема 7.9.4) для двудольных графов. При анализе теорем о паросочетаниях мы использовали понятие дефицита для двудольного графа Как будет показано, это понятие можно распространить на случай связывающих простых цепей в произвольном ориентированном или неориентированном графе G. Если граф G ориентированный, то нужно рассматривать только ориентированные цепи. [1]
Из теоремы Менгера следует теорема Холла. [2]
Обычная форма теоремы Менгера использует понятие внутренне непересекающихся цепей. [3]
Это завершает доказательство теоремы Менгера. [4]
 |
Граф для иллюстрации теоремы Менгера. [5] |
Хронологически второй вариант теоремы Менгера был опубликован Уитни в его статье [2], содержащей критерий п-связности графа. [6]
Вторая импликация выражает прежнюю теорему Менгера для обыкновенного графа Lxy. [7]
В еще одном варианте теоремы Менгера рассматриваются два подмножества V и V множества У ( 0) и ищется максимальное число попарно непересекающихся соединений между И и V. В этом случае соединением может быть и граф-вершина в С, соответствующий вершине, принадлежащей одновременно подмножествам II и V. Кроме того, соединением является цепь в графе О, один конец которой лежит в II и не принадлежит V, а другой содержится в У и не входит в [, причем внутренние вершины цепи ( если они есть) не принадлежат ни одному из подмножеств [ У и У. [8]
Хотя это утверждение типа теоремы Менгера, доказать его значительно проще, чем теорему Менгера. [9]
Следует заметить, что теорему Менгера для графов, которая рассматривалась в разд. [10]
Существует много равноценных способов обоснования теоремы Менгера. Мы начнем с такого ее варианта, который нам кажется наиболее легко доказуемым с помощью теории, развитой в разд. [11]
Харари также указывает, что другие варианты теоремы Менгера встречаются в литературе по линейному программированию и теоремам двойственности. [12]
Покажите, каким образом вершинная и реберная формы теоремы Менгера могут быть выведены одна из другой. [13]
В этом разделе мы сформулируем еще несколько вариантов теоремы Менгера; все они найдены независимо друг от друга, и только позднее была выявлена их взаимосвязь и дана теоретико-графовая формулировка. [14]
Следующая теорема и формулировкой и доказательством сходна с теоремой Менгера. [15]
Страницы: 1 2 3