Метод граничных функционалов в перечислительных изопериметрических задачах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИМ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДШ ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННОЙ УНИВЕРСИТЕТ ИМ.Ы.В.ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

на правах рукописи

САПОЖЕНКО Александр Антонович

УДК 519.175'.3

МЕТОД ГРАНИЧНЫХ ФУНКЦИОНАЛОВ В ПЕРЕЧИСЛИТЕЛЬНЫХ ИЗОПЕРИЫЕТРИЧЕСКИХ ЗАДАЧАХ

01.01.09 - математическая кибернетика

- АВТОРВНГРАТ диссертации на соискание ученой оепени доктора физико-математических наук

Москва - 1992

Работа выполнена на кафедре математической кибернетики Московского государственного университета им.М.Б.Ломоносова

Официальные оппоненты: действительный член РАН,

доктор физико-математические наук профессор Ю. И.Куравлев, доктор физико-математических наук профессор В.Ф.Колчин, доктор физико-математических наук профессор А.А.Марков.

Ведущая организация - Институт математики Сибирского отделения

РАН

Защита диссертации состоится в II час. 00 мин на заседании специализированного Совета факультета вычислительной математики и математической кибернетики МГУ по адресу: Москва, Ленинские горы, МГУ, факультет ВМиК,

С диссертацией можно познакомиться в библиотеке факультета.

Автореферат разослан / 1992 г.

Ученый секретакъ специализированного Совета Д.053.05.38 при МГУ

профессор Н.П.Трифонов

ОВДАЯ ХАРАКТЕРИСТИКА РАбОТЫ

