Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
5] 1п 21 + . . . + |щ 1п Зт 5^ 1г> (&121 + ? * ? “Ь ?та2т),
которое при гу = 1/51, гт = м%п превращается в неравенство для энтропии.
ГЛ. 2. СЕТИ
237
ТУР (^ii ? • ч h™) с заданными параметрами р, т, h. Последнее мажорируется числом целых неотрицательных решений уравнения ht + Нг +... + hm — h. Это сводится к расстановке тп — 1 перегородок между h единицами. Мы удовлетворимся грубой оценкой (fe+l)m_1 (каждая перегородка может занимать /г + 1 положение). Таким образом, получаем
Следствие.
S (е0, р, m, h) <с(е0, |х, mf{h + “1>ft <
с' (аи, р, нг)Л/1^”1)Л.
Полученная оценка как частный случай содержит и оценку для числа графов
4(h)*=S{0, 2, 2, к)<слк\
Отсюда получается оценка и для числа графов с двумя выделенными вершинами и без изолированных веполюс-ных вершин (эту оценку легко получить и из следствия теоремы 3 гл. 1)
5(2, 2, 2, k)<^ch3hh.
§ 3. Двухполюсные сети из двухобъектных наборов
Здесь мы рассматриваем важный класс конечных сетей, имеющих два различных полюса (е0 = 2) и состоящих исключительно из двухобъектных наборов (^==2, при i = 'l, 2, ../г). Легко видеть, что данный класс совпадает с классом конечных графов, в каждом из которых выделены две вершины — полюса. Подобного рода сети
Ш(Е0; Еи ..., Eh)
мы будем обозначать через Г (а, Ъ), где Ей = {й, й).
Для сетей, так же как и для графов, вводится понятие пути, соединяющего некоторые его вершины а0, Ь°. В случае, если вершины с° и Ь° совпадают с полюсами а и Ь соответственно, то мы употребляем термин «путь» без указапия вершин, которые он соедппяет. Сеть иазы-вается связной, если соответствующий граф связен. Если сеть Г (а, Ь) связна, то для каждого ребра можно указать путь, проходящий через него. Заметим, что для связных
238
Ч. III. ГРАФЫ И СЕТИ
сетей
Ж<= и <?*>.
1—1
Следовательно, связная сеть полностью определяется перечислением ее ребер и указанием полюсов.
Дальнейшие рассуждения этого параграфа будут относиться исключительно к связным сетям.
rt(aW Гг(а"Х) Г(а\Ьг)
Рис. 9
Пусть Г1(а,) Ь') и Г\{я", Ь") — две непересекающие-ся связные сети, т. е.
Г 1(а\Ь') = Ш1{Е'ЛЕ\ ?*),
El, El,),
где SMi П Шіг = Л. Рассмотрим пропзвольное ребро Е\ => = (а0, 6°) сети Г1(а/, Ь'). Исходя из геометрических соображений (см. рис. 9), нетрудно дать определение операции подстановки ^место ребра сети Г2(а", Ь"),
приводящей к новой сети Г (а', Ьг).
Определение. Результатом подстановка вместо ребра Е{ = (а0, 6°), принадлежащего сети Г, (а', Ь'), сети Гг(а", Ъ") называется каждая из сетей Г'(д', Ъ'} и Г" (а\ Ь'):
Т’{а’, Ь') =
- ® (4; Е\ в;.!, ?ІП Еії\ ?'+1, ..El,),
Г (o', b’) =
= 2Я(?^; Е\ ?',_„ ?lv, .., ?*,+,..................ЕІ,),
где Ш = (Ш!2\{(а", 6")}).
Набор Л']11 {] — 1, . получается из набора Е]
заменой а” па а0 и Ь" на Ь°, набор ?jV (/ = 1, h") получается из набора Ej заменой а" на Ь* и Ь" на а°г
ГЛ. 2. СЕТИ
239
Определение. Сеть Г (а, Ъ), получающаяся из сетей, изоморфных сетям
Г,(о', Ь'), Гж(а<“\ Ь™),
путем применения конечного числа операции подстановки, называется суперпозицией этих сетей.
Пример 4. Сеть Г (а, Ь), изображенная на рис. 10, является суперпозицией сетей Г!(а', Ь'), Гг(а", 6"),
Тя(а"\ Ъ'") (см. рис. 11).
В самом деле, возьмем сеть Г4(а1У, Ь1У), изоморфную сети Гз(а"\
Ь"'), и подставим ее вместо ребра сети Г* (а'", ?>"'). Полученную сеть Рис. 10
подставим в сеть Г!(а7, Ь') вместо
ребра (с, А). Затем, осуществляя подстановку в этой промежуточной сети вместо ребра (а\ с) сети Г2(йЛГ, Ь"), получим сеть Г (а, Ь).
Замечания. 1. Легко видеть, что операция суперпозиции является ассоциативной операцией.
в
Гг(а”дП Рис. 11
Гъ(а”’,П
2. Множество всех связных сетей {Г (а, Ь)} вместе с операцией суперпозиции определяет функциональную систему с операцией.
Пусть в сети Г(й, Ь) взяты два пути Лс0ь0 и Ааъьо, соединяющие вершины о0 и Ь°.
Определение. Путь
<0Ьо “ 1(й0. К’ °<8)> • • К-1, Ь°)1
называется подпутем пути
<оьо- ((о°.ак), (ак, а^), (а,,.,, Ь«)),
если последовательность ребер
1(в°.в1.Ма‘1-в*»)> ь°)1
240
Ч. III. ГРАФЫ И СЕТИ
получается из последовательности ребер
К“1’. °;2)- ь”)1
путем удаления некоторого подмножества ребер. Подпуть К%<> сути Лс0()0, отличный от самого путиЛ^01 называется собственным под пут ем.
, Определение. Путь АапЬо, соединяющий вершины а° и 6° сети Г (а, Ь), называется цепыо, соединяющей эти вершины, если он не содержит собственных подиутей.
Замечание. В случае, если вершины а0 и Ь° совпадают с полюсами а и Ь, вместо слов «цепь, соединяющая а и 6», будем говорить просто «цепы».
Очевидно, что путь является цепью тогда и только тогда, когда он не проходит дважды через одну вершину.
Ат с’
Ас'су /
! / 6
Рис, 12 Рис. 13
Пример 5. Рассмотрим сеть Г (а, 6), изображенную на рис. 12. Очевидно, что {(а, с), (с, с?), (д, с), (с, Ь)} является путем, но не является цепью, так как. содержит собственный подпуть {(а, с), (с, 6)1. Путь {(а, с), (с, 6)1 является цепью.
Легко видеть, что сеть, содержащая к (Л > 0) ребер, имеет бесконечное число путей и конечное число цепей.
Введем понятие, которое позволит еще сузить класс рассматриваемых сетей.
