Cтраница 3
Если весовая функция w ( х, у) произвольна, то любое неприводимое r - разделяющее множество легко можно сделать разделяющим множеством с минимальным весом. [31]
Рассмотрим подграф Сг графа G - Го, для которого С П Н ф 0 и который является компонентой графа G - Т для некоторого наименьшего разделяющего множества вершин Т графа G. Такие подграфы существуют по предположению; пусть, С - такой подграф с минимальным числом вершин и Т - соответствующее наименьшее разделяющее множество вершин. Если в С П Я найдется вершина с, для которой N ( c H) T, то предложение доказано. Поэтому предположим, что в СПЯ существует ребро с, с7, с е Г, и покажем, что это предположение приводит к противоречию. Тем самым предложение 1 будет доказано. [32]
Максимальное число реберно непересекающихся простых цепей, соединяющих две различные вершины, v uw связного графа G, равно минимальному числу k ребер в vw - разделяющем множестве. [33]
Проиллюстрируем эту теорему на примере орграфа, изображенного на рис. 28.3. Непосредственно проверяется, что у него 6 непересекающихся по дугам простых орцепей из v вш; соответствующее и - разделяющее множество обозначено пунктирными линиями. [34]
Теорема 7.9.3. Если G - двудольный граф с максимальными паросочеганияАШ М, то все такие паросоче-тания имеют одно и то же кардинальное число гШ) ребер, равное минимальному числу ( S) вершин в разделяющем множестве. [35]
Теорема 7.9.3. Если G - двудольный граф с максимальными паросочетаниями М, то все такие паросочетания имеют одно и то же кардинальное число v ( M) ребер, равное минимальному числу v ( S) вершин в разделяющем множестве. [36]
Тогда Sm разделяет комплекс 33, и по крайней мере один из его подкомплексов содержит ( d - 2) - грань, не ставшую правильной, когда удалили рт. Повторяя описанный процесс, в конце концов придем к ( d - 2) - грани в разделяющем множестве S -, которая не является правильной. [37]
Пропускной способностью разделяющего множества называется сумма пропускных способностей дуг, входящих в него. Разделяющее множество, пропускная способность которого минимальна, называется минимальным множеством. [38]
Разделяющее множество представляет собой множество ребер связного графа, после удаления которого граф становится несвязным. Разделяющее множество, состоящее из всех ребер, которые соединяют некоторое множество вершин графа V с его дополнением V ( VJV V, V f V 0), называют разрезом. [39]
Для обсуждения данного вопроса удобно ввести еще два определения, которыми мы и завершим этот параграф. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу. Например, в графе, изображенном на рис. 5.2, каждое из множеств еъ е %, es и ея, е6, е -, е &) является разделяющим; несвязный граф, оставшийся после удаления второго из этих множеств, показан на рис. 5.3. Далее, назовем разрезом такое разделяющее множество, никакое собственное подмножество которого не является разделяющим. [40]
Каждое разделяющее множество ребер содержит минимальное такое множество. Любое множество S, содержащее один конец каждого ребра из разделяющего семейства ребер, является разделяющим множеством вершин; любое семейство ребер, которое содержит все ребра, отходящие от разделяющего множества вершин, является разделяющим множеством ребер. [41]
Разделяющее множество (7.9.1) согласовано с М, если оно является М - множеством. Наконец, разделяющее множество согласовано, если оно согласовано со всеми максимальными паросочетаниями. [42]
Разделяющее множество (7.9.1) согласовано с М, если оно является Д / - множеством. Наконец, разделяющее множество согласовано, если оно согласовано со всеми максимальными паросочетаниями. [43]
Следующий этап доказательства заключается в перечислении ( d - 2) - граней многогранника М, принадлежащих разделяющим множествам. Покажем, что каждое разделяющее множество 5г имеет по крайней мере одну ( d - 2) - грань, не являющуюся правильной. Отметим, что ( d - 2) - грань из разделяющегося множества 5 - является правильной, если она в пересечении с некоторым другим разделяющим множеством дает ( d - 3) - грань. Рассматриваем последовательно все разделяющие множества S /, / t, которые в пересечении с St имеют ( d - 3) - грани. [44]
В, если каждая связывающая простая цепь должна проходить хотя бы через одну вершину из S. Заметим, что каждое разделяющее множество содержит минимальное разделяющее множество. Множества Л и В называются а-вершинно разделенными, если существует конечное разделяющее множество (12.2.2) с минимальным числом о вершин. [45]