С.В. Яблонский - Введение в дискретную математику (1060464), страница 35
Текст из файла (страница 35)
Так как граф Г' связен, то каждая пара граничных вершин может быть соединена цепью, целиком принадлежащей Г'. Пусть с' и с" — две такие граничные вершины, что указанная цепь А... не содержит никаких других граничных вершин. Ясно, что через вершины с' и с" можно провести цепи (соединяющие полюса) А' и А". Очевидно, что цепь А. - имеет с цепями А' и А" общими только концевые вершины с' и с".
Применяя к цепям А', А" и А." лемму 1, мы построим цепь, частью которой будет А... что противоречит определению Г'. Следовательно, Г' обладает единственной граничной вершиной, т. е. Г' является отростком. Лемма доказана. Ю В дальнейшем будем рассматривать Рве. 14 только сильно связные сети. Рассмотрим сеть Г,(а, Ь)- йй«(Е«1 Е,), где йй (о Ь) Е«Е~ (а, Ь) (см. рис. 14) .
Эту сеть будем назь1вать тривиальной сетью, О п р е д е л е н и е. Сильно связная сеть называется разложимой, если существуют такие нетривиальные непересекающиеся сети Г,(а, Ь) нГ«(а', Ь'), что сетьГ(а, Ь) есть результат подстановки сети Г,(а', Ь') вместо некоторого ребра сети Г,(а, Ь).
Очевидно, сеть, приведенная на рис. 10, является разложиыой. Определение. Сильно связная сеть Г(а, Ь), не являющаяся разложнмой, нааывается неразложимой На рис. 15 представлены примеры трех нетривиальных неразложимых сетей (полюса помечены кружочками). Можно показать, что любая нетривиальная неразложимая сильно связная сеть, имеющая не более шести ребер, изоморфна одной из трех сетей, представленных на рис. 15, Это оаначает, что не существует неразложимых «) Зели ил несколько, возьмем одно из ввх. 243 гл. х сети сильно свяаных сетей с тремя, четырьмя и шестью ребрамн.
В то же время для каждого Ь > 7 существуют неразложимые сильно сзязпые сети с Ь ребрами (см. [31]). Последнее легко усматривается из рис. 16, на котором укааано построение неразложимых сетей с Й (Ь > 7) ребрами. Цель дальнейших рассмотрений — изучение вопросов разложимости сетей. Поскольку нас будут интересовать разложения специального вида, выделим две простейшие Ь-71+1 ИФ+7 Рис.
16 неразложимые сети: параллельное соединение двух ребер Г, "(а„Ь) и последовательное соединение двух ребер Гз(а, Ь) (см. рис. 17). Множество остальных нетривиальных неразложимых сетей обозначим через Н и сеть, принадлежащую Н, будем называть Н-сетью. С сетямп Гзз (а, ь) и Г', (а, ь) связаны два бесконечных множества сетей. Множество Р, состоящее из сетей Гзь(а, Ь), — параллельное соединение й ребер (й 2, 3, ...). Очевидно, что Г1(а, Ь) при й ~ 2 является суперпозицией сетей 1'",(а, Ь) (см. рпс.
18). ч. !п. ГРЛФы и сети в Ь фщ Рис. 1т Определение. Сильно связная сеть Г(а, Ь) распадается на два параллельных куска, если множество всех ее цепей можно разбить на два непустых класса так, что любые две цепи иэ разных классов не имеют общихвнутренних вершин. Очевидно, каждая иэ сетей Гь(а, Ь) (й > 2) распадается на два параллельных куска. У» ФВ Г~Ь,И Рис.
18 О п р е д е л е н и е. Пусть с ' — внутренняя (т. е. отличная от полюсов) вершина сильно связной сети Г(а, Ь). Вершина с называется разделяющей, если каждая цепь проходит через с. Очевидно, что каждая иа внутренних вершин сети Гь(а, Ь) является рааделяющей, Пусть с — разделяющая вершине сети Г(а, Ь). Рассмотрим в каждой цепи отрезок от вершины а до вершины с.
Очевидно, что совокупность этих отреаков цепей порождает сеть Г,(а, с) с полюсами в вершинах а и с. Аналогично, если выделить в каждой цепи отрезок от вершины с до вершины Ь, то получим сеть Г,(с, Ь). Л е м и а 3. Пусть с — разделяющая вершина сильно связной сети Г(а, Ь). Тогда Г(а, Ь) получается супврпозицивй сетей Г. (а, Ь), Г,(о, с), Г,(с, Ь) (последовательное соединение сетей Г,(о, с) и Г,(с, Ь)). Множество Я, состоящее иэ сетей Г'„(а, Ь), — последовательное соединение й ребер (й 2, 3, ...). Очевидно, что Гь(а, Ь) при й ) 2 является суперпоэнцпей сетей Гг(а, Ь) (см.
рис. т8). гл. к сити 245 Доказательство следует из того факта, что сети Г,(а, с) п Г,(с, Ь) не имеют общих внутренних вершин. В самом деле, если это не так, то существуют две цепи А,. и Азь соответственно, сетей Г,(а, с) и Г,(е, 6), которые имеют общую внутреннюю вершину (см. рис. 19). Рис. 20 Рис. 19 Обозначим через с( первую общую вершину этих цепей, если двигаться по цепи А„от точки а.
Очевидно, что отреаок цепи А.. между вершинами а и а* и отрезок цепи А„между вершинами а и Ь порождают цепь, не проходящую через с. Последнее противоречит тому, что вершина с является разделяющей. Лемма доказана. Определение. Пусть с — вершина сети Г(а, Ь), тогда совокупность всех ее ребер, имеющих своим концом вершину с, называется звездой (с центром в с). Если с— полюс, то звезда называется полюсной. Относительно Н-сетей сформулируем следующую лемму. Лемма 4. Если Г(а, 6) — Н-сеть, а с и а — две различные внутренние вершины (т. е. отличные от полюсов), то существует цепь, проходящая через И и не проз(одящал через вершину с.
Д о к а з а т е л ь с т в о. Данное утверждение вытекает из более сильного факта: если из Г(а, 6) удалить звезду с центром в с, то полученная сеть будет сильно связной. Возможны три случая. а) Удаление звезды приводит к распадению графа на две связные компоненты, которые не имеют общих вершин (см. рис. 20). Очевидно, в атом случае вершина е будет разделяющей, и в силу леммы 3 исходная сеть будет разложимой (одна из компонент будет содержать не менее двух ребер, так как Н-сеть имеет более четырех ребер), а это невозмоя'но. б) Удаленно звезды приводит к сети, которая является связной, но не сильно связной. В силу того, что полученная сеть не сильно связная, она имеет отросток с граничной точкой а' (см. рис. 21).
Поскольку исходная сеть 24б Ч 1П. ГРАФЫ И СЕТИ Г(а, Ь) сильно связная, то отросток должен иметь граничные вершины с данной звездой и отличные от с(. В таком случае отросток с частью ребер звезды образует двухполюснуюсеть Г'(д, с). Последнееозначает, что Г(а, Ь)— разложима, мы пришли к противоречию. Рнс. 2$ Рвс. 22 в) Остается последняя возможность — удаление звеады приводит к сильно связной сети. Лемма доказана. Следствие.
Н-сеть не имеет разделяющих вершин. Лемма 5. Если Г(а, Ь) — Н-сеть и (а, с) — ребро, принадлежащее полюсной звезде, то после удаления етого ребра тюлучим сильно связную сеть. Доказательство (аналогично доказательству предыдущей леммы) . а) Удаление ребра дает сеть, не являющуюся связной. Очевидно, тогда с будет разделяющей вершиной сети Г(а, Ь), что противоречит следствию леммы 4. б) Удаление ребра дает связную сеть Г'(а, Ь), но не сильно связную. Обозначим граничную вершину отростка сети Г'(а, Ь) через д (см.
рис. 22). Ясно, что втот отросток вместе с ребром (а, с) дает двухполюсную сеть Г (а, Н). Последнее противоречит неразложимостя Г(а, Ь). в) Остается последняя возможность: сеть Г'(а, Ь)— сильно связная. Рассмотрим разложимую сеть Г(а, Ь). Пусть Г(а, Ь) есть результат подстановки вместо ребер Е„ . , Е» (Ь > 2) сети Г,(а, Ь) =зг»(Е,; Е„ ..., Е») соответственно сетей Г,(а'", Ь'"), ..., Г,(а'"', Ь1"'), из которых хотя бы одна нетривиальна.
Разложение сети Г(а, Ь) на внешнюю сеть Г»(а, Ь) и внутренние сети Г,(а"', Ь'"), ..., Г„(а'"', Ь'"') допускает простое геометрическое толкование: исходная сеть Г(а, Ь) покрывается сгтямя Г,(а'", Ь'"), ..., Г„(а'"', Ь'"') так, что любые две внутренние сети могут иметь общилги только свои иолюсвые вершины; расположение отпх внутренних Рл.
а сети сетей характеризуется внешней сетью (см. рнс. 23). Таким образом, каждое ребро сети принадлежит ровно одной внутренней сети, а вершина сети Г(а, Ь) либо является полюсом внутренней сети (и значит вершиной внешней Рис. 24 Рис. 23 сети), либо внутренней вершиной ровно одной внутренней сети. 3 а и е ч а н и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
