Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Л' Определение. Связная сеть Г (я, Ь) называется сильно связной,.еели через .каждое ее ребро проходит некоторая цепь.
Очевидно, что не всякая связная сеть является сильно связной (см. пример 5).
Ниже доказываются две леммы *). Первая из них дает условие, при котором через данное ребро можно провести цепь. Она служит основой для доказательства второй лем-
*) Дальше изложение связано с работами А. В. Кузнецова [16] и Б. А. Трахтенброта [31].
ГЛ. 2. СЕТИ
241
мы, выясняющей необходимые и достаточные условия сильной связности.
Лемма 1. Пусть Г (я, Ь)—произвольная сеты {не обязательно связная) и пусть через вершины с’ и с" {с'Фс") сети Г проходят цепи А' и А" {не исключено, что А,=1А"). Если вершины с' и с" можно соединить цепью Ас/с«, имеющей с цепями А' и А" общими только концевые вершины с' и с", то существует цепь А, частью которой является Ае/Сп.
Доказательство. Если обе вершины с' и с” принадлежат одновременно хотя бы одной цепи, вапрзшер, А\ то тогда искомая цепь А получается из А' заменой части дени А\ расположенной между с и с", на -Ай‘С»-В противном случае вершины с и с" являются внутренними. Обозначим через с первую общую для цепей А’ л А" вершину, если двигаться ио цепи А" от вершин:ы с" к полюсу Ь (с Ф с и с Ф с"). На рис. 13 изобра_жена одна из двух возможных ситуаций. Обозначим через А путь, получающийся из цепи А' заменой участка с'с на путь, состоящий из цепи Ас/с» и участка цепи А " ьяежду вершинами с" и с. Очевидно, А является искомой ц«пью.
Пусть в сети Г (а, Ь) выделено некоторое подмноэкест-во ребер Г', которое, очевидно, определяет граф. Вер шина с графа Г' называется граничной, если она является либо полюсом сети Г (а, Ь), либо концом ребра сети Г(«з, ?>), не принадлежащего Г'.
Определение. Подмножество Г7 ребер сети Г (а, 6) называется отростком, если Г7 обладает единственной граничной вершиной.
Например, на рис. 12 подмножество ребер {(с, д)} является отростком, так как. имеет одну граничную* вершину с, а подмножество ребер {(а, с), (с, ?>)} отростком не является, поскольку оно имеет три граничные вершины: а, с, Ь.
Лемма 2. Связная сеть Г (а, Ь) является сильно связной тогда и только тогда, когда Г (а, Ь) не содержим отростков.
Доказательство. Пусть связная сеть Г (а, 5) содержит отросток Г7. Обозначим через с его граночнук вершину. Рассмотрим произвольное ребро, принадлежащее этому отростку. Ясно, что всякий путь, проходящш через данное ребро, должен по крайней мере два. разг пройти через вершину с. Ввиду этого через ребро не про
16 С. В. ЯблоыскиЛ
Ч. III. ГРАФЫ И СЕТИ
ходит ип одной цепи. Следовательно, сеть Г (а, 6) не является СИЛЬНО СВЯЗНОЙ.
Пусть теперь связная сеть Г (а, Ъ) не является сильно связной. Покажем, что тогда она содержит отросток. Так как Г(д, Ь) не является сильно связной, то существуют ребра, через которые не проходит ни одной цепи. Пусть Г' — максимальное связное подмножество ребер, обладающих этим свойством*). Б силу связности сети Г (а, Ъ) граф Г' обладает по крайней мере одной граничной вершиной. Предположим, что Г' имеет по крайней мере две граничные вершины.‘Так как граф Г' связен, то каждая пара граничных вершин может быть соединена цепью, целиком принадлежащей Г'. Пусть с' и с"—две такие граничные вершины, что указанная цепь Лс#с« не содержит никаких других граничных вершин. Ясно, что через вершины с' и с" можно провести цепи (соединяющие полюса) А' й А". Очевидно, что цепь Нс/с» имеет с цепями А' и А" общими только концевые вершины с и с". Применяя к цепям А', А" и Ас>лемму 4, мы построим цепь, частью которой будет Ас/сп^ что противоречит определению Г'. Следовательно, Г' обладает единственной граничной вершиной, т. е. Г' является от-
о ..... - —о ростком. Лемма доказана.
° ® В дальнейшем будем рассматривать
Рис. 14 только сильно связные сети. Рассмот-
' рим сеть Го (я, Ь) — $Я0(Е0\ Е±), где 2ТС = (й, Ь), 2?0 = ~ (а, Ъ) (см. рис. 44).
Эту сеть будем называть тривиальной сетью.
Определение. Сильно связная сеть называется разложимой, если существуют такие нетривиальные не-пересекакнциеся сети Г^а, Ъ) иГ2(а', 6'), что сеть Г (а, Ь) есть результат подстановки сети Г2(а\ Ь') вместо некоторого ребра сети 1\ (о., Ъ). Очевидно, сеть, приведенная на рис. 10, является разложимой.
^Определение. Сильно связная сеть Г (а, Ъ}, не являющаяся разложимой, называется неразложимой.
На рис. 45 представлены примеры трех нетривиальных неразложимых сетей (полюса помечены кружочками).
Можно показать, что любая нетривиальная неразложимая сильно связная сеть, имеющая не более шести ребер, изоморфна одной из трех сетей, представленных на рис. 45. Это означает, что не существует неразложимых'
*) Если их несколько, возьмем одно из них.
ГЛ. 2. СЕТИ
?43
сильно связных сетей с тремя, четырьмя и шестью ребрами. В то же время для каждого к > 7 существуют неразложимые сильно связные сети с к ребрами (см. [31]). Последнее легко усматривается из рис. 16, на котором
а о Ь а Ь
Рис. 15
указано построение неразложимых сетей с Л (Л > 7) ребрами.
Цель дальнейших рассмотрений — изучение вопросов разложимости сетей. Поскольку нас будут интересовать разложения специального вида, выделим две простейшие
