У нас уже 176407 рефератов, курсовых и дипломных работ
Заказать диплом, курсовую, диссертацию


Быстрый переход к готовым работам

Мнение посетителей:

Понравилось
Не понравилось





Книга жалоб
и предложений

 





Название Развитие метода граничнык функционалов и его приложение к комбинаторным задачам
Количество страниц 93
ВУЗ МГИУ
Год сдачи 2010
Бесплатно Скачать 23593.doc 
Содержание Содержание
ВВЕДЕНИЕ 3

ГЛАВА 1. Оценки сумм граничных функционалов 12

1.1. Основные понятия 12

1.2. Асимптотики сумм граничных функционалов 13

1.3. Отношения между суммами граничных функционалов 16

1.4. Оценки сумм S{B) для ординарных функциональных пар 21

1.4.1. Оценки сумм S{B) для ординарных функциональных

пар 22

1.4.2. Оценки сумм S(B) для семейств rf-связных множеств 25

1.4.3. Оценки сумм S{B) для регулярных семейств 32

1.5. Оценки сумм S{B) для нерегулярных функциональных пар 35

ГЛАВА 2. Асимптотика числа антицепей в декартовой степени

звезд SI 42

2.1.Основные понятия 42

2.2. Унимодальность множества STkl 44

2.2.1. Расширительность пар слоев Sk с большими к 46

2.2.2. Расширительность пар слоев Sk с малыми к 52

2.2.3. Доказательство основного результата 58

2.3. Асимптотика числа антицепей в 5? 59

ГЛАВА 3. Оценки числа антицепей в трехзначной п-мерной

решетке Щ 64

3.1. О мощности слоев множества Е^ 64

3.2. Нижняя оценка числа антицепей в средних слоях множества Е$ 72

3.3. Логарифмическая выпуклость мощностей слоев

/г-значной n-мерной решетки 77

3.4. Расширительность пар слоев Е$ 80

ПРИЛОЖЕНИЕ 85

СПИСОК ЛИТЕРАТУРЫ 93

Введение

Значительное место в математике занимают перечислительные задачи, связанные с доказательством существования, алгоритмами построения и подсчетом числа элементов данного множества, обладающих некоторыми свойствами. Речь может идти, например, о числе решений задач целочисленного линейного программирования, числе ге-вершинных графов с определенными свойствами или о числе изомеров химических элементов. Существующие методы решения таких задач можно разделить на два типа: комбинаторные и вероятностные.

К комбинаторным методам относится классический метод производящих функций, получивший развитие в середине XX века. Использование перечислительных теорем Пойа, де Брёйна и Робинсона позволяет получать некоторые соотношения между числовыми характеристиками изучаемых объектов. Метод заключается в том, что на основании рекуррентных соотношений выводится дифференциальное уравнение, решением которого является производящая функция. Разложение производящей функции в ряд дает точные или асимптотические формулы для коэффициентов. Тем не менее, методика построения производящих функций сложна и не всегда приводит к обозримым результатам, поэтому существует класс задач, которые не могут быть решены с помощью классических методов.

Существенную роль играют комбинаторно - вероятностные методы решения перечислительных задач. В своих работах эти методы применяли Ю.Л. Васильев, В.В. Глаголев, В.Л. Гончаров, В.Ф. Колчин, А.А. Сапоженко, В.Н. Сачков, Н. Алон, Дж. Спенсер, П. Эрдёш. Идея вероятностного метода заключается в том, чтобы показать, что почти все объекты из рассматриваемого класса обладают некоторым свойством. Вероятностные формулировки комбинаторных задач дают возможность при отыскании асимптотических формул использовать аппарат предельных теорем.

Задачи, в которых речь идет о нахождении числа объектов, имеющих заданную границу или заданную мощность границы, естественно назвать перечислительными изопериметрическими задачами. Такими являются, например, задачи о числе монотонных булевых функций (так называемая проблема Дедекинда), независимых множеств в двудольных графах, булевых функций ранга ноль, двоичных кодов с расстоянием 2, пар подмножеств с расстоянием 2 в графах. Оказалось что, такие задачи сводятся к вычислению сумм специального вида, которые называются суммами граничных функционалов. Метод граничных функционалов разработан А.А. Сапоженко для решения перечислительных изопериметрических задач. Он сочетает в себе комбинаторный и вероятностный подходы и позволяет получать предельные распределения для случайных величин типа числа компонент связности. Сущность метода заключается в сведении исходной комбинаторной задачи к вычислению сумм граничных функционалов и дальнейшему аналитическому исследованию последних. Цель метода — получение оценки исходных сумм через "простейшие" суммы граничных

