Cтраница 2
Попытаться охарактеризовать все согласованные разделяющие множества: ( а) если G конечно; ( ( 3) если G является графом с максимальным паросочетанием. [16]
Рассмотрим еще одно свойство разделяющих множеств. [17]
ТЕОРЕМА 12.1. Каждое r - разделяющее множество содержит неприводимое r - разделяющее множество. [18]
Как подсказывает интуиция, r - разделяющим множеством в трехмерном пространстве R3 будет некоторая поверхность толщины г, что приводит к задаче Плато. [19]
При использовании терминов дерево, лес, разделяющее множество, разрез и простой разрез без специальной оговорки считается, что направления дуг не учитываются и рассматривается соответствующий неориентированный граф. Однако, при учете направления дуг, возникает несколько дополнительных понятий. [20]
Примеры двух разделяющих множеств графа G ( второе разделяющее множество является подмножеством первого) показаны пунктиром на рис. 1.9. Разделяющее множество, изображенное на рис. 1: 9, а, разбивает граф на три компоненты, одна из которых содержит вершины множества W, обведенного кружком на рисунке. [21]
Согласно теореме 12.3, всякое неприводимое r - разделяющее множество С r - разделяет плоскость R2 на такие два открытых множества А и В, что любая пара точек в каждом из этих множеств может быть r - связана цепью, не имеющей общих точек с С. [22]
Теорема 7.9.1. Любой граф с максимальными паросочетаниями имеет согласованные разделяющие множества. [23]
Это представление показывает, что А0 также является разделяющим множеством. [24]
Это прадставление показывает, что Ай также является разделяющим множеством. [25]
Снова / вершин ( аг) не могут образовывать разделяющее множество, и существует связывающая простая цепь Р, не проходящая через эти вершины. Если Р не содержит никаких вершин простых цепей А /, то она является искомой связывающей простой цепью. Предположим, что р - первая вершина на Р, лежащая в б или за a. [26]
ТЕОРЕМА 12.1. Каждое r - разделяющее множество содержит неприводимое r - разделяющее множество. [27]
Если весовая функция w ( х, у) произвольна, то любое неприводимое r - разделяющее множество легко можно сделать разделяющим множеством с минимальным весом. [28]
Следующий этап доказательства заключается в перечислении ( d - 2) - граней многогранника М, принадлежащих разделяющим множествам. Покажем, что каждое разделяющее множество 5г имеет по крайней мере одну ( d - 2) - грань, не являющуюся правильной. Отметим, что ( d - 2) - грань из разделяющегося множества 5 - является правильной, если она в пересечении с некоторым другим разделяющим множеством дает ( d - 3) - грань. Рассматриваем последовательно все разделяющие множества S /, / t, которые в пересечении с St имеют ( d - 3) - грани. [29]
Примеры двух разделяющих множеств графа G ( второе разделяющее множество является подмножеством первого) показаны пунктиром на рис. 1.9. Разделяющее множество, изображенное на рис. 1: 9, а, разбивает граф на три компоненты, одна из которых содержит вершины множества W, обведенного кружком на рисунке. [30]