С.В. Яблонский - Введение в дискретную математику (1060464), страница 34
Текст из файла (страница 34)
равны х», следующие а» чисел равны хх и т. д., мы и получим неравенство (»). Путем вределького верехода неравенство (е) можно распространить и на иррациональные числа $», ..., $т, однако а данном случае этого даже не требуется. Логарифмвруя неравенство (л), мы получим неравенство $» 1в ц+... + 1 !их„"!сЯ»х»+...
+ $„,» 1, которое кри х, = 1/$», ..., хт = 111т превращается в неравенство для энтропии. гл. 2. Сити 237 тур (Ь„..., Ь ) с заданными параметрами н, т, Ь. Последнее мажорируется числом целых неотрицательных решений уравнения Ь, + Ь, +... + Ь„Ь. Это сводится и расстановке т — 1 перегородок между Ь единицами. Мы удовлетворимся грубой оценкой (Ь+ 1)" ' (каждая перегородка может занимать Ь+1 положение). Таким образом, получаем Следствие. Я(еа р,т, Ь)~(с(е» )»,ш)" (Ь+1)" 'Ьш и" 4,' ( с' (е«, (», т)»Ьш-»)л Полученная оценка как частный случай содержит и оценку для числа графов т (Ь) = Ю(0, 2, 2, Ь) < с"Ь".
Отсюда получается оценка и для числа графов с двумя выделенными вершинами и без изолированных неполюсных вершин (зту оценку легко получить и из следствия теоремы 3 гл. 1) Я(2 2 2 Ь)(свЬ~ $3. Двухполюсные сети нз двухобъектных наборов Здесь мы рассматриваем важный класс конечных сетей, имеющих два различных полюса (е, 2) и состоящих исключительно из двухобъектных наборов (е, 2, при $ 1, 2, ..., Ь). Легко видеть, что данный класс совпадает с классом конечных графов, в каждом из которых выделены две вершины — полюса.
Подобного рода сети »Я(Е«; Е„..., Е ) мы будем обозначать через Г(а, Ь), где Е, (а, Ь). Для сетей, так же как и для графов, вводится понятие пути, соединяющего некоторые его вершины а«, Ь'. В случае, если вершины а' и 6' совпадают с полюсами а и Ь соответственно, то мы употребляем термин «путь» без указания вершин, которые оя соединяет. Сеть называется связной, если соответствующий граф связен. Если сеть Г(а, Ь) связна, то для каждого ребра можно указать путь, проходящий через него. Заметим, что для связных Ч.
1П. ГРАФЫ И СЕТИ сетей Л йы 0 <Е»). » 1 Следовательно, связная сеть полностью определяется перечислением ев ребер н указанием полюсов. Дальнейшие рассуждения этого параграфа будут относиться исключительно к связным сетям. Гг (в,'д) Гг (е,д"! Г»:»т,'О Ркс. 9 Пусть Г,(а', Ь') и Г,(а", Ь ) — две непересекающиеся связные сети, т. е. Г,(а', Ь') — й1(Ео' Е» ° ° ., Ел). Го (а", Ь") йо(Е,; Е„..., Ел.), Р где й, 9 й, = Л. Рассмотрим произвольное ребро Е» (а', Ьо) сети Г,(а', Ь'). Исходя нз геометрических соображений (см. рис.
9), нетрудно дать определение операции подстановки вв»есто ребра Е; сети Г,(а", Ь"), приводящей к новой сети Г(а', Ь'). О п р еде л е н и в. Результатом подстановки вместо ребра Е» (ао, Ь'), принадлежащего сети Г,(о', Ь'), сети Го(а", Ь") называется каждая из сетей Г'(а', Ь') и Г" (а', Ь'): Г'(а', Ь') =* 1 1П П1 й(Ео*' Е» ° ° ' Е»-» Е» ~ ° ° .
~ Ел., Е»+» ..., Ел), Г(а', Ь') -й(Еоз Е», ° з Е»-» Е» ° ° ю Ел з Е~+1, ° °, Ел~)~ где й ° й, 0 (й»Ч(а", Ь"))). Набор Е; 1 (! 1, ..., )»") получается из набора Е, заменой а" на а' и Ь" на Ь', набор Ь",~ () = 1, ..., Ь") получается из набора Е; заменой ао на Ь' н Ь" па а'. 230 Гл, х сати Определение. Сеть Г(а, Ь), получающаяся из сетей, изоморфных сетям Г,(а', Ь'), ..., Г (а'"', Ь' '), путем применения конечного числа операции подстановки, называется еуперпоэицией этих сетей, П р и м е р 4. Сеть Г(а, Ь), изоб- с раженная на рис. 10, является суперпозициейсетей Г,(а', Ь'), Г,(а, Ь"), Г,(а"', Ь"') (см. рис. 11).
В самом деле, возьмем сеть Г,(а'", Ь'т), изоморфную сети Г,(а"', Ь"), и подставим ее вместо ребра сети Г,(а"', Ь ). Полученную сеть Рсс. 10 подставим в сеть Г,(а', Ь') вместо ребра (с, й). Затем, осуществляя подстановку в етой промежуточной сети вместо ребра (а', с) сети Г,(а", Ь'), получим сеть Г(а, Ь). Замечания. 1. Легко видеть, что операция супер- позиции является ассоциативной операцией.
а" е Ь Ьт(ерЬу 12 (е", Ь") Рес. И 2. Множество всех связных сетей (Г(а, Ь)) вместе с операцией суперпозиции определяет функциональную систему с операцией. Пусть в сети Г(а, Ь) взяты два пути А... и А,, с, соединяющие вершины а' и Ь'. Определение. Путь А" ((а', а;,), (аче а;,), ..., (а;,, Ьс)) навывается подпутем пути Р А с с ((ас, а; ), (а;, а; ), ..., (а;... Ьс)), если последовательность ребер ((ас, а; )а (а,, а; )... „(а;, „Ьс)) ч. пь гряды н сати получается из последовательности ребер ((а', а,о), (а,„а,,), ..., (аб ., Ьо)] путем удаления некоторого подмножества ребер, Подпуть А,о,о пути А,о,о~ отличный от самого пути А,ооо, называется собственных подпутех. О и р е д е л е н и е.
Путь А, ы, соединяющий вершины а' и Ь' сети Г(а, Ь), называется цепью, соединяющей эти вершины, если он не содержит собственных подпутей. Замечание. В случае, если вершины а' и Ь' совпадают с полюсами а и Ь, вместо слов «цепь, соединяющая а и Ь», будем говорить просто «цепью Очевидно, что путь является цепью тогда и только тогда, когда он не проходит дважды через одну вершину, л' с лов Ф / с Рис.
12 Рис. 13 П р и м е р 5. Рассмотрим сеть Г (а, Ь), изображенную на рис. (2. Очевидно, что ((а, с), (с, А), (д, с), (с, Ь)) является путем, но не является цепью, так как содержит собственный подпуть ((а, с), (с, Ь)). Путь ((а, с), (с, Ь)) является цепью. Легко видеть, что сеть, содержащая Ь (Ь ~ 0) ребер, ивтеет бесконечное число путей и конечное число цепей. Введем понятие, которое позволит еще сузить класс рассматриваемых сетей. Определение.
Связная сеть Г(а, Ь) называется сильно связной, если через каждое ее ребро проходит некоторая цепь. Очевидно, что не всякая связная сеть является сильно связной (см. пример 5). Ниже доказываются две леммы о). Первая из них дает условие, при котором через данное ребро можно провести цепь. Она служит основой для доказательства второй лем- *) Дальше салом«иве связано с работ«ив А. В. Кузи«иова (16) и Б. А. Трахтоиброта (31], гл. г.
сети мы, выясняющей необходимые и достаточные условия сильной связности. Лемма 1. Пусть Г(а, Ь) — произвольная сеть (нв обязательно связная) и пусть через вершины с' и с" (с'чь с") сети Г проходят цепи А' и А " (нг исключено, что А' А"). Если вершины с' и с" можно соединить цепью А..., имеющей с цгпями А' и А" общими только концввгаг вершины с' и с", то существует цепь А, частью которой является А„, .
Доказательство. Если обе вершины с' и с" принадлежат одновременно хотя бы одной цепи, например, А', то тогда искомая цеиь А получается из А' заменой части цепи А', расположенной между с' и с", на Аг г' В противном случае вершины с' и с" являются внутренними. Обозначим через с первую общую для цепей А' и А" вершину, если двигаться по цепп А" от вершины с" к полюсу Ь (с чье' и от'= с"). На рзс. 13 изображена одна из двух возможных ситуаций. Обоэначпм через А путь, получающийся из цепи А' заменой участка с'с на путь, состоящий из цепи А.; и участка цепи А" между вершинами с" и с.
Очевидно, А является искомой цепью. Пусть в сети Г(а, Ь) выделено некоторое подмножество ребер Г', которое, очевидно, определяет граф. Вершина с графа Г' называется граничной, если она является либо полюсом сети Г(а, Ь), либо концом ребра сети Г(а, Ь), не принадлежащего Г'. О и р е д ел е н и е. Подмножество Г' ребер сети Г(а, Ь) называется отростком, если Г' обладает единственной граничной вершиной. Например, на рис. 12 подмножество ребер ((с, д)) является отростком, так как имеет одну гранпчную вершину с, а подмножество ребер ((а, с), (с, Ь)) отростком не является, поскольку опо имеет три граничные вершины;а,с,Ь.
Л е и м а 2. Связная сеть Г(а, Ь) является сильно связной тогда и только тогда, когда Г(а, Ь) нв содержит отростков. Д о к а з а т е л ь с т в о. Пусть связная сеть Г(а, Ь) содержит отросток Г'. Обозначим через с его граничную вершину. Рассыотриы произвольное ребро, принадлежащее этому отростку. Ясно, что всякий путь, проходящий через данное ребро, должен по крайней мере два раза пройти через вершину с. Ввиду этого через ребро. не про- Ч.
111. ГРАФЫ П СЕТИ ходит нн одной цепи. Следовательно, сеть Г(а, Ь) не является сильно связной. Пусть теперь связная сеть Г(а, Ь) не является сильно связной. Покажем, что тогда она содержит отросток. Так как Г(а, Ь) не является сильно связной, то существуют ребра, череа которые не проходит ни одной цепи. Пусть Г' — максимальное связное подмножество ребер, обладающих этим свойством *). В силу связности сети Г(а, Ь) граф Г' обладает по крайней мере одной граничной вершиной. Предположим, что Г' имеет по крайней мере две граничные вершины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