функционалов. Это позволяет уйти от перебора и громоздких конструкций, возникающих при чисто комбинаторном подходе.

К классу перечислительных изопериметрических задач относятся задачи о числе антицепей в частично упорядоченных множествах, а, значит, и задачи о числе конечнозначных монотонных функций. Наибольшую известность среди таких задач получила упоминавшаяся выше проблема Дедекинда о числе ф{п) монотонных булевых функций или, что то же, о числе антицепей в единичном те-мерном кубе Вп.

В 1897 г. Р. Дедекинд вычислил значение ф(4). Р. Черч в 1940 г. и М. Уорд в 1946 г. получили соответственно значения ^(5) и ф(б)- В 1954 г. Е. Гильберт показал, что ф(п) удовлетворяет неравенствам

2(i«/2j) < ф{п) < nd""2j) + 2.

В.К. Коробков в 1962 - 65 гг. показал, что ф(п) < 24'23(l»/2j), Ж. Ансель в 1968 г. улучшил верхнюю оценку до 3\ln/2-l', а Д. Клейтмен в 1969 г. доказал, что

Асимптотическое решение проблемы Дедекинда было получено А.Д. Коршуновым в 1980 г. Оно основано на описании "типичных" монотонных булевых функций и оценках числа подмножеств вершин слоев единичного те-мерного куба, имеющих заданную мощность границы.

В 1989 г. А. А. Сапоженко получил асимптотику числа антицепей в унимодальных частично упорядоченных множествах, из которой вытекает и асимптотика для ф(п).

Проблема вычисления мощности множеств функций п переменных из замкнутых классов исследовалась и для &-значных логик. В 1974 г. В.Б. Алексеев получил асимптотику логарифма числа &-значных функций, монотонных относительно произвольно заданного частичного порядка на S. В целом же асимптотик числа монотонных функций /г-значной логики при к > 2 практически нет.

Таким образом, актуальным является развитие методов решения перечислительных изопериметрических задач и метода граничных функционалов, в частности.

Краткое содержание диссертации

Модельной задачей, иллюстрирующей подход, связанный с методом граничных функционалов, является проблема нахождения числа независимых множеств в двудольных графах. Пусть дан двудольный граф Г = (X, Z; Е) с долями вершин X, Z и множеством ребер Е. Границей множества АС. X называется множество

д(А) = {о 6 Z : 3 и 6 A {u,v}E E}.

Подмножество С вершин графа Г называется независимым, если подграф, порожденный множеством С, не содержит ребер. Функция f(A) — 2~'д(А>> обладает следующими свойствами:

1) 0 < /(Л) < 1 для всех АСХ;

2) f(A) = 1 тогда и только тогда, когда А = 0; 3)f(AUB)>f(A)f(B);

4) f(A U В) > f(A)f(B) тогда и только тогда, когда существуют и € А и v 6 В такие, что f({u,v}) > f({u})f({v}).

Пусть /(Г) — число независимых множеств в графе Г. Тогда

/(Г) = 2"*" X) 2"|Э(А)|. (1)

АСХ

В самом деле, произвольное независимое множество С в Г может быть представлено в виде С = ЛиВ, где А = СШ, В = С Г\ Z. Если выбрано множество АСХ, то все подмножества В С Z \ д(А) и только они образуют вместе с А независимое множество в Г. Число таких подмножеств равно 2'^9^'. Отсюда следует (1).

Из равенства (1) следует, что вопрос о числе независимых множеств сводится к вычислению сумм вида Y^acx /(-А)-

Функционал / : 2х —> R, удовлетворяющий условиям 1-4, называется граничным. Пара / = [X, /) называется функциональной парой. Через

АСХ

обозначим полную сумму значений граничного функционала /, в дальнейшем для краткости будем говорить о суммах граничных функционалов. Граф Gj = (X; Е) с множеством ребер

называется графом функциональной пары I = (X,f). Подмножество АСХ называется связным (относительно функционала f), если подграф графа G/, порожденный множеством А, связен. В случае описанной выше задачи о числе независимых множеств в двудольном графе Г множество АСХ связно относительно функционала /, если граф, порожденный множеством A U д(А), связен. Через Л = Л(1) обозначим семейство всех связных подмножеств множества X.

Если / = (X,f) — функциональная пара, и, j — натуральные, В С А(1), то положим

«"(%]) = ?(/И)Г, (2)
где Вщ состоит из всех подмножеств, принадлежащих семейству В и имеющих мощность j.

