Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
ГЛ. 2. СЕТИ
233
Заметим, что каждой укладке дерева соответствует кортеж, содержащий поровну нулей ц единиц, причем в любом его начальном отрезке нулей пе меньше, чем единиц. Если в каком-либо собственном начальном отрезке кортежа пулей и единиц поровну, то это означает, что данный кортеж соответствует укладке дерева Д полученной из укладок деревьев А и В путем объединения их корней. Отсюда видно, что по своему кортежу укладка дерева восстанавливается однозначно, т. е. имеется взаимно однозначное соответствие между укладками деревьев с к ребрами и подмножеством кортежей длины 2к, содержащих поровну нулей и единиц.
Мы имеем
г* №<(“)<2!Л = 4\
Теорема доказана.
Сравнивая верхние оценки для чисел у (к) и 6 (/г), связанных с числом графов и деревьев, мы видим, что последняя оценка существенно меньше, чем первая (при к-*- о°). Эта ситуация обусловлена тем, что деревья имеют более жесткую топологическую структуру.
Теперь мы перейдем к вопросу об оценке *числа конечных сетей для общего случая. С этой целью введем ряд обозначений, касающихся сети
ВД; Еи Д).
Пусть вi обозначает число объектов (с учетом повторений) в наборе Еи Величина е{ будет называться степенью набора. Обозначим через т максимальную степень набора, отличного от ?0, т. е.
т — тах е{.
Величину т будем называть степенью сети. Далее, пусть /г{ —число наборов степени I (без учета на-
бора Е0). Кортеж (ки к2, кт) называется степенной
т
структурой сети. Очевидно, 2 й* — Ь,. Наконец, введем
г—1
величину
иг
Iх = т 2
которую будем называть средней степенью сети.
234
Ч. III. ГРАФЫ И СЕТИ
Мы будем рассматривать класс сетей, для которых имеет место ограничение
ад = и <я4>.
1=0
Это ограничение означает, что данные сети не имеют «изолированных» вершин, отличных от полюсных, и вершин, принадлежащих наборам.
Обозначим через ?(е0, А1; ..кт) максимальное число попарно неизоморфных сетей данного класса, имеющих е0 полюсов и данную степенную структуру. Пусть ?(е0, р, т, к) обозначает максимальное число попарно неизоморфных сетей того же класса, имеющих е0 полюсов, данную среднюю степень р, максимальную степень т и число наборов к (исключая полюсный набор).
Для указанных величин имеют место оценки, составляющие содержание теоремы 2 и ее следствия.
Т е о р е м а 2 (О. Б. Лупанов [17]).
$(е0, ки ..., йт)<с(е„, р, ш)Кк^~ик.
Доказательство. Очевидно, что число вершин в наборах Еи ..Ен не превосходит величины
7П
р = 2 = р к.
1=1
Поскольку сети рассматриваются с точностью до изоморфизма, то можно считать, что полюсами являются
^1] Я2, • ? •}
Произведем оценку числа р,- сортов наборов степени ?, встречающихся в данных сетях. Поскольку среди этих сетей имеются и сети с р вершинами, для данной величины р* имеют место соотношения
= = < (Р + * - 1)*< (2р)‘ = (2и*)1,
так как
ГЛ. 2. СЕТИ 235
Заметим, что в силу монотонности 4^по і
Рі > (г) = Р =* білетно видеть, что число систем наборов степени і, каж-дая из которых содержит 1г{ наооров, не превосходит лРг-При }%і 0 имеем
НН = (Рі + Н‘~і\<(2?і)** _.
Отсюда мы получаем оценку для величины 5(е0, А1( ... кт), которую обозначим просто через ?:
т Л
5 < к+1)11«,;.
г=1
Множитель е0 + 1 отражает тот факт, что либо ни один
к
ИЗ ПОЛЮСОВ не принадлежит множеству и либо
1=1
Л
один полюс принадлежит множеству и {ЕіУ и т. д.,
І=1 Л
либо, наконец, все е0 полюсов принадлежат и (Еі)* Мы
і=і
имеем
?<(с04-1)П (2е) 1 (2ПН)1^
і—1 Л.1
Лі?Ч) г
или
т Ъ • іЬ.*
1п$<1п(*,, + 1) + 2 1пВ,,> ’У "* “
І=1 ^ *
7П
= 1п (г0 4- 1) + к (1п 2е 4- р 1п 2ц) 4* 1п к — 2 Л - 1п к-.
і=і
И^О
т
Пусть к\ = Ці. Очевидно, что2 — 1- При этих условиях
і=і
2Я6 Ч. ИГ. ГРАФЫ И СЕТИ
имеет место неравенство (для энтропии)*)
т
— 2 ЬІІ < 1п т.
І^І
(При 5 = 0 положим ?1п | — 0.) Мы получаем 1п ? ^ 1п(ей+1)+А(1ю т + 1іі 2е+р 1п 2ц) + ([.і — 1) А 1п А. Отсюда имеем
5 <{е, + 1) (2єт(2}іУ)іік^і)\
Если положить с(е0, р., т) = ('е0 + 1) Чет (2ц)11, то окончательно получим
5*(б0, А,, ..Ат)«ї с(ео, р, 7
Теорема доказана.
Полученная оценка слабо зависит от степенной структуры (/&!, ..Ат): в нее входят лишь две ее характеристики, р и т. Это позволяет легко получить и оценку для ?(е0, А) при любых фиксированных значениях
Со, р и 771. Для этого надо оценить число степенных струк-
*) Из неравенства между средним геометрическим и средпнм арифметическим
(*1 ? '' ^я)1 ” ^ (ж1 ^ Хп)
легко вывести следующее неравенство:
*51 • • ? гяГ < &1г1 + • * ? + ?тгт> (*>
где все 5* {?=1.....7п) — неотрицательные рациональные числа и
т
2П=‘-
?
Действительно, пусть п — общий знаменатель чисел 51, ..., 5т и 5( = Л{/л (1 = 1, ..т) (заметим, что пг + п2 + . ? * + пт = п). Тогда, применяя неравенство между средним геометрическим и средним арифметическим к п числам, среди которых первые щ чисел равны 2], следующие чисел равны з2 и т. д., мы и получим неравенство (*).
Путем предельного перехода неравенство (*) можно распространить, и на иррациональные числа 5ь ? • ч Е™, однако в данном случае этого даже не требуется. Логарифмируя неравенство (#), мы получим неравенство
