Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
простое геометрическое толкование: исходная сеть Г(я,Ь) покрывается сетями Г\(яИ), 6(1)), ..Г\(а(ЛЗ, Ъ(Н)) так, что любые две внутренние сети могут иметь общими только свои полюсные вершины; расположение этих внутренних
Рис. 21
Рис. 22
Г (а, Ь).
ГЛ. 2. СЕТИ
247
сетей характеризуется внешней сетью (см. рис. 23). Таким образом, каждое ребро сети принадлежит ровно одной внутренней сети, а вершина сети Г (а, Ь) либо являемся полюсом внутренней сети (и значит вершиной внешней
сети), либо внутренней вершиной ровно одной внутренней сети.
Замечание. Выберем в сети Г0(а, Ь) цепь. Пусть
— внутренние сети, соответствующие ребрам этой цепи. Если в этих сетях выбрать по одной цепи, то получим цепь в Г (а, Ъ) (см. рис. 24).
Определение. Пусть сеть Г (а, Ъ) разлагается на внешнюю сеть Г0(я, Ъ) и внутренние сети Г1 (а(1),Ь{,))
а) если Го (а, Ь) есть Г? (а, Ь), то сеть Г(а, Ь) называется р-разложимой, а соответствующее разложение — р-разложением;
б) если Г0 (а, Ъ) есть П(а, Ъ), то сеть Г (а, Ь) называется в-разложимой, а соответствующее разложение — у-р аз л ож е нием;
в) если Го (а, ?>)—Я-сеть, то сеть Г (а, Ь) называется В-разложимой, а соответствующее разложение — Н-ра^зло-жением.
Лемма 6. Если сеть Г (а, Ь) разложима, то имеет место в точности одно из следующих утверждений:
Г (а, Ь) — р-разложимау Г (а, Ь) - Б-разложима,
Г (а, Ъ) —Н-разложима.
Доказательство. Нетрудно показать, что, «ели Г(а, Ь) разложима, то она допускает либо р-разлож&ние, либо ^-разложение, либо Я-разложение. А именно, так
а
Рис. 23
Рис. 24
Гл(а(Л), г>(Л)). Тогда:
Ч. III. ГРАФЫ И СЕТИ
кок Г (а, Ъ) разложима, то она допускает разложение на Го (а, Ъ) {внешняя сеть) и Г1{а(1\ Ь<0), ..., Г,.(а(,1>, (внутренние сети). Если внешняя сеть есть либо Гл(а, Ъ), либо Гд (а, 6), либо сеть класса Я, то мы имеем одно из указанных разложений. Если это ее так, то Г0 (а, ?>) разложима и мы получаем другое разложение сети Г (а, Ь) на сеть Г^(я, Ь) (внешняя сеть) и ГЦа^0, ...
..., Гд/ {а[к ), Ь\к 5) (внутренние сети), причем сеть Г0(а, Ь) имеет меньше ребер, чем сеть Г« (а, Ъ)(Н' <Н). В случае, если внешняя-сеть Г0(а, Ь) есть либо Г& (д, 6), либо Гд/ (я, Ь), либо сеть класса Я, мы получаем искомое разложение. В противном случае сеть Г[>(а, Ь) разложима и процесс повторяем снова. Так как сеть Г (а, Ь) имеет конечное число ребер, то в конце концов мы построим требуемое разложение. Теперь остается показать, что тип разложения определяется единственным образом.
Предположим, что сеть Г (я, Ъ) допускает Я-разло-жение.
а) Тогда она не может распадаться на два параллельных куска. Иначе внешняя сеть распадается также на два куска, т. е. является разложимой либо совпадает с Гг (а> Ь), что при //-разложении невозможно.
б) Она не может иметь и разделяющей вершины. В противном случае разделяющей вершипой будет внутренняя вершина внешней сети. Последнее при Я-разло-жении невозможно в силу следствия леммы 4.
Ясно также, что два свойства: распадение сети на два параллельных куска и наличие разделяющей вершипы — взаимоисключающи. Таким образом, разложимая двухполюсная сеть обладает в точности одним из следующих свойств: распадается на два параллельных куска, имеет разделяющую вершину, допускает //-разложение.
I. Разложимая сеть распадается на два параллельных куска в том и только том случае, если она р-разложнма.
II. Разложимая сеть имеет разделяющую вершину тогда и только тогда, когда она 5-разложима.
III. Разложимая сеть не распадается на два параллельных куска и не имеет разделяющей вершины в том и только в том случае, если она //-разложима.
Лемма доказана.
Определение, р-разл ожени е сети Г (а, Ь) называется р-расщеплениемл если внутренние сети разложения
ГЛ. 2. СЕТИ
249
отличны от сетей вида Гд(й, Ь) и сетей, являющихся р-раэложимыми; «-разложение сети Г(я, Ь) называется 8-расщеплением, если внутренние сети разложения отличны от сетей вида Г2(я, Ь) и сетей, являющихся «-разложимыми; //-разложение сети Г (а, Ь) называется Н -расщеплением.
Заметим, что сети Г? и Т'1(к^ 3) являются разложимыми, но не допускающими расщепления.
Пример 6. Рассмотрим сеть, изображенную на рис. 25. Очевидно, что разложение этой сети иа сеть Г„ (а, б) и сети Г'г (а, с), Г2(с, Ь) (см. рис. 20, я)) не является «-расщеплением, так как сеть Г3(с, Ь) есть сеть вида Г2(с, Ь). В то же время «-разложение на сеть Гр (я, Ь) и сети Г1 (а, с), Г2(с, й), Га(с?, Ь) (см.рис, 26, б)) является «-расщеплением.
Данный пример показывает, что для сети Г (я, Ь) может существовать несколько разложений.
г г.ы> ;-р р-, г, ли
г«ос ,>'тао $а>с
с О о У Г'^(с^)
е а' Ь
« Г'г(е,6)
а’о-------о Ь Г”Ы,Ь)
ю б)
Рис. 26
Определение. Внутренняя вершина с сети Г (а, Ь)' зависит от вершины д, той же сети, если каждая цепь, проходящая через с, проходит также через й.
Определение. Внутренние вершины с и д, сети Г (я, Ъ) называются эквивалентными, если вершина с зависит от вершины й и вершина д, зависит от вершины с.
Определение. Внутренняя вершина с сети Г (а, Ь) называется минимальной, если, какова бы ни была внутренняя вершина с/ сети Г (я, 6), либо с эквивалентна с/, либо с не зависит от й,