Для подмножеств А, В С X скажем, что В является компонентой множества А, если В связно, но никакое D такое, что В С D С А пе является связным. Для В С Л(1) обозначим через С(В) семейство подмножеств множества X, все компоненты которых принадлежат семейству В. Положим

S(B)=

Справедливо утверждение о том, что

S{B) < Т{1) = S(A(I)) < S(B)S{A{I) \ В).

Идея получения асимптотики сумм Т(1) заключается в том, чтобы найти семейство В С Л(/), для которого выполняются следующие условия:

1) 5(Л(/)\В)~1;

2) существует простая асимптотическая формула, выражающая S{B) через суммы вида (2), вычисление которых обычно не вызывает затруднений.

Назовем характеристикой функциональной пары / = (X, /) наименьшее целое А такое, что выполнено условие

А.А. Сапоженко ([20], [23]) получил асимптотическую формулу для сумм граничных функционалов в случае, когда функциональные пары имеют характеристику Д <2.

Функциональная пара / = (X, /) пара называется нерегулярной, если существуют подмножества Xi С X и Хч С X такие, что для любых вершин и ? Xi и v € .АГ2 выполнено соотношение

ЯМ) = *(/({»})).

Целью данной работы является расширение области применения метода граничных функционалов на случай функциональных пар с характеристикой А > 3, а также на случай нерегулярных функциональных пар. Эта задача решается в главе 1. В главе 2 результаты первой главы применяются для получения асимптотики числа антицепей в частично упорядоченном множестве S%, являющемся декартовой степенью ^-звезды при к < 11. Функциональные пары, порожденные парами слоев этого множества, имеют характеристику 3. В главе 3 рассматривается множество Е?\ являющееся декартовой степенью линейного частичного порядка мощности 3. Функциональные пары, порожденные парами слоев этого множества, являются нерегулярными. С использованием результатов первой главы получена нижняя оценка числа антицепей в Е?.

Во введении обоснована актуальность темы исследования, сформулирована цель диссертации, описана структура диссертации и перечислены основные результаты.

В главе 1 получена асимптотическая формула для вычисления сумм S{B) в случае, когда функциональная пара имеет характеристику 3 при условии, что для любых {и}, {г;} 6 В выполнено f({u}) = f{{v}). Кроме того, определено расширение класса функциональных пар с характеристикой 2.

В главе используются результаты из работ [19], [20] и [23]. Результатом главы являются теоремы 1.4.3, 1.5.2 (см. ниже), дающие асимптотику сумм S(B) для функциональных пар с характеристиками 3 и 2 соответственно.

В параграфе 1.1 введены основные определения.

В параграфе 1.2 описан класс подмножеств множества X "типичных" для семейства В, и получены оценки сумм граничных функционалов S(B) через суммы граничных функционалов по типичным подмножествам. Типичным является множество, состоящее не более, чем из в компонент, где в = а}{В)(1 + о{1)).

Пусть даны семейство В и множество В С X, тогда обозначим через Вв множество подсемейств {Ai,..., Aa} семейства В, удовлетворяющих следующим условиям:

1) множество Н = (J Aj связно
2) множество В U Н связно.

В параграфе 1.3 получены оценки сумм вида

S(B) = ? /(А)тг(Л) (3)

АСХ

через суммы вида (2).

Здесь

п(А)= П (l

Суммы вида (3) являются обобщением сумм S(B). Для оценки исходных сумм достаточно получить асимптотическую формулу, позволяющую вычислять функционал тт. Дальнейшая задача состоит в оценке функционала тг для типичных множеств.

В параграфе 1.4 рассмотрен класс так называемых (Д, к, q, р)-ординарных функциональных пар и доказано, что такие функциональные пары имеют характеристику А.

Для функциональной пары / = (X, /), семейства А(1), вершины v ? X ъ натурального т положим

Лы^{1) = {веА:\в\<т7ви W е Л}.

Функциональная пара / = (X, /) называется (А, к, q, с)-ординарной, если

1) для всякого v ? X выполнено f({v}) < 2~ге,

2) \Х\ < 2(д+1)к-21°52«)

3) для любых А С X и v ? А

4) для всякого v & X it любого натурального числа т

Пусть / = (X, /) — функциональная пара, порожденная двудольным графом Г = (X, Z; Е), где X = В%, Z = В%+1 — соответственно fc-ый и (/г + 1)-ый слои тг-мерного единичного куба, 0 < к < (п — 1)/2,

