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