Cтраница 3
Для гиперсетей это положение не всегда выполняется. Например, на рис. 7 приведена гиперсеть S - ( X, V, R), в которой вершины s и t 1-соединимы, но 2-отделимы. Из примера ясно, что квази - и слабая соединимость отличаются от квази - и слабой отделимости. Легко показать, что для полиномиально вычислимых задач соединимости и отделимости в гиперсетях теорема Менгера справедлива. Причем при исследовании 9Я ( 5) - отделимости вершин необходимо рассматривать при Н X / с-соединимость, при Н V k - F-соеди-нимость, при Н R частичную k - Д - соединимость. [31]
Только в 1956 г. ( II) был получен соответствующий результат ( Фордом и Фалкерсоном) для не имеющих общих ребер путей, соединяющих пары вершин, и ребер, которые разделяют их. Другая теорема, эквивалентная теореме Менгера, была сформулирована в 1932 г.: ( III) Граф является га-связным тогда и только тогда, когда каждая пара вершин соединяется не менее чем п путями, отличающимися вершинами. Теоремы ( I), ( II) и ( III) являются следствиями теоремы Форда и Фалкерсона о максимальном потоке и минимальном разрезе. Харари указывает, что несколько других теорем, которые на первый взгляд отличаются от теоремы Менгера, на самом деле эквивалентны ей. [32]
Поэтому можно считать, что на каждой А общие с Q участки (12.2.3) располагаются в возрастающем порядке и любые два последовательных участка имеют не более одной общей вершины. Отсюда следует, что па каждой Ai любая вершина может иметь не более однсн г входящей и одной выходящей секущей цени. Построение Q показывает, что любой входящей секущей цепи на At должна предшествовать выходящая цепь. Таким образом, секущие цепи Ch удовлетворяют условиям для чередующегося семейства секущих ребер с простыми цепями Ai. Это завершает доказательство теоремы Менгера. [33]
С имеет не менее й 1 вершин. Поскольку вершине ц и смежным с ней вершинам приписаны обычные цвета, то должны существовать две смежные с и вершины, скажем V и ш, окрашенные в одинаковый цвет. Поэтому К ( 0; 7, 7) 3 ( определение величины К ( 0 Т и), см. в разд. Значит, согласно теореме Менгера ( 11.34 или 11.35), в графе О существуют три внутренне непересекающиеся цепи, соединяющие вершину I с вершиной и. [34]