Е - {{u,v} :ueX,v

и f(A) — 2~1а(л" для всех АС. X. Пара / = (X, /) является (2, п — к, 1,2)-ординарной. В самом деле,

1) минимальная степень вершины v ? X в графе Г равна п — к;

2) |??п| — М < 23("-fc)-2bg^(n-fc).

3) границы любых двух вершин u,v ? X имеют не более одной общей точки;

4) для любого т и любой вершины v ? X мощность ее окрестности порядка 2т не превосходит ((к + 1)(ге - к))т < (п - к)2т.

Если функциональная пара имеет характеристику 2, то значение функционала тг для типичных множеств асимптотически равно 1, и, следовательно, значения сумм S(B) и S(B) асимптотически равны.

В пункте 1.4.3 получена асимптотическая формула, выражающая функционал тг через суммы вида (2) для функциональных пар с характеристикой 3 в случае регулярных семейств подмножеств. Семейство В называется регулярным, если

ДМ) = ДМ)

для всех {и}, {v} ? В. В результате получена асимптотика сумм S(B) для функциональных пар с характеристикой 3 и регулярных семейств В:

Теорема 1.4.3. Пусть I — (X,f) является (3, к,, q, с)-ординарной функциональной парой, семейство В С А~(1) является регулярным. Тогда

MB) = а1 (В) ~ \а\В) + \« 4з]4]

В параграфе 1.5 введено обобщение понятия ординарности функциональных пар, и найдена их характеристика. Получена асимптотика сумм граничных функционалов для нерегулярных функциональных пар с характеристикой 2.

Теорема 1.5.2. Пусть I = (X,f) является (2,{к1,к,2},д,с,р)-ординарной функциональной парой, В С Aq(I). Тогда при достаточно больших к^

S(B) = где

В главе 2 рассматривается задача о числе антицепей в частично упорядоченном множестве S%, диаграмма которого является декартовой степенью А;-звезды, т.е. дерева с к + 1 вершинами, одна из которых имеет степень к. В работе [20] получена формула, позволяющая вычислять асимптотику числа антицепей в так называемых унимодальных ранжированных множествах (точное определение см. в параграфе 2.1) и задача решена для 1 < к < 4.

В параграфе 2.1 введены основные определения. Двудольный граф G — (X, Z; Е) является «^-расширителем, если для всех А С X выполнено неравенство \А\ < (1 — ^)|9(Л)|. Для ранжированного m-слойного множества Р = (Рх,. .. , Рт) с порядком :< и числа j, 1 < j' < т обозначим через Gj — (Pj, Pj+i; Ej) двудольный граф с долями вершин Pj и Pj+i и множеством ребер Ej = {{u,v} : и G Pj,v E Pj+\,u X v}. Через Gj = (Pj,Pj-i; Ej) обозначим двудольный граф с долями вершин Pj и Pj-i и множеством ребер Ej = {{и,v} : и 6 Pj,v ? Pj-i,v < и}. Множество Р является (Д, к, q,р,г)-квазиунимодалъиым, если графы Gj являются ?(/г)-расширителями при О ^ 3: < г ~ 1) графы Gj являются ^(лс)-расширителями при г + 1 < j < n, а функциональные пары, порожденные этими графами, являются (Д, к, q, 4р)-ординарными. Множество Р является (Д, к, q,p, г)-унимодальным, если оно является (Д,«,д,р,г)-квазиунимодальным, и, кроме того, выполнены следующие условия:

max an (v) < хшиап-Ы) при 0 < j < r — 1, а также (4)

vePj+i 'v ; " uePj jK ~ ~ v '

max

(v) < min стяг (и) при r -f 1 < j < n, (5)

где

Из работ [20], [23] следует, задача о числе антицепей в (Д, к, q,p, г)-унимодальном множестве сводится к задаче о числе антицепей в множестве (-Pr-i, Pr, Pr+i)-

Пусть к — натуральное число, рассмотрим множество Sk = {~1> 0,1,.. ., к — 1} и зададим на нем отношение частичного порядка ^ следующим образом: — 1 ^ г при г = 0,1,..., к — 1. В параграфе 2.2 доказана унимодальность множества 5?. Положим

Теорема 2.2.3. Пусть п = [к + 1)т + i для некоторых целых т и г, 0 < г < к. Положим А = -?-Hog2(& + 1) — 1. Тогда при достаточно больших т и 0 < г < к — 1 множество S% является (А,те — m + 1,1,2,т,т)-унимодальным. При i = к множество 5? является (А, та — т, 1, 2, т,т + 1)-унимодальным.

Обозначим через ч/Ч^) число антицепей в 5?.

