Cтраница 1
Минимальные разделяющие множества называются простыми) разрезами. Из предыдущих определений ясно, что простой разрез обязательно является разрезом, однако не каждый разрез является простым. Например, разрез, изображенный на рис. 1.9, Ь, не является простым. В общем случае, если удаление ребер, принадлежащих разрезу F, делит граф на три или более компоненты, то разрез не может быть простым. [1]
Любое разделяющее множество содержит минимальные разделяющие множества. [2]
Теорема 7.9.5. Локально конечный граф имеет конечно минимальные разделяющие множества S, и любое такое множество согласовано для некоторого максимального паросочетания. [3]
Чтобы доказать его достаточность, предположим, что условие (12.4.4) выполнено. Тогда А само имеет минимальное разделяющее множество не менее чем с v ( A) вершинами; следовательно, по теореме 12.2.1 существует ( А) непересекающихся простых цепей от А к В. [4]
Чтобы доказать его достаточность, предположим. Тогда А само имеет минимальное разделяющее множество не менее чем с ( А) вершинами; следовательно, по теореме 12.2.1 существует vL4) непересекающихся простых цепей от А к В. [5]
В, если каждая связывающая простая цепь должна проходить хотя бы через одну вершину из S. Заметим, что каждое разделяющее множество содержит минимальное разделяющее множество. Множества Л и В называются а-вершинно разделенными, если существует конечное разделяющее множество (12.2.2) с минимальным числом о вершин. [6]
А и В, если каждая связывающая простая цепь должна проходить хотя бы через одну вершину из S. Заметим, что каждое разделяющее множество содержит минимальное разделяющее множество. Множества А п В называются а-вер-шинпо разделенными, если существует конечное разделяющее множество (12.2.2) с минимальным числом а вершин. [7]
Два разделяющих множества, стоящих в левой части неравенства, вместе образуют множество, разделяющее / k пар узлов. Сумма их пропускных способностей не может быть меньше выражения, стоящего в правой части неравенства, так как это выражение есть пропускная способность минимального разделяющего множества. [8]