С.В. Яблонский - Введение в дискретную математику (1060464), страница 36
Текст из файла (страница 36)
Выберем в сети Г, (а, Ь) цепь. Пусть Г,,(а(ч), Ь(")), ..., Гв (а('), Ь(')) — внутренние сети, соответствующие ребрам этой цепи. Если в этих сетях выбрать по одной цепи, то получим цепь в Г(а, Ь) (см. рнс. 24). Определение. Пусть сеть Г(а, Ь) разлагается на внешнюю сеть Г,(а, Ь) и внутренние сети Г,(а'",Ь"'), ,.„Г„(аоз Ьоо). Тогда: а) если Г,(а, Ь) есть Гь" (а, Ь), то сеть Г(а, Ь) называетсн р-разложимой, а соответствующее разложение — рразложением; б) если Г,(а, Ь) есть Гь(а, Ь), то сеть Г(а, Ь) навывается е-разложимой, а соответствующее разложение— в-ра зл ожени ем; в) если Г,(а, Ь) — Н-сеть, то сеть Г(а, Ь) нааывается Н-разложимой, а соответствующее разложение — Н-разложением.
Лемма 6. Если сеть Г(а, Ь) разложима, то имеет место в точности одно из следующих утверждений: Г(а, Ь) — р-разложима, Г(а, Ь) — з-разложима, Г (а, Ь) — Н-разложима. Доказательство. Нетрудно. показать, что, если Г(а, Ь) разложима, то она допускает либо р-разложение, либо з-разложение, либо Н-разложение. А именно, так 248 ч пь ГРАФЫ и сити как Г(а, Ь) разложкма, то ояа допускает разложевие на Г,(а, Ь) (ввешяяя сеть) и Г,(а'", Ь'"), ..., Г~(а'"', Ьее) (виутрекиие сети). Если вкешвня сеть есть либо Гь(а, Ь), либо Г„'(а, Ь), либо сеть класса Н, то мы имеем одно из укаэанных разложений. Если это ие так, то Г„(а, Ь) разложима и мы получаем другое разложение сетп Г(а, Ь) иа сеть Г„(а, Ь) (внешяяя сеть) и Г,(а,~~, Ь;~~), ...
..., Гь (а,, Ь, ) (внутренние сети), причем сеть <ьо а~ Гэ (а, Ь) имеет меньше ребер, чем сеть Г„(а, Ь) (Ь' ( Ь). В случае, если внешняя сеть Г„(а, Ь) есть либо Г„",(а, Ь), либо Г„' (а, Ь), лабо сеть класса Н, мы получаем искомое Ф разложение. В противном случае сеть Гэ(а, Ь) разложима и процесс повторном спова.
Так как сеть Г(а, Ь) имеет коиечиое число ребер, то в конце концов мы построим требуемое разложение. Теперь остается показать, что тип разложения определяется единственным образом. Предположим, что сеть Г(а, Ь) допускает Н-разложенив. а) Тогда она ие может распадаться ка два параллелькых куска. Иначе внешняя сеть распадается также иа два куска, т. е. является разложнмой либо совпадает с Г",(а, Ь), что при Н-разложеяии невозможно. б) Оиа яе может иметь и разделяющей вершины.
В противном случае разделяющей вершиной будет внутреикяя вершина внешней сети. Последнее при Н-разложеиии иевозмо~кко в силу следствия леммы 4. Ясно также, что два свойства: распадение сети иа два параллельных куска и наличие разделяющей вершины —. взаимоисклзочающи. Таким образом, разложпмая двухполюсная сеть обладает в точности одним иэ следующих свойств: распадается па два параллельных куска, имеет разделяющую вершину, допускает Н-разложекие. 1.
Разложимая сеть распадается па два параллельных куска в том и только том случае, если оиа р-разложима. 11. Разложимая сеть имеет разделяющую вершииу тогда и только тогда, когда ояа г-разложима. 111. Раэложимая сеть ие распадается иа два параллельиых куска и ие имеет разделязощей вершины в том и только в том случае, если ояа Н-разложима. Лемма доказана. Определеиие..р-разложекие сети Г(а, Ь) иазывается р-расщеплением, если внутренние сети разиожеиия 249 Гл. 2. сети отличны от сетей вида Гтт (а, Ь) и сетей, являющихся р-разложимыми; в-разложение сети Г(а, Ь) называется в-расщеплением, если внутренние сети разложения от- личны от сетей вида Г',(а, Ь) и сетей, являющихся в- разложимыми; Н-разложение сети Г(а, Ь) нааывается Н-расщеплением. Заметим, что сети Гь и Гь(Ь) 3) являются разло- жимыми, но не допускающими расщепления.
Прим ер 6. Рассмотрим сеть, изображенную на рвс. 25. Очевидно, что разложение этой сети на сеть С ' '— «в' Г,(а, Ь) и сети Г, (а, с), Г,(е, Ь) (см. рис. 26, а)) не является з-расщепле- Рис. 25 вием, так как сеть Г, (е, Ь) есть сеть вида Г',(с, Ь). В то же время в-разложение на сеть Гв(а, Ь) и сети Г, (а, с), Г,(с, Ы), Г,(д, Ь) (см.рис. 26, б)) является в-расщеплением. Данный пример показывает, что для сети Г(а, Ь) мо- жет существовать несколько разложений.
г«для г М ««О Гт Г«,с> «С с« С о — -о й' Гт"т«,сэ Г' Ф,Ж г~ ббпр г,'т«,й Ряс. 28 Определение. Внутренняя вершина с сети Г(а, Ь) зависит от вершины а той же сети, если каждая цепь, проходящая через с, проходит также через а. Определение. Внутренние вершины с и а сети Г(а, Ь) называются эквивалентнызш, если вершина с зависит от вершины И и вершина а' зависит от вершины с. О и р е д е л е н и е. Внутренняя вершина с сети Г(а, Ь) называется минимальной, если, какова бы ни была внутренняя вершина д сети Г(а, Ь), либо с эквивалентна д, либо с не зависит от а.
Ч. ПЕ ГРАФЫ И СЕТИ П р и м е р 7. Рассмотрим сеть Г (а, 5), изображенную на рис. 27. Здесь вершина ( зависит от вершины в, вершина в эквивалентна вершине у, вершины с и а' являются минимальными. Из определений следует, что отношения вависимости и эквивалентности удовлетворяют аксиоме транзнтивности, а отношение эквивалентности — также и рефлекснвности.
Рвс. 28 Рвс, 27 Лемма 7. Если Г(а, 6) допускает Н-разлозссние, то совокупность минимальных вершин совпадает с совокупностью внутренних вершин внешней сети. Доказательство. Пусть с — минимальная вершина; покажем, что она принадлежит множеству внутренних вершин внешней сети. Допустим, что это не так. Тогда с принадлежит некоторой внутренней сети.
Очевидно, что с зависит от полюсных вершин атой сети. Так как внешняя сеть — Н-сеть, то по крайней мере одна из данных полюсных вершин является внутренней вершиной исходной сети. В этом случае с не является минимальной вершиной. Пусть теперь с — внутренняя вершина внешней сети, покажем, что она минимальна. Для этого достаточно установить, что с не зависит ни от какой другой внутренней вершины с(, т.
е. что существует цепь, проходящая через с и не проходящая через а. Очевидно, вершина а' либо является внутренней вершиной внешней сети, и тогда мы воспользуемся леммой 4, либо является внутренней вершиной некоторой внутренней сети (см. рис. 28). Обозначим через е и 7 полюса этой сети. Возможны следующие подслучаи. а) Вершина е совпадает с полюсом, например а, вершина ) совпадает с вершиной с. Тогда применяем лемму 5.
Учитывая замечание на с. 247, мы получим цепь, проходящую черев с и не проходящую через 1(, 251 гл. ". сгтп б) Одна пз вершин, например г', не совпадает ни с полюсом сети пн с вершиной с, Здесь применим лемму 4. Учитывая замечание на с. 247, мы опять получим цепь, проходящую через с н не проходящую через И. Т е о р е и а 3.
Если сильно связная сеть Г(а, Ь) разложилш и отлична от сетей Г,"„Гь*(1~3), то она допускает единственное расщепление. Доказательство. Мы уже видели, что тип расщепления единствен. Поэтому остается показать единственность расщепления внутри данного типа. Случай 4. Сеть Г(а, Ь) распадается на два параллельных куска. Проведем разбиение всех цепей сети на классы.
Две цепи А' н А" относятся к одному классу тогда н только тогда, когда на цепях А' н А" найдутся внутренние вершины (соответственно с' и с"), которые можно соединить цепью А~", не проходящей через полюса (отсюда следует, что н любая пара внутренних вершин этих цепей может быть соединена цепью, не проходящей через полюса). Такое определение корректно, поскольку если внутренние вершины цепей А' и А " могут быть соединены цепями, не проходящими череа полюса, и внутренние вершины цепей А" и А"' — цепями, не проходящими через полюса, то н внутренние вершины цепей А' и А"' могут быть соединены цепями, не проходящими через полюса. Таким образом, мы получаем разбиение на классы и это разбиение определяется однозначным образом.
Дан- ное разбиение порождает р-расщепление на сети Гь'(а, 6), Г,(а, Ь), ..., Гь (а, Ь) (каждая из сетей Г,(а, Ь) (Е = 1, ..., Ь) отлична от Гет(а, Ь) и не допускает р-разложений; кроме того, хотя бы одна пэ них нетривиальна, так как Г(а, Ь)-ь Гьт(а, Ь)). Случай 2.
Сеть Г(а, Ь) имеет разделяющие вершины с„..., с,, Легко видеть, что, двигаясь по любой цепи от полюса а к полюсу Ь, разделяющие вершины встречаются в одном и том же порядке (пусть с„..., с,,). Пусть Г,(а, с,), Г,(с„с,), ..., Г,(с, „Ь) — сети, образованные из отрезков этих цепей между соответствующими вершинами. Как и в доказательстве леммы 3, легко покааать, что эти, сети не имеют общих вершин, отличных от своих 252 Ч. П1. ГРАФЫ П СЕТИ полюсов. Ыы приходим к в-расщеплению сети Г(а, Ь) па сеть Гь(а, Ь) и сети Г,(ао с,), Г,(с„с,), ..., Г,(с„„Ь), так как Г(а, Ь) ФГи(а, Ь), и, значит, хотя бы одна из внутренних сетей нетривиальна.
Из построения вытекает однозначность. Случай 3. Сеть Г(а, Ь) допускает П-разложение. Как это следует из леммы 7, оно однозначно. В самом деле, минивг мальные вершины зада- 'Ъ ют все внутренние вершины внешней сети, пара минимальных вер- ШИН ИЛН ПОЛЮСОВ С, 1( вз задает ребро внешней в м сети тогда и только тогвв в да, когда существует в цепь, соединяющая с и «г Н и не проходящая через другие миннмальРвс. 29 ные вершины или полюса. Теорема докааана. Рассмотрим некоторую сеть Г(а, Ь).
Вели она допускает расщепление, то осуществим ее расщепление. В результате получим сети с меньшим чпслом ребер. Опять вг г <:>" —— вг вв вт вп сы вгг Рвс. 30 расщеппм те внутреннле сети, которые допускают расщепление, и т. д. Этот процесс аакончится на конечном шаге и мы прядем к сетям либо тривиальным, либо неразложимым, либо сетям вида Гьг, Гь()с) 3). Система всех нетрнвпальпых сетей, которая возникает при рас- 253 Гл. 2. Свтп щеплепии сети Г(а, Ь), вазывается каноии лескам расщеплением сети Г(а, Ь). Таклллл образом, яами доказана Теорема 4.
Ьалсдая сильно сеязпая нетриеиальнач сеть Г(а, Ь), допускающая расщепление, имеет единственное каноническое расщепление. Пример 8. Сеть Г(а, 'Ь), изображенная иа рис. 29, при каноническом расщеплении разлагается иа сети (см. рис. 30). $4. и-сети Важвым подклассом двухполюсяых сетей из двухобьектиых наборов является класс п-сетей. О п р е д е л е и и е. Сеть, являющаяся суперпозицией сетей Гл(а, Ь) и Г",(а, Ь), называется я-сетью. Даввое определение эквивалентно другому: двухполюсиая сеть иэ двухобъектяых наборов, которая сильно связка, будет я-сетью, если каиоиическое расщеплекие содержит сети двух типов Г),(а, Ь) и Гь(а, Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