Теорема 2.2.4. Пусть п — (к + 1)пг + г с?л.# некоторых целых т и i, 0 < i < к. Положим А = ^rMog2(fc + 1) — 1. Тогда при достаточно большихт иО < i < к — 1

^^.! и 5ДГ„ и

/Zpw достаточно больших т и i = к

(SLn-i U Slm U 5fc"TO+i

Множество (5'^_1,5'^,5^+1) порождает функциональную пару In = (Xn,fn), где

/„(Л) = 2~'9(А>К В параграфе 2.3 доказано, что при 5 < к < 11 функциональные пары /п = (Хп, fn) являются регулярными и (3,те — гп, 2,3)-ординарными. С использованием результатов главы 1 доказана

Теорема 2.3.3. Пусть 5 < к < 11, п достаточно велико и п — (k -\- \)m -\- i

для некоторых щ, г, 0 < г < к, 1п = (Х„, /„) — функциональная пара, порождаемая множеством (5'^_1, 5^, ^+1). Тогда

\<*^2 +1^'3 - 42)д+^'2)д-

В приложении суммы ос? v вычислены через параметры множества 5J?.

В главе 3 рассматривается частично упорядоченное множество Е%, являющееся декартовой степенью линейного порядка мощности 3. Как и в предыдущей главе, здесь ставится задача о числе антицепей в данном множестве.

Пусть к — натуральное число, рассмотрим множество Ек — {0,1,..., к — 1} и зададим на нем отношение частичного порядка < следующим образом: г < i + 1 при г — 0,1,.. . ,к — 2. Положим F(n,i,k) = {& = («i ... ,ап) 6 Е% : 2™=1 at = г}, N(n,i,k) = \F{n,i,k)\.

Обозначим через ф{Е^) число антицепей в множестве Е%. Из работы В.Б. Алексеева следует [1], что

оп+1/2

(1 +

В параграфе 3.1 получена асимптотика мощностей центральных слоев Е%. Теорема 3.1.1. При достаточно достаточно больших п справедливы равенст-
В параграфе 3.2 рассмотрены функциональные пары, порождаемые тремя центральными слоями Е%. Трехслойное множество (F(n,n — 1, 3), F(n,n, 3), F(n,n + 1, 3)) порождает функциональную пару /n = (Xn,fn), где Xn = F(n, те — l,3)UF(ra, ге + 1,3), для ЛС1„

д{А) = {В С F(n, n,3) :Vv <Е ВЗиЕ A(u

fn{A) = 2~'э(л)!. Эти функциональные пары являются нерегулярными, показано, что они имеют характеристику 2. С использованием результатов главы 1 получена асимптотика сумм значений граничных функционалов по множествам малой мощности.

Теорема 3.2.1. Пусть {1п = (Хп,/П)} — последовательность функциональных пар, порожденных соответственно множествами (F(n,n — 1,3), F(ra,re,3), F(n,n-\-1,3)). Тогда при п —^ оо

L()/J \ / _ -

= Е (") („ _ 2/_ 1]2"(""Л I2 + 2-("-Л(Зп2 - 7»; + H|i2 + 10fi + n - 2)].

где

L(n-1)/2J

Из теорем 2.2.3, 3.2.1 и [21], [23] следует Теорема 3.2.2. При достаточно больших п

где /jq определено в предыдущей теореме.

Таким образом, улучшена известная нижняя оценка ф(Е%). Замечание. Можно убедиться в том, что

где с к» 1.95.

В работе Н.Н. Катериночкиной оценивалась величина 6(i,n,k) — N(n,i + l,fe) — 7V(n,i,/s). В параграфе 3.3 доказана логарифмическая выпуклость мощностей слоев множества Е%.

Теорема 3.3.1. При любых k>2,n>2u2

N(n,i-2,k) N(n,i-l,k) N(ilk)

N(n,i,k) 10

В параграфе 3.4 доказана (3, [п/2\, 1,2, п, и)-квазиунимодальность множества Eg, а также унимодальность частично упорядоченных множеств, состоящих из 2и/3 первых или из 2га/3 последних слоев Eg. Это позволяет свести задачу о числе антицепей в Eg к аналогичной задаче в множестве, состоящем из 2та/3 центральных слоев Eg.

Теорема 3.4.3. Положим Egti = F{n,i,Z), t = [2(n - l)/3j, к = n - [t/2\. При

достаточно больших п множества (Egfi, Egtl,..., Egt) и (Eg2n_t, ¦ • • ¦> E$,2n-ii ^з,2п) являются (2, к, 1,2, i, t)-унимодальными.

Функциональная пара / = {X,f) называется /^.-сходящейся, если выполнено

Если для квазиунимодального множества выполнены условия (4), (5), то функциональные пары, порожденные парами его соседних слоев, автоматически являются Д-сходящимися.

Для получения асимптотики числа антицепей в Eg достаточно показать, что функциональные пары, порожденные парами соседних слоев множества Eg, являются /^.-сходящимися для некоторого А.

В таком случае асимптотика числа антицепей совпадает с нижней оценкой.

Основные результаты диссертации

1. Для функциональных пар с характеристикой 3 получена асимптотическая формула для вычисления сумм граничных функционалов по регулярным семействам подмножеств.

2. Получена асимптотическая формула для вычисления сумм граничных функционалов в случае нерегулярных функциональных пар с характеристикой 2.

3. Получена асимптотика числа антицепей в множестве Sj! при к < 11.

4. Получена оценка отношения мощностей соседних слоев множества Eg.

5. Доказана логарифмическая выпуклость мощностей слоев множества Е%.

6. Получена нижняя оценка числа антицепей в множестве Eg.
Глава 1

Оценки сумм граничных функционалов

1.1 Основные понятия

В параграфе приводятся основные понятия и определеня, введенные в [19], [20], [23].

Через 2х обозначается семейство всех подмножеств множества X. Произвольное отображение / : Iх —>• (0; 1] называется граничным функционалом на семействе подмножеств множества X, если оно удовлетворяет следующим условиям:

1) f{A) = 1 тогда и только тогда, когда А = 0;

2)f(AuB)>f(A)f(B);

3) f(A U В) > f(A)f(B) тогда и только тогда, когда существуют и (Е А и v ? В такие, что /({«,«}) > /({«})/(М)-

Пара / = (X,f), где X — конечное множество, а / — граничный функционал, называется функциональной парой. Через

T{I) = T(X,f)= ?/(А)

АСХ

обозначается полная сумма значений функционала /.

Пусть / = (X, /) — функциональная пара. Вершины и и v из X такие, что f({u,v}) > f{{u})f({v}), называются смежными (обозначение u#v). Вершины миг;, для которых выполнено равенство /({w, v}) = /({^})/({i>}), называются несмежными (обозначение и || v). Множества А С. X w. В G X называются смежными (обозначение А#В), если /(AU В) > f(A)f(B). Множества А и В называются несмежными (обозначение А \\ В), если /(A U В) = f(A)f(B).

Граф Gi = {Х]Е) с множеством ребер Е = {{^,i>} : ифу} называется гра-^'ож функциональной пары I — (X,f). Через Но{(А) — [А;Е'), где А С X, ?l' = {{ti,u} G .& : {и, и} С А} обозначается подграф графа Gi, порожденный множеством А. Непустое множество F С X называется связным, если подграф Hgx{F) графа G/, порожденный множеством F, связен.

Семейство всех связных подмножеств множества X обозначается через Л(1). Подмножество В С. А называется компонентой связности множества А (обозначение В Ь А), если граф Hg,{B) является компонентой связности графа Hq^A). Через 7/(А) обозначается число компонент связности семейства А. Для В С Л(1) полагаем

С (В) = {А С X : В h A =^ BGS}, 12

Таким образом, С(В) состоит из всех множеств, у которых все компоненты принадлежат семейству В.

Введем некоторые суммы граничных функционалов. Пусть v — натуральное число и В С Л(1) — прозвольное семейство, тогда1 положим

лее

/(л),

Аеск(в) Пусть т > 0 — целое, тогда

|А| = го}, = U

Последовательность {/n = (Xn, fn)}^>==1 функциональных пар называется А-схо-дящейся, если

Лемма 1.1.1.[23] Дл^ любой функциональной пары I = (X, /) и любого В С справедливо неравенство

S{B) < Т{1) = S(A(I)) < S{B) exp (a1^/) \ В)} .

При й„ = Д^(/„) из леммы 1.1.1 следует, что для Д-сходящихся последовательностей функциональных пар при п —>¦ оо справедливо

Г(/п) ~ 5(ВП).

Таким образом, задача о вычислении сумм Т(1) сводится к выражению сумм S(B) через суммы типа аУ{В) по связным множествам малой мощности.

1.2 Асимптотики сумм граничных функционалов

В статье А.А. Сапоженко [21] было введено понятие ап-ограниченной последовательности. Сумма такой последовательности приближается суммой ее "типичных" членов. При этом случайные величины, связанные с типичными членами последовательности имеют в пределе при п —>¦ оо распределение Пуассона или нормальное распределение. Пусть даны последовательность функциональных пар {/п = (Хп, fn)}5v=i и последовательность семейств {Вп С A(In)}™=i- В данном параграфе доказано, что последовательность сумм {S(Bn)}™=1, являющихся обобщением сумм 5(йп), является а1 (Бп)-ограниченной.

Последовательность {<7Vi,j}?°j=o называется ап~ограниченной, если при любом j выполняется неравенство

В дальнейшем для краткости (/(А))" = f{A).
Для «„-ограниченных последовательностей справедливы следующие утверждения:

Теорема 1.2.1.[21] Пусть последовательность {&n,j}™j=o является ап-ограни-чеиной и Km шп = ею, Положим вп = ап + и>пЛ/а^. ап — У2 ап л Тогда при п —у оо

lim е„ = 0. Z7pti этом еп — O(e"Wn^4), если шп < y/a^, и еп — О(шп1е~ш"/2), если
Следствие 1.2.1. Пусть выполнены условия теоремы 1.2.1 и шп — о Тогда при п —>• оо
Теорема 1.2.2.[21] Пусть последовательность {o'n,j}^'j=o является ап-огра-ниченной и lim шп = сх>. Положим 0п = ап + и>пл/о^, сгп = X) °"n,j, an,j =

Gn,i, Pn - min{an),-}; rn = /?n - шпл/Щ, an -n —> oo

5-n = «rn(l - ?„),

lim en = 0. При этом еп — О(е~ш"/4), если шп < у/а^,, и еп = O(u>~le~Wnl2), если

Пусть функционал 7г : 2х —> (0; 1] удовлетворяет следующему условию:

тг(?)тг(1>)<7г(5и1>) <тг(5) (1.2.1)

при всех В, D С X.

Для функциональной пары / = (X, /) и семейства В С Л(1) положим

А?Ск(В)

В параграфе 1.3 введен функционал 7Г, удовлетворяющий условию (1.2.1), а также получены асимптотические формулы, выражающие суммы S(B) через суммы вида аУ{В). В дальнейшем для нахождения асимптотики сумм S(B) необходимо получить оценку функционала 7г. Теорема 1.2.3 дает возможность при оценке к(В) ограничиться рассмотрением только тех множеств В, у которых количество компонент мало отличается от а1 (В). При выполнении некоторых условий это позволяет получить асимптотические формулы для сумм граничным функционалов, имеющих характеристику 3 (см. параграф 1.4).

Если В С 2х, В 6 X, то положим

В?={АеВ :А\\ В}.

Лемма 1.2.1. Пусть даны функциональная пара I = (X,f) и функционал тт. Тогда для любого семейства В С Л(1) и целого числа к > 0 выполнено

(fc + 1) ? ДА)тф4)= ? f(B) ? f(D)*{BUD). (1.2.2)

веск(в)
Доказательство. Правая часть равенства (1.2.2) равна сумме произведений f(B)f(D)Tr(B U D) по всем упорядоченным парам (B,D) таким, что В € Ск(В), D 6 B-q. Для каждой такой пары множество А — В U D принадлежит семейству Ck+i(B). При этом f(A)n(A) = f(B U D)tc(B U D) = f{B)f(D)n(B U D). Таким образом, каждая пара (B,D) определяет множество А ? С^+1(В), причем каждое множество А порождается к + 1 раз. Отсюда следует (1.2.2).

Пусть / = (X,f) — функциональная пара, А С X, Я С 2х. Через т]и{А) обозначим число компонент множества А, принадлежащих семейству N. Если к натуральное, В С Л(/), то положим

