Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
о с
Рис. 16
неразложимые сети: параллельное соединение двух ребер Га (ах Ь) и последовательное соединение двух ребер
Га (а, Ъ) (см. рис. 17). Множество остальных нетриви-
альных неразложимых сетей обозначим через Н и сеть, принадлежащую Нл будем называть Н-сетью. С сетями Га (й, Ь) и Г|(а, Ь) связаны два бесконечных множества сетей.
Множество Р, состоящее из сетей (я, &), — параллельное соединение к ребер (& = 2, 3, ...). Очевидно, что ГЕ (я, Ь) при к> 2 является суперпозицией сетей
Го (а, Ь) (см. рис. 18).
16*
т
Ч. III. ГРАФЫ И СЕТИ
Множество 5, состоящее из сетей Г| (а, Ъ),— последовательное соединение к ребер (к~ 2, 3, ...). Очевидно, что II (я, Ь) при к > 2 является суперпозицией сетей Га (я, Ъ) (см. рис. 18).
/-/to,» г/ад
Рис. 17
Опр еделение. Сильно связная сеть Г (я, Ь) распадается на два параллельных куска, если множество всех ее цепей можно разбить на два непустых класса так, что любые две цепи из разных классов не имеют общих внутренних вершин. Очевидно, каждая из сетей Г? (а, Ъ) (&> 2) распадается на два параллельных куска.
фз,д) ГрШ
Рис. 18
Определение. Пусть с — внутренняя (т. е. отличная от полюсов) вершина сильно связной сети Г (я, Ь). Вершина с называется разделяющей, если каждая цепь проходит через с. Очевидно, что каждая йз внутренних вершин сети Г^(я, Ъ) является разделяющей.
Пусть с — разделяющая вершина сети Г (а, Ь) . Рассмотрим в каждой цепи отрезок от вершины а до вершины с. Очевидно, что совокупность этих отрезков цепей порождает сеть А (я, с) cj полюсами в вершинах я и с. Аналогично, если выделить в каждой цепи отрезок от вершины с до вершины Ъ, то получим сеть Гг (с, Ь),
Лемма 3. Пусть с — разделяющая вершина сильно связной сети Г (я, Ь). Тогда Г (а, 6) получается суперпозицией сетей Г, (а, Ъ), 1\(я, с), Г2(с, Ь) {последовательное соединение сетей Г} (я, с) и Г2(с, Ь)}.
ГЛ. 2. СЕТИ
245
Доказательство следует из того факта, что сети ГДа, с) и Гг(с, Ь) не имеют общих внутренних вершин. В самом деле, если это не так, то существуют две цепи Аас и АсЬ, соответственно, сетей Г, (я, с) и Г2(с, 6), которые имеют общую внутреннюю вершину (см. рис. 19).
Обозначим через d первую общую вершину этих цепей, если двигаться по цепи Аас от точки а. Очевидно, что отрезок цепи Аа,-, между вершинами а и d и отрезок цепи АсЬ между вершинами d и b порождают цепь, не проходящую через с. Последнее противоречит тому, что вершина с является разделяющей. Лемма доказана.
Определение. 11 усть с — вершина сети Г (а, Ъ), тогда совокупность всех се ребер, имеющих своим концом вершину с, называется звездой (с центром в с). Если с — полюс, то звезда называется полюсной.
Относительно //-сетей сформулируем следующую лемму.
Лемма 4. Если Г (я, Ъ) —И-сеть, а с и d — две различные внутренние вершины (т. е. отличные от полюсов), то существует цепь, проходящая через d и не проходящая через вершину с.
Доказательство-. Данное утверждение вытекает из более сильного факта: если из Г (я, Ь) удалить звезду с центром в с, то полученная сеть будет сильно связной.
Возможны три случая.
а) Удаление звезды приводит к распадению графа на две связные компоненты, которые не имеют общих вершин (см. рис. 20). Очевидно, в этом случае вершина с будет разделяющей, и в силу леммы 3 исходная сеть будет разложимой (одна из компонент будет содержать не менее двух ребер, так как //-сеть имеет более четырех ребер), а это невозможно.
б) Удаление звезды приводит к сети, которая является связной, но не сильно связной. В силу того, что полученная сеть не силъпо связная, она имеет отросток с граничной точкой d (см. рис. 21). Поскольку исходная сеть
Рис. 19
Рис. 20
246
Ч. III. ГРАФЫ И СЕТИ
Г (я, Ь) сильно связная, то отросток должен иметь граничные вершины с данной звездой и отличные от д. В таком случае отросток с частью ребер звезды образует двухполюсную сеть Т'(с1, с). Последнее означает, что Г (а, Ь) — разложима, мы пришли к противоречию.
в) Остается последняя возможность — удаление звезды приводит к сильно связной сети. Лемма доказана.
Следствие. Н-сетъ не имеет разделяющих вершин.
Лемма 5. Если Г (а, Ь)—Н-сетъ и (о, с)—ребро, принадлежащее полюсной звезде, то после удаления этого ребра получим сильно связную сеть.
Доказательство (аналогично доказательству предыдущей леммы).
а) Удаление ребра дает сеть, не являющуюся связной. Очевидно, тогда с будет разделяющей вершиной сети Г (а, 6), что противоречит следствию леммы 4.
б) Удаление ребра дает связпую сеть Г '(а, Ь), но не сильно связную. Обозначим граничную вершину отростка сети Г'(я, &) через д (см. рис. 22). Ясно, что этот отросток вместе с ребром (а, с) дает двухполюсную сеть Г "(а, й). Последнее противоречит неразложимости
в) Остается последняя возможность: сеть Г'(а, Ъ) — сильно связная.
Рассмотрим разложимую сеть Г (я, Ь). Пусть Г (а, Ъ) есть результат подстановки вместо ребер Еи Ен (И ^ 2) сети Г0(я, 6) = 9Л(Е0; Еи ..., Ек) соответственно сетей ГДа113, 6т), Гл(о(Л\ Ь(ЛЗ), из которых хотя бы одна нетривиальна.
Разложение сети Г (а, 6) на внешнюю сеть Г0(я, 6) и внутренние сети ?>(1)), ..., 1\(а(,1), 6(ЛЗ) допускает
