Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
250
Ч. III. ГРАФЫ И СЕТИ
Пример 7. Рассмотрим сеть Г (а, Ъ), изображенную на рис. 27. Здесь вершина / зависит от вершины е, вершина е эквивалентна вершине g, вершины с и d являются минимальными.
Из определений следует, что отношения зависимости и эквивалентности удовлетворяют аксиоме транзитивности, а отношение эквивалентности — также и рефлексивности.
Лемма 7. Если Г (я, Ь) допускает Н-разложение, то совокупность минимальных вершин совпадает с совокупностью внутренних вершин внешней сети.
Доказательство. Пусть с — минимальная вершина; покажем, что она принадлежит множеству внутренних вершин внешней сети. Допустим, что это не так. Тогда с принадлежит некоторой внутренней сети. Очевидно, что с зависит от полюсных вершин этой сети. Так как внешняя сеть — II-сеть, то по крайней мере одна пз данных полюсных вершин является внутренней вершиной исходной сети. В этом случае с не является минимальной вершиной.
Пусть теперь с — внутренняя вершина внешней сети, покажем, что она минимальна. Для этого достаточно установить, что с не зависит ни от какой другой внутренней вершины ё, т. е. что существует цепь, проходящая через с и не проходящая через ё. Очевидно, вершина ё либо является внутренней вершиной внешней сети, и тогда мы воспользуемся леммой 4, либо является внутренней вершиной некоторой внутренней сети (см. рис. 28).
Обозначим через ей/ полюса этой сети. Возможны следующие подслучаи.
а) Вершина е совпадает с полюсом, например а, вершина / совпадает с вершиной с. Тогда применяем лемму 5. Учитывая замечание на с. 247, мы получим цепь, проходящую через с и не проходящую через ё.
а
Рлс. 27
Рис. 28
ГЛ. 2. СЕТИ
251
б) Одна из вершин, например /, не совпадает ни с полюсом сети ни с вершиной с. Здесь применим лемму 4. Учитывая замечание на с. 247, мы опять получим цепь, проходящую через с и не проходящую через й.
Теорема 3. Если сильно связная сеть Г(й, &) разложима и отлична от сетей Г?, Г^/с^З), то она допускает единственное расщепление.
Доказательство. Мы уже видели, что тип расщепления единствен. Поэтому остается показать единственность расщепления внутри данного типа.
Случай 1. Сеть Г(я, Ъ) распадается па два параллельных куска. Проведем разбиение всех цепей сети на классы. Две цепи А' и А" относятся к одному классу тогда и только тогда, когда на цепях А' и А" найдутся внутренние вершины {соответственно с' и с"), которые МОЖНО соединить цепью АС1С», не проходящей через полюса (отсюда следует, что и любая пара внутренних вершин этих цепей может быть соединена цепыо, не проходящей через полюса). Такое определение корректно, поскольку если внутренние верпшны цепей А' и А" могут быть соединены цепями, не проходящими через полюса, и внутренние вершины цепей А" и А"' — цепями, не проходящими через полюса, то и внутренние вершины цепей А' и А'" могут быть соединены цепями, не проходящими через полюса. Таким образом, мы получаем разбиение па классы
«С* .... И*
и это разбиение определяется однозначным образом. Данное разбиение порождает р-расщеиление на сети
Га (а, Ь), Г! (а, Ь), Гл (а, Ь)
(каждая из сетей Г,(а, Ъ) (г = 1, ..., Ь) отлична от Г? (я, Ь) и не допускает р-разложений; кроме того, хотя бы одна из них нетривиальна, так как Г (а, Ь)фТ%(а, Ь)).
Случай 2. Сеть Г (о, 6) имеет разделяющие вершины си ..., сл_!. Легко видеть, что, двигаясь по любой цепи от полюса а к полюсу Ь, разделяющие вершины встречаются в одном и том же порядке (пусть с„ ..., ел_,). Пусть ГДя, с,), Г2(с1, с2), ..., Гл(сл_„ Ь) — сети, образованные из отрезков этих цепей между соответствующими вершинами. Как и в доказательстве леммы 3, легко показать, что эти сети не имеют общих вершин, отличных от своих
252
Ч. III. ГРАФЫ И СЕТИ
полюсов. Мы приходим к ^-расщеплению сети Г (а, Ь) па сеть П (я, Ь) и сети Г1(й1, С!), с2), .Гл(сл-1( Ь),
так как Г (а, Ъ) Ф 1* (л. ?>), п, значит, хотя бы одна из внутренних сетей нетривиальна. Из построения вытекает однозначность.
Случай 3. Сеть Г (о, Ъ) допускает //-разложение.
Как это следует из леммы 7, оно однозначно.
В самом деле, мини-Щ мальные вершины зада-
ют все внутренние вершины внешней сетп, пара минимальных вершин или полюсов с, с? задает ребро впешней сети тогда и только тогда, когда существует
пепь, соединяющая с и с1 и не проходящая через другие минимальные вершины или полю-
са. Теорема доказана.
Рассмотрим некоторую сеть Г (а, Ь). Если она допускает расщепление, то осуществим ее расщепление. В результате получим сети с меньшим числом ребер. Опять
-•?'''я
а-? а*
11
Рис, 30
73
72
расщепим те внутренние сети, которые допускают расщепление, и т. д. Этот процесс закончится иа конечном шаге и мы придем к сетям либо тривиальным, либо неразложимым, либо сетям вида Г?, Г? (А: ^ 3). Система всех нетривиальных сетей, которая возникает при рас-
щеплении сети Г (а, Ь), называется каноническим расщеплением сети Г (а, Ь). Таким образом, пами доказана
Теорема 4. Каждая сильно связная нетривиальная сеть Г(а, Ъ), допускающая расщепление, имеет единственное каноническое расщепление.
Пример 8. Сеть Г (а, Ь), изображенная на рис. 29, при каноническом расщеплении разлагается на сети (см. рис. 30).