= U c,-(

Пусть в: j — натуральные, М, А4С2Х,МГ\М = Ф тогда положим
Лемма 1.2.2. Пусть I = (X,f) — функциональная пара, функционал тг удовлетворяет условию (1.2.1), #i С В С Л(/), «1 = ск1(Б1) достаточно велико, N С 2^, jV П ^! = 0; ^ — натуральное число. Положим


Тогда последовательность {ck{Bi)}™=Q является a.i~ограниченной. Доказательство. Из (1.2.1) и (1.2.2) получаем

(fc + i) Е f(B)*(B)= Е /(^) Е

Е fWKaW Е

Отсюда следует (1.2.3).

Теорема 1.2.3. Пусть I = (X,f) — функциональная пара, функционал тг удовлетворяет условию (1.2.1), В\ С В С Л(/), / — натуральное число. Пусть также

В ~ [j Bt, Bid Bj = 0 d/iir ecez г 7^ j,

и at = al{Bt) достаточно велики. Положим 9t = at + at ,

l

Тогда

E f{B)n{B). (1.2.4)
Доказательство. Из леммы 1.2.2 следует, что для каждого t, 0 < t < I, последовательность

является «^-ограниченной. Теперь утверждение вытекает из следствия 1.2.1.

Следствие 1.2.2. Пусть I = (X,f) — функциональная пара, В\ С В С Л(1), I — натуральное число. Пусть также

В = U Bt, BiH Bj = 0 для всех i ф j, \

и at — al(Bt) достаточно велики. Положим 6t = at + at ,

C(B)= П С%{

Тогда

вед{в) Доказательство. Заметим, что по определению

S{B) = Функционал п(В) = 1, очевидно, удовлетворяет условию (1.2.1).

1.3 Отношения между суммами граничных функционалов

В этом параграфе введен функционал специального вида 7Г и получены асимптотические формулы для сумм S(B) (теоремы 1.3.3, 1.3.4) в тех случаях, когда выполнены условия типа

av{B{r)) = о(1).

Для дальнейшей оценки сумм S{B) необходимо получить асимптотику функционала 7Г. Отметим, что значение функционала 7Г асимптотически равно 1, если выполнены условия теоремы 1.3.3, тем самым, задача об оценке сумм S(B) окончательно решена для функционалов с характеристикой 2. В параграфе 1.4 получена оценка 7г для функционалов с характеристикой 3.

Нам понадобятся обобщения введенных ранее сумм на случай семейств подмножеств.

Пусть / = {X,f) — функциональная пара, введем понятие семейства ранга г над X. Произвольное подмножество А С X называется семейством ранга 1. Если Ai,..., As — различные семейства ранга г, то F = {Ах,..., As} называется семейством ранга г + 1. Семейства А\,..., Ая называются элементами семейства F. Множество всех семейств ранга г над X обозначается через Х^г\
Для произвольного семейства F ранга г по индукции определены величины \F\ — мощность семейства F, \\F\\ — мулътимощность семейства F, f(F) — значение функционала на семействе F и множество (F) — основа семейства F. Если F — семейство ранга 1, т.е. F С X, то ||F|| = \F\, где |F| — число элементов множества F, f(F) определяется функциональной парой / = (X,f), a (F) — F. Пусть для некоторого г > 1 эти величины и множество определены, и пусть F — {Ai,..., As} — семейство ранга г + 1. Тогда

ШЪ /(*") = П Я*). (F)= U <*>¦

Введем понятие связного семейства ранга г. Пусть I = (X, /) — функциональная пара. Для семейств ранга 1 связность определена ранее. Семейство F = {Ai,..., As} ранга г > 1 называется связным, если каждое из Ai, i = 1,..., s, является связным семейством ранга г — 1 и (F) ? А(1). Множество всех связных семейств ранга г обозначается через А^(1). По определению А^(1) = А(1).

Для произвольного подсемейства В С А(1) определено семейство В^ связных подмножеств ранга г, порожденное множеством В. Положим В^ = В. Если В^7""1' определено, то

ВМ = 2в1г-1)ПАМ(1).

Подсемейство В семейства F ранга г называется компонентой связности семейства F (обозначение В h F), если В G А^(1) и (В) — компонента связности множества (F). Через n(F), как и раньше, обозначается число компонент связности семейства F.

Пусть / = (X,f), В С А^(1). По аналогии со случаем г = 1 полагаем

а"(В) = ? f{A),

С (В) = {FC Х{т) : А\- F ^ АеВ},

С;{В) = {F € С(В) : n(F) = j}, S{B)= E f(A), Sk(B)= ? /(A).

Если Б С Х(Г\ В е Х("\ т, s > 1, то положим

Вв = {А е В : <Д>#<5)} , % = {A G В : (А) || (В)}.

Далее доказываются некоторые соотношения между суммами граничных функционалов разных типов.

Лемма 1.3.1.[23] Для любой функциональной пары I = (X,f), любого натурального г и любого В С А^г'(1) справедливо неравенство

S{B) < expja1^)}. (1.3.1)

Пусть Т> — В^"1', через ТУ обозначим семейство В^г\

Теорема 4.1 из статьи [23] легко переносится на случай семейства ранга г > 1:
Список литературы
Цена, в рублях:

(при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)		 1425
Скачать бесплатно 23593.doc 





Найти готовую работу


ЗАКАЗАТЬ

Обратная связь:


Связаться

Доставка любой диссертации из России и Украины

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ


Ссылки:

Выполнение и продажа диссертаций, бесплатный каталог статей и авторефератов

Счетчики:

Besucherzahler
счетчик посещений

© 2006-2022. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.