Актуальность теин исследований. В дискретной математике, где множества изучаемых объектов, как правило, конечны и, вместе с тем, достаточно велики, существенную роль играет вопрос о моиности этих множеств. Зто ваяно, например, с алгоритмической точки зрения для оценки сложности перебора при реиении дискретных задач (I, раздел 31,, для получения низших мощностных оценок и решения вопроса о существовании того или иного типа объектов 12) для оценки эффективности вероятностных алгоритмов (II, (211. В ряде случаев асимптотика или даже оценки мощности множеств комбинаторных объектов представляют самостоятельный интерес. Сада можно отнести, например, так называемую проблему Дедекинда о числе монотонных булевых функций [31,£41,151. Бе асютгготическое решение, найденное А.Д.Кориуновым сравнительно недавно (см.151,[61), получено им с помоз&ю довольно громоздка* комбинаторных конструкций, связанных с перебором большого количества случаев. С другой стороны, сувдствует целый ряд перечислительных задач из различных областей дискретной' математики, имещях общую с проблемой Дедекинда комбинаторную природу . К ним относятся задачи о числе независимых мяогеств в двудольных графах, задача о числа булевых ({ункций с интервала« только размерности ноль, о числе двоичных кодов с расстояние» 2 (см.(301), задача о протекания (перколяции) (71, многие задачи нз теории многозначных функций (81,[91. Во. всех этих задачах речь идет о нахождении числа объектов, нмеювдх заданную границу зли заданную мощность границы. Поэтому естественно назвать • их перечислительными изоперимэтрическгага задачами (сокращенно, ИЗ).

Общее в этих задачах также то, что все они, как оказалось, сводятся к вычислению су»« специального вида, которые называются здесь сушами граничных функционалов (С1Ч>). Весьма актуальной поэтому является разработка единого метода решения задач такого типа. Основным побудительным мотивом для разработки метода является стремление уйти от перебора и громоздких конструкций, неизбежных при традиционном чисто комбинаторном подходе к решению перечислительных изопериметрических задач. Здесь эта цель достигается с помощью сведения исходной комбинаторной задачи к вычислению СГФ и дальнейшем аналитическом исследовании последних.

Постановка задачи и примеры. Граничным называется функционал

Ф, определенный на семействе всех подмножеств некоторого множества X и обладающий следующими свойствами:

1. О <. ф(А) « 1 для всех АсХ ;

2. ф(А) = 1 »4=0;

3. ф(АиВ) » ф(А)ф(В);

4. ф(АиВ) > ф(А)ф(В) « (э иеА)(э тг(в) ф(Си,у}) > ф((и))ф((т)}.

Пара (Х,ф), где X - множество (как правило, конечное), а ф -граничный функционал, называется функциональной парой (сокращенно, ОТ). Задача ВСГО состоит в вычислении сумм вида

Т(1) = I ф(А). АгХ

Под вычислением здесь понимается представление ее асимптотики в виде формул, через "легко вычислимые" суммы аналогичного вида, берущиеся по связным подмножествам множества X. Использование термина "граничный функционал" объясняется тем, что функции, связанные с различными понятиями границы множеств, обычно ч>бладают

свойствами 1-4.

Пример I (Задача о числе независимых множеств в двудольном графе). Пусть 0=(Х,г;Е) связный двудольный граф с долями верпин Х.г и множеством ребер Е и АсХ. Границей (или тенью) множества А называется множество д(А) = {^г: (зи) (ц,у)€е|. Нетрудно

проверить, что функционал <р, такой, что <р(А) = обладает

свойствами 1-4. Пусть ф(С> - число незавивтаяп "множеств в графе С=(Х,г;Е). Тогда оказывается, что (см. легану 3.3.1)

Ф(с> =г121 -г!2» т«с) .

где 1с = (Х,<р) - ФП, порожденная графом (3, в которой для всех А£Х.

Прниар 2 (Задача о пврколяцин). Рассмотрим плоскую целочисленную реаетку Г^, состоящую из всех пар вяда (а,Ь) , где а, Ъ -целые числа. Пары (точки) (а,Ь) и (а' ,Ь') называются соседаиии, если |а - а' | + |Ъ - Ъ' | = 1. Границей мновества А с называется множество Н(А), включающее все точки из Г^ЧА, ниещив хотя бы одну соседнюю точку из множества А. Связное подмнояество точек репетая

называется кластером. Функционал <р£А) = р'А' (1-р)н*А' обладает

свойствами I - 4. В теории просачивания (перколяции) (см. Х.Кестен [71, стр.84) важную роль для нахождения вероятности перколяции по вершинам играет суки £ фр(А), где суишрование ведется по всем кластерам А, содержащим начало координат.

Прэюр 3 (Проблема Двдехинда). Пусть Вп - единичный п-ыэрный куб с обычным отнесением частичного порядка. Антицепью называется произвольное подмножество, состоящее из элементов куба, попарно несравнимых между собой. Задача заплетается в нахождении числа

<j>(n) антицепей в В11. Пусть в£ - к-й слой куба Вп, состоящий из

наборов с К единицами. Проекцией произвольного множества AsBn на

слой В£ (или границей множества А) назовем множество тех

элементов, из в£, которые сравнима хотя бн с одним элементом из А.

Если А&В£_, (АеВ£+) ), то пусть Q(A) - число антицепей De U В"

(D с U В?), удовлетворяющих условию Pv ,(D)=A (Рь ,(D)=A). Пусть 1>кн

Xk=B^_)UB^+), a *k - множество всех антицепей AsX^ Для всех СсХ^ полагаем Q(A) = Q(A П В£_,) U Q(A П В^,)- Пусть ф(С) = Q(C)2"iPk(C)' для всех С с Х^. Тогда

к

ф(п> = 2!Вк! Y. Ф<с> = 2°П Z <Р(С>.

Cef, CcW.

к к

Если при этом Q(C) < г!с1 для всех непустых множеств С с XJt, то ц>

удовлетворяет условиям 1-4. При четных пи к = п/2 эти условия оказываются выполненными, а пара = (Х^.ф) является ФП.

Приведенные примеры, перечень которых можно продолжить, показывают , что вычислив сумму вида Т(1), мы фактически получаем решение соответствующей перечислительной ИЗ.

Цель работы - разработка метода приближенного вычисления суш

граничный функционалов (сокращенно, метода РФ), и решения с его помощью некоторых перечислительных ИЗ. Под приближенным вычислением мы понимаем получение асимптотик сумм граничных функционалов (CPS) и решений перечислительных задач. Мы стремимся к тому, чтобы, сведя некоторую перечислительную задачу к

вычислению СГО для некоторой Ж и определив ее тип , а также ряд параметров ФП, получить готовую асимптотическую формулу для числа искомых объектов.

Рассмотрим метод ГО в применении к задаче о числе <|>(0) независимых множеств в двудольном графе С (см. пример I). Поскольку вычисление величины 2!2! для заданного графа С=(Х,г;Е) не вызывает трудностей, задача сводится к вычислению СГФ

Т<1) = I ф(А> (0.1)

А=Х

-¡а<А):

для функциональной пэры 1=Т(,=(Х,ф), где ф(А) = 2 . Свойства

1-4 граничных функционалов позволяют ввести граф Н(1)=(Х;Е) с

множеством ребер Е={{и,у): ф{{и,7)) > ф({и))-ф<{7)и тем самым

определить понятие связного множества. Именно: АсХ называется связным, если подграф графа Н(1), порожденный множеством А, связен. Пусть II =• 41(1) - семейство всех связных подмножеств множества X. Далее для произвольного 8 с определим семейство <Т(8) как множество всех А&Х, каждая компонента связности которых принадлежит семейству Ж, а также функционал

<Л«> = ^ (Ф(А))1' (0.2)

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

I ф(А) < I ф(А) < £ ф(А) I ф(А) (0.3) Ае«(ав> А=Х А(5(®> В€б-(11\$)

Эти неравенства содержат идею получения асимптотики суммы Т(С).

Именно: положив Б(0)= £ ф(А), будем искать такое ¡В = чтобы А«СГ(»)

выполнялись следующие два условия:

1) S(«\S)~1, (0.4)

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

В связи с тем, что S(R) ^ expía'(О)), условие (0.4) сводится к условию

a1 «IV») = о(1). (0.5)

Условия (0.4) и (0.5) предполагают неявно наличие параметра п,

стремящегося к а>, относительно которого рассматриваются асимптотики.

Очевидно следующее соотношение:

a'(P)= I <р( А) = 2~вФ(»,8),

Aí£> AíP

где Ф(Х),е) - число множеств Ае» с границей мощности g, а g,=g, Ш) - наименьшая мощность границы у множества из I). Поэтому для доказательства (0.5) достаточно доказать существование такого е, чтобы выполнялись условия:

Ф(»,в) < 2_в(1~е) (0.6)

и

£ 2_8s -О при 11-» (0.7)

Таким образом, проверка условия (0.4) приводит к оценке числа Ф(D,g) множеств с мощностью границы, равной g. Мы вновь сталкиваемся с изопериметрической задачей, но в "облегченном"

варианте: нужна лишь оценка сверху. Неравенство вида (0.6) удается доказать (см. главу II) для довольно широкого класса графов, называемых расширителями. Тем самым, для каждого такого графа С и для подходящего 3$ выполнено

Т(1С) ™ 8(8) (0.8)

Введем теперь параметр п явным образом: пусть 8 = ®п-Проблема состоит в том, чтобы найти асимптотику для 5(®п). Полагаем

®к(®п> = |а(®($п): число компонент связности А равно к|.

°n,k = SA> = I Ф<А> И °п = S<»n> = 1

Aí®k(Sn) kX>

к'

Оказывается, что последовательность on k удовлетворяет рекуррентному соотношению:

для некоторой последовательности an k такой, что an 0 ? an k !1РИ всех к. Эти неравенства вместе с равенством (0.9) влекут неравенство on k < (ап Q)k/k! и существование такого, что

У о , = о(о ). Положим b = rain а , . Тогда, если

í. п, к п п <й n,k

k>0

n

bn = an,0 + 0(1>• T°

°n,k ~ <«h.0>k/k! И °n ~ «РЧ^о'» (0-10) В этом случае цель достигнута, поскольку о =S(SB ), аа „= a' (S ).

п п п, и п

Заодно мы получаем предельное распределение случайной величины i ,

равной числу компонент связности случайного множества АсХ: Р(5П=Ю - ((а^Мт ехр<-ап10>

Заметим, что при выполнении условия - а^ 0! = о £{ап 0)' ^>]

величина имеет асимптотически нормальное распределение. В этом и в более сложных случаях используется приближенное представление суммы о^ = произведениями взда П(1+ф(А)>, берущимися по

семействам типа а также семействам подмножеств из 2Вп и

семействам более высокого порядка (см. §3.4). Отметим, что полученные здесь условия сходимости к пуассоновскому распределению отличны от тех, что получатся с помощь» метода моментов (см., например, (101, стр.117)

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

Дальнейшее развитие метода - в расширении области его применимости, именно:

1) В распространении метода ГФ на случай задач , в которых элементы границы и'элементы самого множества принадлежат одному пространству (как,например, в задаче о перколяции).

2) В ослаблении условий, при которых получены нераваства вида

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

3) В получение асимптотик СГО вида 8 (К) через суммы вида аг'($) для более слабых ограничений.

Метода исследования. В работе используются метода теории графов, комбинаторики и теории вероятностей. При выводе асимптотик (0.8) используются вероятностные и комбинаторные методы, а при получения неравенств вида (0.6) - методы теории графов и комбинаторики.

Научная новизна. В диссертации получены следующие основные результаты:

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

2. Получены оценки для числа множеств вершин двудольного графа, имеющих заданную мощность границы.

3. С помощью метода 1У$ получены асимптотики для числа антицепей в унимодальных частично упорядоченных множествах.

4. Как следствие получено новое доказательство асимптотики числа монотонных, булевых функций, найдены асимптотики числа двоичных кодов с расстоянием 2, числа нечетких монотонных функций, а также числа независимых множеств в двудольных графах,

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

6. Получено решение задачи поиска максимального нуля случайной монотонной (0,1)-функции, заданной на унимодальном множестве.

Практическая ценность. Работа имеет теоретическую направленность. Полученные результаты могут применяться для

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

Апробация и публикации. Результаты диссертации докладываюсь на международной конфоренциии по основам теории вычислений (Казань, 1987), на советско-германских семинарах (Самарканд, (Э87, Росток, 1988, Ереван, 1989), на международном семинаре по дискретной математике (Благоевград, 1990), на международном семинаре по экстремальным проблемам в конечных множествах (Вышеград, 1991), на мездународной конференции по случайным графам (Познань, 1991), на международном семинаре по сложности и реализации булевых функций (Дагштул, 1992), на всесоюзных конференциях по проблемам теоретической кибернетики (Иркутск, 1985, Горький, 1988, Волгоград, 1990), на всесоюзных семинарах по дискретной математике и ее приложениям (Москва, 1987, 1990), на всесоюзном семинаре по вероятностным методам в дискретной математике (Петрозаводск, 1988), на семинаре по кибернетике под руководством чл.-корр. РАН С.В.Яблонского, на семинаре по сложности булевых функций под руководством чл.-корр. РАН О.Б.Лупанова и с.н.с. В.М.Храпченко, на семинаре чл.-корр. РАН Б.А.Севастьянова и проф. В.Ф.Колчина в Математическом институте им. В.А.Стеклова, на других конференциях и семинарах.

Результаты диссертации опубликованы в работах 118 - 311.

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы. Первая и четвертая главы содержат по четыре параграфа, вторая - три, а третья - пять параграфаов. Объем работы 240 страниц, включая 8 страниц

цитированной литературы - В списке литература 81 наименование.

ОСКОВКОЕ СОДЕРЖАНИЕ РАБОТЫ

Глава I имеет вспомогательный характер. В § I.1 даны основные отделения. 13 § 1.2 доказываются вспомогательные утверждения с мощности границ множттг вериин в двудольных графах и верхние оценки длины градиентных покрытий. В § 1.3 определяются понятия б-связного и ¿-плотного множества и устанавливаются связи между покрытиями и б-связными множествами, выводится оценка числа (1-свягзных множеств заданной мощности в дискретных метрических пространствах. При оценке числа й-связных подмножеств существенную роль играет оценка числа п(0,т,в) связных порожденных т-вершшщых под^афоъ произвольного графа 0^(У;Е) с нумерованными вершинами и максимальной степенью верхшш в. В 1231 доказано (см.лемму 1.3.3), что

п(С,т,в) < !V!(4в)т~'. (0.11)

Это неравенство, по-существу, использовалось в работе автора (201 в Г9С7г. Приблизительно такая же идея использовалась в работе О.Г-'.Лупанова 121 при оценке числа схем из функциональных элементов. Неравенство (0.11) является достаточно удобным инструментом исследования случайных графов. Оно использовалось в работах ЭЛомана 1111, К.Вебера 1121, А.В.Косточки 1131.

В^ 1.4 получены утверждения о том что двудольные графи, порождаемые парами соседних слоев некоторых частично упорядоченных множеств, являются расширителями. Па самом деле, речь идет о выводе утверждений типа: " АаХ, !А1<е!Х! влечет !АЬ' ¡д(А)! (1 -й)" из утверждений типа: "Среда всех равномощннх множеств А< X наименьшую

границу имеет лексикографический отрезок". В доказательстве этих утверждений используются результаты Краскала 114], Д. Катоны 1151," Л.Харпера [161 и обобщения, полученные С.Л.Безруковым {171.

Глава II посвящена оценкам числа мнотеств с заданной мощностью границы в двудольных графах. В § 2.1 дана постановка задачи. В § 2.2 получены основные результаты этой главы, а именно, неравенство (0.6) для d-связных мнокеств. В § 2.3 это неравенство доказано для множеств, не являющихся d-сьязннш. Для получения оценки используется прием, который ш называем "методом контейнеров". Суть его в следующем: каждому множеству А^Х с границей ö(А) сопоставляется его приближение (контейнер), г.иляицийся парой вида <F,D), где Fs"3(A), AcD. Идея получения г.ерхне!! оценки числа множеств с заданной мощностью граншн состоит ь той, чтобы оценить сверху число контейнеров п максимальный объем контейлера, т.е. максимально возможное число мнокеств с заданным приближением, и перешокить эти оценки. Сначала с помощью достаточно тонкого кодирования связных мног.еств доказывается существование контейнеров (лекш 2.2.3 и 2.2.4) и оценивается их число (леммы 2.2.5 и 2.2.G). Затем понятие прио-чжжа'я уточнился (определение 2.2.4), т.е. как бы выбираются r.onee е(лкш контейторы. Их, вообще говоря, больше, чем прэяшх. (лок-.а 2.Я.7), но зато их объем удается оценить достаточно точно (лем^а 2.2.10). Наконец, отсюда выводится основной результат:

Теорема 2.2.1. Пусть G=(X,Z;E) - двудольный граф такой, что

min !ö(v)l=ae, max ¡ö(v)!«n>, v*ae, max Iö(v)f0(ü)l<q,

v^X veZ v,ueX

1> 0 ja?7"4. Пусть i'd(G,g,ö) - число d-связных подмножеств A=X

таких, что ! (AI¡<!д(А)!(1-ß), где lA]=iviX:d(v)&9(A)). Тогда при достаточно больших ж

Ф(С,е,0) $ ¡Х!2в(,~ 6/(6 lrj5$,) (0.12)

Теорема обеспечивает выполнение условий вида (0.6) и (0.7) для многих задач.

Глава III посвящена вычислению сумм граничных функционалов. В § 3.1 определяется понятие функциональной пары, вводятся сумммы граничных функционалов и устанавливаются асимптотики таких сумм типа (0.(0), а также предельные распределения числа компонент связности случайных множеств. В § 3.2 результаты предыдущего параграфа переносятся на случай вложенных подсемейств. В § 3.3 оценки /да суш граничных функционалов обобщаются на d-связные множества, уточняется структура компонент типичных множеств. В § 3.4. асимптотики для сумм граничных функционалов распространяются на область более слабых, чем в § 3.1, ограничений. В § 3.5 результаты предыдущих параграфов доказываются для так называемых ординарнкх ФП, для которых условия существования асимптотик легко проворятся и которые удобны в приложениях. Пусть 1=(Х,ф)-нжочорэя ФП и Wk(I) = iAilt(I): ¡А'=Ю, ФП I называется (А ,эе, q, с) -ординарной, если

1) для всякого у«Х и натурального числа к.

j{Ae«k(I): ф(А1Ку)) > ф(А)-ф({у)>|| ^ ае?^

2) для всех AiX и veXVA

(p(AUiv)) « ф(А).ф{{7))-2 ,

3) ДЛЯ ВСЯКОГО ViX

ф({у)) <

Последовательность ФП (1^=(Хп,фп)) называется Ä-сходящейоя, если lim J a'iiyjj) - О.

П-аэ к>Д

Основным результатом главы является

Теорема З.Б.З. Пусть последовательность (2,ас^,q,с)-ординарных il =(Х ,ф )) является 2-сходящейся, Ilm х - Тогда при п-«-

П Ti * Ti Л п 1

П-Х»

Т(1п) ~ ехр((1г(1п)), (0.13)

где Иг(1п> = а'ш,) 4- a'itt,) - a2(il, )/2 - а' \2? j ^ ( п] ^[23.(1 I = U.ViX , <J>({U,v)) > (|({и)) <Д(к);],

а' (1)) = I а сумма берется по всем Ни),(7))

Это утверждение позволяет получать асимптотики для многих перечислительных ИЗ.

Глава IV посвящена приложениям. Здесь с помощью метода PI получены асимптотики для перечислительных задач из теории rpaJioB, конечнозначшх логик и комбинаторики. В § 4.1 получены асимптотики числа независимых множеств в двудольных графа?. В пункте 4.I.I асимптотики для числа независимых множеств и расширителях. В пункте 4.1.2 результаты распространены на полурасширите.чи. Здесь же в качестве следствия получена асимптотика числа двоичных кодов

с расстоянием 2. В -5 4.2 получена асимптотика для числа антицепей в унимодальных ранжированных множествах. В § 4.3 получены асимптотики числа монотонных функций из некоторых классов многозначных логик, в частности, числа монотонных булевых функций, числа обобщенных нечетких функций, получены нижние оценки числа монотонных (0.1)-функций трехзначной логики. В § 4.4 получено асимптотическое решение задачи поиска максимального верхнего нуля монотонных (О. i )-функций па унимодальных часпггао упорядоченных множествах.

ЛИТЕРАТУРА

1. Дискретная математика и математические вопросы кибернетики // Сб.статей п.р. С.В.Яблонского и О.Б.ДуПанова - И.: Наука, 1974.

?.. Луппнов О.В. О синтезе некоторых классов управляющих систем // Проблемы кибернетики - 1963 - Вып. 10 - с. 63-98.

3. Dedeklnd R. Uber Zerlegungen von Zahlen durch ihre groaaten gemeinsamen Teilor // festschrift Hoch. Braunschweig u. ges.Herke II - 1897, S. - p. 103-148.

4. Kleltman D. On Dedeklnd's problem: the number of monotone Boolean functions // Proc. Am. Math. soc. - 21, Ä3 -1969 -p. 677-682.

5. Коршунов А.Д. Реаение проблемы Дедеккнда о числе монотонных булевых функций // Докл. АН СССР - 1977 - т. 223, £4 - с. 543-546.

6. Коршунов А.Д. О числе монотонных булевых функций // Проблемы кибернетики. - 1980 - Вып. 38 - с. 5-108.

7. Kesten H. Percolation theory for mathematicians // Boston e.g.: Birkhauser - 1982 - 423 p. (Русск. перевод:Кестен X. Теория

просачивания для математиков// М. , Мир, 1986)

8. Яблонский C.B. функциональные построения в k-значной логике // Труда МИ АН СССР Т. 51 - M. 1958 - с. 5-142.

9. Алексеев В.В. О числе монотонных k-значных функций // Проблемы кибернетики - 1974 - вып. 28. - С. 5-24.

10. Колчин В.Ф., Севастьянов В.А., Чистяков В.П. Случайные размещения // М.: Наука - 1976.

11. Томан Э. Геометрическое строение случайных булевых функций //

.. СО„,.35 М- ,.1979 -, г.. JJ W-3?

12. Weber К. On components of random graphs In n-cube // Electron. Inf.verarb. Kybern. - EIK - 22 - 1986 - p. 601-613.

13. Косточка A.B. Наибольшие паросочетания и компоненты связности случайных суграфов n-мерного единичного куба // Метода дискретного анализа в изучении булевых функций и графов. - Новосибирск, 1989, - Вып. 48. - с. 23-39.

14. Kruscal J.B. The number of Syraplices In a complex // Math.OptimisâtIon Techniques - Univ. of California Press -Berkeley, Calif. - 1963. - p. 251-278.

15. Katona G.O.H. The Haimling sphere has minimum boundary // Studia Sei. Math. Hungarica - 10, 1975 - p. 131-140.

16. Harper L.H. Optimal numbering and isoperimetric problems on graphs // J. Comb. Theory - 1, JÉS - 1966 - p. 385-393.

17. Безруков С.Л. Минимизация теней подмножеств частичных отображений // Метода дискретного анализа в исследовании функциональных систем, вып. 47 - Новосибирск, 1988 - С. 3-18.

Работы'автора по теме диссертации

18. Сапоженко A.A. О сложности дизъюнктивных нормальных форм.

получаемых с помощью градиентного алгоритма // Дискретный анализ

- 1972 - Новосибирск, вып. 21 - с. 62-71.

19. Сапозенко A.A., Асратян A.C., Кузюрин H.H. Обзор некоторых результатов по задачам о покрытии // Методы дискретного анализа

в решении комбинаторных задач, - вып. 30 - Новосибирск, 1977,

- с. 46-75.

20. Сапоженко A.A. Метрические свойства почти всех функций алгебры логики // Дискретный анализ, вып. 10 - Новосибирск, 1967, -с. 91-119.

21. Сапоженко A.A. Дизъюнктивные нормальные формы - М., МГУ, 1975.

- 90 с.

22. Сапоженко A.A. Асимптотика числа монотонных функций на частичных упорядоченных множествах // Докл.АН СССР, - т. 305, й2

- с. 279-283.

23. Сапоженко A.A. О числе множеств с заданной мощностью границы в двудольных графах // Методы дискретного анализа в решении комбинаторных проблем - вып. 45 - Новосибирск, 1987 - с. 42-70

24. Сапоженко A.A. О числе антицепей в ранжировнных частично упорядоченных множествах // Дискретная математика -1989 т. I, вып.1 - с. 74-93

25. Сапоженко A.A. О числе антицепей в многослойных ранжировнных частично упорядоченных множествах // Дискретная математика - 1989 т. I, вып.2 - с. I10-128.

26. Сапоженко A.A. Асимптотика для одаого типа функционалов на конечных множествах // Вероятностные метода в дискретной математике. Тезисы докладов Второй всесоюзной конференции -Петрозаводск, 1988 - с. 90-91.

27. Сапоженко A.A. О поиске максимального верхнего нуля монотонных

Функций на ранжированных множествах // Журнал вычислительной математики и математической физики - т. 31, *12, - 1991 -с. I871-1884.

28. Сапоженко A.A. О числе специальных подмножеств ве[еин двудольного графа, имеющих заданную мощность границы // Труда семинара по дискретной математике и ее приложениям - М.: МГУ, 1989 - с. I7I-I73.

29. Емеличев A.B., Сапоженко A.A. О число монотонных самодвойственных функций // Материалы второго Всесоюзного семинара по дискретной математике и ее приложениям - М.: Изд-во МГУ, 1988 -с. 140-141.

3D. Коршунов А.Д., Сапоженко A.A. О числе двоичных кодов с расстоянием 2 // Сб."Проблемы кибернетики", выи. 40 - М.: Паука, ! т с. III-I40.

.",a[iit"h'-riko A.A. The number of fuz?,y monotone functions /< I. not.es in Comp.sei. - 1987 - . 278 - p. 389-390.