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

Московский государственный университет имени М. В. Ломоносова

Н

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

□и^4----

Дайняк Александр Борисович

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2009

003476628

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

Научный руководитель: доктор физико-математических наук,

профессор

Сапоженко Александр Антонович

Официальные оппоненты: доктор физико-математических наук,

руководитель отдела ИСП РАН Кузюрин Николай Николаевич

кандидат физико-математических наук, старший научный сотрудник ВЦ РАН Вялый Михаил Николаевич

Ведущая организация:

Институт системного анализа РАН

Защита диссертации состоится 9 октября 2009 г. в 11:00 на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М.В.Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан « » сентября 2009 г.

Ученый секретарь диссертационного совета

профессор

Трифонов Н. П.

Общая характеристика работы

Актуальность темы. Рассматриваемые в диссертации вопросы относятся к перечислительной и экстремальной теории графов. Доказываются верхние и нижние оценки числа независимых множеств (то есть подмножеств попарно не смежных вершин) в графах из различных классов, и описывается структура графов, на которых достигаются полученные оценки.

Исследования в области перечисления независимых множеств в графах ведутся с середины прошлого века. Результаты этих исследований находят приложения не только непосредственно в математике (комбинаторная теория чисел, теория кодирования, теоретическая информатика), но и в других областях. Так, например, в теоретической химии важными характеристиками соединений являются индексы Мэррифилда-Симмонса,1 и Хосойи2, которые есть не что иное, как число независимых множеств в соответствующих графах.

Подмножество попарно несмежных вершин графа называется независимым. Под максимальными независимыми множествами (м. н.м.) понимаются максимальные по включению независимые множества. Максимальный размер независимого множества в графе называется числом независимости графа. Будем обозначать через a(G) число независимости графа G. Через i(G) и iu{G) будем обозначать число независимых множеств и число м. н. м. в G соответственно.

Одними из первых работ в области перечисления независимых множеств являются статьи3 Миллера, Маллера и Муна, Мозера, в которых независимо был доказан следующий факт.

Теорема (P.E. Миллер, Д.Е. Маллер и Дж.У. Мун, JI. Мозер). Пусть G — граф на п вершинах, имеющий максимальное число м. н. м. среди всех п-вершинных графов. Тогда G является

объединением п/3 копий графа Кз при п = 0 (mod 3),

объединением графа и (п — 2)/3 копий Кз при п = 2 (mod 3), объединением (п — 4) копий графа Кз и либо графа К4, либо двух графов Кг при п = 1 (mod 3).

'Merrifield R.E., Simmons Н. Е. Topological methods in chemistry, New York, John Wiley & Sons, 1989.

2Hosoya H. Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons //Bull. Chem. Soc. Jpn. 1971. 44(9). P. 2332-2339.

3Miller R.E., Muller D.E. The problem of maximum consistent subsets — IBM Research Report RC-240. 1960. J.T.Watson Research Center, Yorktown Heights, N.Y.

Moon J.W., Moser L. On cliques in graphs // Israel J. Math. 1965. 3. P. 23-28.

Экстремальные графы в приведённой выше теореме являются частным случаем графов UKn¡a, определяемых следующим образом: UKn¡0¡ суть объединение (a-([n/a J + 1)—п) клик размера [п/а\ и (п~а-[п/а J) клик размера \п/а~\. Можно проверить, что n(UKnia) = п, a{UKn¡a) — а.

Теорема Муна-Мозера обобщалась в различных направлениях несколькими авторами. Так, например, К. Кройтору4 получил верхние оценки числа м. н. м. в классе всех графов с заданным числом независимости. Дж. М. Нильсен получила5 достижимую верхнюю оценку числа м. н. м. заданного размера в графах. В обеих указанных задачах максимум достигается на графе иКща. Подобные результаты используются для получения оценок времени работы алгоритмов раскраски графов и определения мощности максимального независимого множества (см., например, работы Д. Эппштейна6 и Дж.М. Нильсен).

Интерес представляет также получение оценок числа м. н. м. в классах графов, описанных в терминах запрещённых подграфов. М. Гуйтером и Ж. Тузой была получена7 оценка числа м. н. м. в графах без треугольников (то есть в графах, не содержащих K¡ в качестве подграфа). В. Е. Алексеев исследовал8 число м. н. м. в графах, не содержащих «большого» па-росочетания (объединения графов К2) в качестве порождённого подграфа.

Исследовался вопрос о числе независимых множеств в графах с небольшим числом циклов, в первую очередь, деревьев. В работе Г. Продингера и Р. Ф. Тичи9 были получены верхние и нижние оценки числа независимых множеств в деревьях с заданным числом вершин. Через фп обозначим (п + 2)-ое число Фибоначчи (фо = 1, 4>i = 2, фп = фп-1 + Фп-2 при п ^ 2).

Теорема (Г. Продингер, Р. Тичи). Пусть Т — дерево на п вершинах. Тогда фп ^ i{T) < 2"-1 + 1, причём равенство г(Т) = фп имеет место

4Croitoru С. On stables in graphs // Proc. Third Coll. Operations Research, Babes-Bolyai University, Cluj-Napoca, Romania. 1979. P. 55-60.

5Nielsen J.M. On the number of maximal independent sets in a graph. Preprint. Research Series RS-02-15, BRICS. Aarhus, Denmark: University of Aarhus, Department of Computer Science, 2002. Юр.

eEppstein D. Small maximal independent sets and faster exact graph coloring // J. Graph Algorithms and Applications (special issue for WADS'01) 2003. 7(2). P. 131-140.

7Hujter M., Tuza Í. The number of maximal independent sets in triangle-free graphs // SIAM J. Discr. Math. 1993. 6(2). P. 284-288.

8Алексеев В. E. Верхняя оценка числа максимальных независимых множеств графа // Дискретная математика. 2007. Т. 19. Вып. 3. С, 84-88.

'Prodinger H., Tichy R.F., Fibonacci numbers of graphs // Fibonacci Quart. 1982. 20(1). P. 16—21.

только в случае, если Т является простой цепью, а равенство ЦТ) — 2"-i ^ лишъ е случае когда Т — звезда.

В той же статье было найдено число независимых множеств в цикле на п вершинах. По-видимому, со статьи Продингера и Тичи берёт начало использование термина «число Фибоначчи графа» в качестве синонима для числа независимых множеств.

В статье Г. С. Вильфа была получена10 верхняя оценка числа максимальных независимых множеств в деревьях с заданным числом вершин:

Теорема (Г. С. Вильф). Для любого дерева Т на п вершинах выполнены неравенства ím(T) < при нечётных п, и %м(Т) < 1 +

при чётных п.

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

Пусть и = {ui, ..., ud_i}, V = {ui, ..., vp}, W = {wu ..., wq}. Обозначим через BdtPtq дерево на множестве вершин UUV\JW, такое, что его поддеревья, порождённые множествами {ni} U V, {u¿_i} U W и U представляют собой соответственно звёзды KiiP, Kí¡q и цепь Pd-i- Отметим, что Дцд есть просто цепь длины d. П. Д. Вестергардом и А. С. Педер-сеном была получена13 следующая верхняя оценка числа независимых множеств в деревьях заданного диаметра:

Теорема (П. Д. Вестергард, А. С. Педерсен). Для любого п-вершинного дерева Т диаметра d выполнено неравенство i(T) ^ ¿(Дг,п-сг,1), обращающееся в равенство только если Т изоморфно B¡¡¡n-d,i ■

10Wilf Н. S. The number of maximal independent sets in a tree // SIAM J. Alg. Discr. Methods 1986. 7. P. 125-130.

nSagan В. E. A note on independent sets in trees // SIAM J. Discr. Math. 1988. 1. P. 105-108.

l2Sagan B.E., Ying G.Ch., Meng K.K., Vatter V. Maximal independent sets in graphs with at most r cycles // J. Graph Th. 2006. 53. P. 270-282

13Pedersen A. S., Vestergaard P. D. An upper bound on the number of independent sets in a tree // Ars Combinatoria. 2007. 84. P. 85-96.

В той же работе был поставлен вопрос о нижних оценках числа независимых множеств в деревьях заданного диаметра. Для деревьев диаметра 4 исчерпывающий ответ был дан в работе Вестергарда, Педерсена, Сапоженко и Френдрупа.14 Ими была описана структура экстремальных деревьев диаметра 5 для достаточно больших п. Проблема Вестергарда (полное описание экстремальных деревьев при произвольном заданном числе вершин и диаметре) до сих пор не решена в общем случае.

Важным направлением является получение асимптотических оценок числа независимых множеств в параметрических классах графов. К таковым относятся диаграммы Хассе частично упорядоченных множеств, плоские прямоугольные решётки и др. Для числа независимых множеств в полных бинарных деревьев с п ярусами рёбер В. П. Ворониным и Е.В. Демаковой получен15 следующий результат.

Теорема (В.П. Воронин, Е.В. Демакова). Обозначим через 1ц число независимых множеств в полном бинарном дереве, имеющем к ярусов рёбер. Существуют константы ß и 7 такие, что при п -4 оо справедлива асимптотика

in~ß■ 72"-

Интерес представляют оценки числа независимых множеств в регулярных и «почти регулярных» графах (то есть графах, в которых степени вершин либо попарно равны, либо лежат в сравнительно узком диапазоне). К задачам такого рода сводятся некоторые перечислительные проблемы теории чисел и теории групп. Например, перечисление множеств, свободных от сумм (МСС), в абелевых группах (то есть множеств А, таких, что АГ\{а+Ь | а, Ь £ А} = 0) сводится к перечислению независимых множеств в графах Кэли. Этот подход был применён Н. Алоном16 для получения асимптотики логарифма числа МСС в отрезке натуральных чисел. Позже, также с применением теории графов, А. А. Сапоженко получил17 асимптотику числа МСС в отрезке натуральных чисел. В

14Frendrup A., Pedersen A.S., Sapozhenko A.A., Vestergaard P.D. Merrifield-Simmons index and minimum number of independent sets in short trees // Department of Mathematical Sciences, Aalborg University. Research Report Series. ISSN 1399-2503. R-2009-03, January 2009. 13pp.

15Воронин В.П., Демакова Е.В. О числе независимых множеств для некоторых семейств графов // Труды IV Международной конференции «Дискретные модели в теории управляющих систем», Красновидово, 19—25 июня 2000 г., М: МАКСПресс, 2000. С. 145-149.

1вА1оп N. Independent sets in regular graphs and suin-free subsets of finite groups // Israel J. Math. 1991. 2(73). P. 247-256.

17Сапоженко A.A. Доказательство гипотезы Камерона-Эрдеша о числе множеств, свободных от сумм // Математические вопросы кибернетики. Вып. 12. М.:Физматлит. 2003. С. 5-14.

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

Теорема (Н. Алон). Для любого к-регулярного графа G на п вершинах число независимых множеств i{G) удовлетворяет неравенству

i(G) < 2»<1+W», (1)

где ¡{к) = О{к~0Л).

В доказательстве приведённой теоремы подсчёт числа независимых множеств в регулярных графах был сведён к подсчёту числа независимых множеств в почти регулярных двудольных графах.

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

А. А. Сапоженко предложил18 более простое доказательство оценки (1), улучшив, кроме того, остаточный член до f(k) = 0(VÄF4n/c) и распространив оценку на квазирегулярные графы. Алон высказал следующее предположение.

Гипотеза (Н. Алон). Наибольшим числом независимых множеств среди к-регулярных графов на п вершинах при 2к | п обладает единственный с точностью до изоморфизма граф, представляющий собой объединение ¿fe непересекающихся полных двудольных графов.

Граф из формулировки гипотезы будем называть далее графом Алона. Эта гипотеза остается недоказанной до сих пор (сентябрь 2009), хотя большинство исследователей не сомневаются в ее справедливости. Справедливость этой гипотезы означала бы в частности, что в (1) имеет место оценка f(k) = 0(к~г).

С помощью теоретико-информационного подхода Дж. Каном и А. Лоренцем была получена19 достижимая верхняя оценка числа независимых множеств в двудольных регулярных графах, что косвенно подтверждает гипотезу Алона.

Теорема (Дж.Кан, А.Лоренц). Пусть G — двудольный к-регулярный граф на п вершинах. Тогда

i(G) ^ (2м - 1)®.

18Саложенко А. А. О числе независимых множеств в расширителях // Дискретпая математика. 2001. Т. 13. № 1. С. 56-62.

19Kahn J., Lawrenz A. Generalized rank functions and an entropy argument //J. Comb. Th. Ser. A. 1999. 87. P. 398-403.

Отметим, что вопрос о единственности экстремального графа в теореме Кана-Лоренца до сих пор остаётся открытым.

Интересен вопрос о числе независимых множеств в графах, для которых известен размер наибольшего независимого множества. Это связано с довольно общим подходом в перечислительной комбинаторике, который может быть назван методом контейнеров. Метод состоит в следующем. Пусть Ли В — семейства подмножеств некоторого множества. Скажем, что семейство В является системой контейнеров для Л, если для каждого А £ Л найдётся В £ В, такое, что А С. В. Тогда, очевидно, выполнено неравенство

вей

Грубые на первый взгляд, такие оценки при подходящем выборе системы В позволяют получать асимптотику. Таким способом, например, А. А. Сапоженко получил20 решение проблемы Камерона-Эрдёша. Вопрос о применимости метода контейнеров для задачи оценки числа независимых множеств в графах тесно связан с указанной выше задачей перечисления независимых множеств в графах с фиксированным числом независимости, поскольку семейство всех м. н. м. графа является системой контейнеров для семейства всех независимых множеств, и число независимости графа является прямым ограничением размера таких контейнеров.

В. Е. Алексеевым была доказана следующая

Теорема (В.Е. Алексеев). Для любого графа (7 выполнено неравенство

(^ + 1)", (2)

гдеп = а = а(С).

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

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

20Сапоженко А. А. Доказательство гипотезы Камерона-Эрдеша о числе множеств, свободных от сумм // Математические вопросы кибернетики. Вып. 12. М.:Физматлит. 2003. С. 5-14.

и числом независимых множеств в регулярных и «почти регулярных» графах.

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

Научная и практическая ценность. Работа имеет теоретическую направленность. Получены достижимые оценки числа независимых множеств в деревьях с заданным числом вершин и диаметром, при этом описана структура экстремальных деревьев.

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

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

Публикации и апробирование. Результаты диссертации докладывались на семинаре ВМК МГУ «Дискретный анализ» (руководители — А. А. Сапоженко, Т. В. Андреева), на VI молодёжной научной школе по дискретной математике и её приложениям (Москва, 16-21 апреля 2007), на VII молодёжной научной школе по дискретной математике и её приложениям (Москва, 18-23 мая 2009), на XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008), на XVII Международной школе-семинаре «Синтез и сложность управляющих систем» (Новосибирск, 27 октября - 1 ноября 2008), на Международной конференции «Современные проблемы математики, механики и их приложений» (Москва, 30 марта - 2 апреля 2009) а также на XVIII Международной научной конференции «Дискретные модели в теории управляющих систем» (Москва, 6-9 апреля 2009).

По теме диссертации опубликовано 10 работ.

Структура и объем работы. Диссертация состоит из введения, трёх глав, приложения и списка литературы. Объём работы 98 страниц.

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

Первая глава посвящена оценкам числа независимых множеств в деревьях фиксированного диаметра. В разделе 1.1 вводится понятие ёмкости графа и даётся несколько других определений, доказываются вспомогательные утверждения. В разделе 1.2 доказываются нижние оценки числа независимых множеств в деревьях диаметра 6,7,8,9. В частности, доказываются следующие теоремы:

Теорема 8 (разд. 1.2). Любое дерево диаметра 6 на п вершинах содержит не меньше независимых множеств. Любое дерево диаметра 7 на п вершинах содержит не меньше независимых множеств.

Теорема 9 (разд. 1.2). Любое дерево диаметра 8 на п вершинах содержит не меньше независимых множеств. Любое дерево диаметра 9 на п вершинах содержит не меньше независимых множеств.

В разделе 1.3 доказываются теоремы, характеризующие структуру экстремальных деревьев в проблеме Вестергарда. Дерево Т называется (тг, с!)-минимальным, если оно имеет наименьшее число независимых множеств среди всех деревьев диаметра й на п вершинах. Ёмкостью п-вершинного графа С?, имеющего г (С?) независимых множеств, называется величина с(С) = (г(С))1//п (отметим, что это определение отличается от известного понятия ёмкости Шеннона). Деревья минимальной ёмкости играют существенную роль в описании структуры (п, с!)-минимальных деревьев. Через Рт будем обозначать лес, полученный из дерева Т удалением всех центральных вершин. Положим

Щ = Ы с(Т).

Т- дерево, &ат(Г)=<г

Теорема 11 (разд. 1.3). Пусть й — чётное число, иМ.^. ~ множество всех деревьев Т', для которых с(Т') = т1пт<;(г с(т). Тогда найдётся такое N = N((1), что для д! £ {й +2, ¿ + 3}, произвольного натурального числа п, и произвольного (п, д!) -минимального дерева Т в лесе Рт не более N вершин лежат в компонентах связности, не изоморфных деревьям из Ма-

Пусть множество Ма определено так же, как в теореме И. Рассмотрим множество

Л = {з е N I ВТ' е Мл,

Назовём число q разложимым по если = За для некоторых (не обязательно различных) чисел Л, • • •, л € 5в.-

Теорема 12. Пусть А — чётное натуральное число, ид,' £ {(1+2, с!+3}. Существует такая константа И, что для всех п, п^ N, таких, что (п — + й +1) разложимо по &> и произвольного (п, с1') -минимального

дерева Т, каждая из компонент леса Ер изоморфна некоторому дереву из М^

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

В разделе 1.5 получено обобщение теоремы Воронина-Демаковой на случай д-арных деревьев при произвольном д. Обозначим через ся<к число независимых множеств в полном д-арном дереве, имеющем к ярусов рёбер, или, что то же, диаметр 2к. Доказана следующая

Теорема 15 (разд. 1.5). При ц е {2,3,4} для ¿^ справедлива асимптотика при к оо;

~ Ря • 7д\

для некоторых констант /?9 и 7?.

При д > 5 справедлива асимптотика при к-* оо:

о"

1>д,2к ~ «9,0-7, .

где константы а?,о и адд удовлетворяют неравенству а9)0 > а.ь\.

Заслуживает внимания различный характер асимптотики величины при я < 4 и ? ^ 5.

Результаты первой главы опубликованы в [2, 6]. Вторая глава диссертации посвящена оценкам числа максимальных независимых множеств в графах заданного диаметра. В разделе 2.1 вводятся основные определения и доказываются некоторые вспомогательные утверждения. В разделе 2.2 получено полное описание графов с заданным диаметром, на которых достигается минимум числа м.н. м. Определим последовательность фп соотношением фп = + "Фп-з и начальными условиями фо — фх = 1, Ф2 = 2.

Теорема 16 (разд. 2.2). Для любого <1, 4, и для любого графа С? диаметра <1 выполнено неравенство гд/(С?) ^ фа+г- Если гм{0) = фа+1, то множество У(С) можно разбить на подмножества Ц), ... так, что при любом к, 2 ^ к ^ с1, и любом г, 0 ^ г ^ с1 — к, е (3 отсутствуют рёбра между вершинами из Щ и Ц+/., и для всякого г, 0 ^ г ^ 1, подграф графа С?, порождённый множеством V* и ^+1, является полным двудольным с долями VI и 1^+1.

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

Теорема 17 (разд. 2.3). Для любого п-вершинного дерева Т диаметра d выполнено неравенство гм{Т) ^ М(п, d), где

При d ^ 9 существует единственное с точностью до изоморфизма дерево, на котором достигается указанная оценка (полное описание экстремальных деревьев при всех d см. в разд. 2.8 диссертации).

Приведённая теорема является усилением теорем Вильфа и Сагана.

Результаты второй главы опубликованы в [7, 8, 9, 10].

В третьей главе диссертации исследуется число независимых множеств в графах с заданным размером максимального независимого множества. Неравенство (2) обращается в равенство при а] га (максимум числа независимых множеств достигается на графе IIКп<а). Доказываемая в разделе 3.1 теорема 18 даёт уточнение оценки (2), делающее её достижимой при всех возможных сочетаниях параметров п, а, а также описывает экстремальные графы.

Теорема 18 (разд. 3.1). Для любого п-вершинного графа (7, такого, что а(0) = а, выполнено неравенство г (б) ^ г{икп<а), обращающееся в равенство только на графах, изоморфных иКп<а.

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

Теорема 19 (разд. 3.2). Для любых п, а (п ^ 2) среди всех деревьев на п вершинах с числом независимости а максимальное число независимых множеств имеют только деревья, изоморфные дереву, полученному из звезды подразбиением (п — а — 1) рёбер.

Теорема 20 (разд. 3.2). Среди всех лесов на п вершинах без изолированных вершин с числом независимости а максимум числа независимых множеств достигается только на лесах, являющихся объединением паросочетания на 2(п — а — 1) вершинах и звезды

M(n,d) = <

Vfc-i + (2("-d+1>/2 - 1 )фЛ. i>d- 2 + Ф<1,

1-2, при d^ 4, n - d = 2k + 1, при d ^ 4, n — d = 2,

при d^b, d^7,n — d = 2k ^ при d £ {4,7}, n - d = 2k ^ 4.

Раздел 3.3 посвящён оценкам числа независимых множеств в регулярных п-вершинных графах, число независимости в которых близко к п/2 (то есть к максимально возможному).

Теорема 22 (разд. 3.3). Для сколь угодно больших К и N существуют к-регулярный п-вершинный граф (7, такой, что к > К, тг > N, и

^(»•(С)) >£(1 + П(*Г1))-

С другой стороны, для любой константы в € (0, 1/2) для любого к-регулярного п-вершинного графа С, такого, что ск(С?) < |(1 — £1(к~в)), выполнено неравенство

В терминах контейнеров, теорема 22 показывает, в частности, что существуют графы, в которых большое число независимых множеств обеспечивается не максимальным размером «контейнера» (м.н. м.), как это имеет место в графе Алона, а большйм числом контейнеров.

В разделе 3.4 доказывается обобщение теоремы Кана-Лоренца на квазирегулярные двудольные графы:

Теорема 23 (разд. 3.4). Пусть £ — двудольный граф с долями А и В. Пусть степени вершин из А ограничены сверху числом кг, а степени вершин из В ограничены снизу числом Тогда

Результаты третьей главы опубликованы в [1, 3, 4, 5].

В Приложении приведена последовательность Штурма для полинома, использующегося в доказательстве теоремы 15.

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

1. Для произвольного 4 описана структура (п, й)-минимальных деревьев. Получены асимптотически достижимые нижние оценки числа независимых множеств в деревьях диаметра б, 7, 8, 9.

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

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

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

Публикации по теме диссертации

1. Дайняк А. Б. О числе независимых множеств в графах с фиксированным числом независимости // Дискретная математика. 2007. Т. 19. Вып. 2. С. 63-66.

2. Дайняк А. Б. О числе независимых множеств в деревьях малого диаметра // Материалы XVII Международной школы-семинара «Синтез и сложность управляющих систем» (Новосибирск, 27 октября — 1 ноября 2008) / Под ред. О. М. Касим-Заде. Новосибирск: Изд-во ИМ СО РАН, 2008. С. 32-36.

3. Дайняк А. Б. О некоторых вопросах, связанных с гипотезой Алона о числе независимых множеств // Материалы VI молодёжной научной школы по дискретной математике и её приложениям (Москва, 16— 21 апреля 2007). Часть I. / Под ред. А.В.Чашкина. М.: ИПМ им. М. В. Келдыша РАН, 2007. С. 26-30.

4. Дайняк А. Б. Уточнение оценки В. Е. Алексеева числа независимых множеств в графах // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции (Казань, 2—7 июня 2008) / Под ред. Ю. И. Журавлёва - Казань: Отечество, 2008. С. 25.

5. Дайняк А. Б. Оценки числа независимых множеств в графах с фиксированным числом независимости // Вестник Московского университета, сер. 15. Вычислительная математика и кибернетика. 2009. №2. С. 45-48.

6. Дайняк А. Б. О числе независимых множеств в деревьях фиксированного диаметра // Дискретный анализ и исследование операций. 2009. Т. 16. №2. С. 61-73.

7. Дайняк А. Б. О нижних оценках числа независимых множеств в некоторых классах графов // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов — 2009». Секция «Вычислительная математика и кибернети- ■ ка». 13—18 апреля, Москва, МГУ имени М. В. Ломоносова. М.: МАК-СПресс, 2009. С. 24.

8. Дайняк А. Б. О числе максимальных независимых множеств в деревьях фиксированного диаметра // Современные проблемы математики, механики, и их приложений. Материалы международной конференции, посвященной 70-летию акад. В. А. Садовничего. М.: Университетская книга, 2009. С. 357.

9. Дайняк А. Б. Оценки числа независимых множеств в графах из некоторых классов // Восьмая международная конференция «Дискретные модели в теории управляющих систем» (Москва, 6—9 апреля, 2009 г.): Труды / Отв. ред. В. Б. Алексеев, В. А. Захаров. - М.: МАКС

Пресс, 2009. С. 79-81.

10. Дайняк А. Б. О числе максимальных независимых множеств в деревьях фиксированного диаметра // Сборник статей молодых учёных факультета ВМК МГУ. Выпуск 6. 2009. М: Изд. отд. ф-та ВМК МГУ; МАКС Пресс, 2009. С. 58-68.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 01.09.2009 г. Формат 60x901/16. Усл.печл. 1,0. Тираж 100 зкз. Заказ 449. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. МБ. Ломоносова, 2-й учебный корпус, 627 к.

Введение

Глава 1. Оценки числа независимых множеств в деревьях фиксированного диаметра

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

1.2 Число независимых множеств в деревьях диаметра 6.

1.3 Структура (п, с?)-минимальных деревьев.

1.4 Радиально регулярные деревья.

1.5 Асимптотика числа независимых множеств в полных д-арных деревьях.

Глава 2. Оценки числа максимальных независимых множеств в графах фиксированного диаметра

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

2.2 Нижние оценки числа максимальных независимых множеств в графах фиксированного диаметра.

2.3 Верхние оценки числа максимальных независимых множеств в деревьях фиксированного диаметра.

Глава 3. Оценки числа независимых множеств в графах с фиксированным числом независимости

3.1 Верхняя оценка числа независимых множеств в классе всех графов с заданным числом независимости

3.2 Верхние оценки числа независимых множеств в лесах с заданным числом независимости.

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

3.4 Число независимых множеств в квазирегулярных двудольных графах.

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

История вопроса

Задача перечисления независимых множеств в графах рассматривается с середины прошлого века и успела стать одним из классических разделов теории графов. Эта задача находит приложения не только непосредственно в математике (комбинаторная теория чисел [17, 21], теория кодирования [14], теоретическая информатика [26]), но и в других областях. Так, например, в теоретической химии параметр i(G), равный числу независимых множеств графа G, называется индексом Мэррифилда-Симмонса [34], а параметр i'(G), равный числу независимых множеств в рёберном графе графа G, упоминается как индекс Хойозы [29]. Ниже приводится краткий обзор работ по перечислению независимых множеств.

Используемая далее терминология в целом согласуется с книгой [13]. Далее рассматриваются только простые неориентированные графы. Подмножество попарно не смежных вершин графа называется независимым. Под максимальными независимыми множествами (м.н. м.) будем понимать максимальные по включению независимые множества. Максимальный размер независимого множества в графе называется числом независимости графа. Будем обозначать через a(G) число независимости графа G, а через n(G) — число вершин в G. Через i(G) и Im{G) будем обозначать число независимых множеств и число м. н. м. в G соответственно. Запись G' ~ G" означает, что графы G' и G" изоморфны.

Одними из первых работ в области перечисления независимых множеств являются статьи [35] и [36], в которых независимо был доказан следующий факт.

Теорема 1 (Р.Е. Миллер, Д.Е. Маллер [35] и Дж.У. Мун, J1. Мозер [36]). Пусть G — граф на п вершинах, имеющий максимальное число м. н. м. среди всех п-вершинных графов. Тогда G является объединением п/3 копий графа Кз при п = 0 (mod3); объединением графа Кч и (п — 2)/3 копий при п = 2 (mod 3), объединением (п—4) копий графа и либо графа К4, либо двух графов Кч при п = 1 (mod 3).

Экстремальные графы в теореме 1 являются частным случаем графов UKnta, определяемых следующим образом: UKn a суть объединение (а • (\п/аJ -}-1) — п) клик размера [п/аJ и (п — а ■ \п/ос\) клик размера \п/а1. Можно проверить, что n(UKlha) = n, a{UKna) = а.

Теорема 1 обобщалась в различных направлениях несколькими авторами. Так, например, К. Кройтору [25] рассматривал задачу оценки сверху числа м. н. м. в классе всех графов с заданным числом независимости. Дж. М. Нильсен [37] получила достижимую верхнюю оценку числа м. н. м. заданного размера в графах. В обеих указанных задачах максимум достигается на графе UKn>a. Подобные оценки используются для получения оценок времени работы алгоритмов раскраски графов и определения мощности максимального независимого множества (см., например, [26, 37]). Это обеспечивается существованием алгоритмов, перебирающих все м. н. м. в графе за время, пропорциональное количеству м.н. м., умноженному на полином от числа вершин графа [31, 43].

Интерес представляет также получение оценок числа м. н. м. в классах графов, описанных в терминах запрещённых подграфов. М. Гуйтером и Ж. Тузой [30] была получена оценка числа м. н. м. в графах без треугольников (то есть в графах, не содержащих в качестве подграфа). В работе В.Е. Алексеева [1] исследовалось число м.н.м. в графах, не содержащих «большого» паросочетания (объединения графов К2) в качестве порождённого подграфа.

Большое внимание уделяется получению оценок числа независимых множеств в графах с небольшим числом циклов, в первую очередь, деревьев. В работе [40] Г. Продингера и Р. Ф. Тичи были получены верхние и нижние оценки числа независимых множеств в деревьях с заданным числом вершин. Через фп обозначим (п + 2)-ое число Фибоначчи (ф0 = 1, = 2, фп = фп-1 + фп-2 при п ^ 2).

Теорема 2 (Г. Продингер, Р. Тичи [40]). Пусть Т — дерево на п вершинах. Тогда фп ^ г(Т) < 2п~1 + 1, причём равенство ь{Т) = фп имеет, место только в случае, если Т является простой цепью, а равенство г(Т) = 2п~1 + 1 лишь в случае когда Т —звезда.

В той же статье было найдено число независимых множеств в цикле на п вершинах. По-видимому, со статьи Продингера и Тичи берёт начало использование термина «число Фибоначчи графа» в качестве синонима для числа независимых множеств. В работе С. Лин и Ч. Лин [33] были охарактеризованы деревья, число независимых множеств в которых отличается не более чем на 7 от максимально возможного 2П~1 + 1.

В статье Г. С. Вильфа [44] была получена верхняя оценка числа максимальных независимых множеств в деревьях с заданным числом вершин:

Теорема 3 (Г. С. Вильф [44]). Для любого дерева Т на п вершинах выполнены неравенства гм(Т) < при нечётных п, и гм{Т) < 1 + 2(п~2)/2 при чётных п.

Оригинальное доказательство теоремы 3 основывалось на свойствах разбиений натуральных чисел. Б.Е. Саган в работе [41], используя теоретико-графовые рассуждения, упростил доказательство теоремы 3 и полностью охарактеризовал деревья, на которых достигается верхняя оценка. В статье [44] был поставлен вопрос о числе м. н. м. в связных графах с заданным числом вершин. Ответ на него был получен в [28]. В работе [42] теоремы Вильфа и Муна-Мозера одновременно обобщались за счёт рассмотрения класса связных графов с заданным числом циклов. Для каждых фиксированных п и г в [42] были указаны графы, на которых достигается максимум числа м. н. м. в классе всех связных n-вершинных графов с г циклами.

Для дальнейшего изложения введём несколько определений. Пусть U = {ui, ., 1}, V = {г»1, ., Vp}, W = {tyi, ., wq}. Обозначим через Bd,p,q дерево на множестве вершин U U V U W, такое, что его поддеревья, порождённые множествами {щ} U У, {u(i-\} UWwU представляют собой соответственно звёзды Ki,p, К\л и цепь P(i-1 • Отметим, что -В^дд есть просто цепь длины d. П. Д. Вестергардом и А. С. Педерсеном была получена следующая верхняя оценка числа независимых множеств в деревьях заданного диаметра:

Теорема (П. Д. Вестергард, А. С. Педерсен [39]). Для любого п-вершинного дерева Т диаметра d выполнено неравенство i(T) ^ i{Bd,n-d,\), обращающееся в равенство только при Т ~ Bd,n-d, 1 •

В той же работе [39] был поставлен вопрос о нижних оценках числа независимых множеств в деревьях заданного диаметра. Для деревьев диаметра 4 исчерпывающий ответ был дан в работе [27] (формулировка теоремы приведена в разд. 1.1). Также в работе [27] была описана структура экстремальных деревьев диаметра 5 для достаточно больших п. Проблема Вестергарда (полное описание экстремальных деревьев при произвольном заданном числе вершин и диаметре) до сих пор не решена в общем случае.

Важным направлением является получение асимптотических оценок числа независимых множеств в параметрических классах графов. К таковым относятся диаграммы Хассе частично упорядоченных множеств, плоские прямоугольные решётки и др. В работе [14] А. Д. Коршуновым и А. А. Сапоженко была получена асимптотика числа независимых множеств в графе n-мерного булева куба (в оригинале результат сформулирован в терминах числа двоичных кодов с расстоянием 2).

Теорема (А. Д. Коршунов, А. А. Сапоженко [14]). Для графа п-мерного булева куба Вп справедлива асимптотика i(Bn) ~ 2л/ё22"-1.

Для числа независимых множеств в полных бинарных деревьев с п ярусами рёбер В. П. Ворониным и Е. В. Демаковой получен следующий результат.

Теорема 4 (В. П. Воронин, Е. В. Демакова [2]). Обозначим через i,n число независимых множеств в полном бинарном дереве, имеющем к ярусов рёбер. Существуют, константы (3 и у такие, что при п —> оо справедлива асимптотика л 2" ~ Р ■ 7 •

Активно также исследовался вопрос асимптотики числа независимых множеств в плоских прямоугольных решётках — графах Гт)7г, определяемых соотношениями ^(Гт;П) = {1,., т} х {1,., п} и

Я(гт,п) = {{(«ь л), foih)} ■ In - Ц + |ii - h\ = l}.

Из многих работ на эту тему упомянем статью Г. С. Вильфа и Н. Кал-кина [23], характерную применением метода трансфер-матриц, в которой доказана следующая

Теорема (Г. С. Вильф, Н. Калкин [23]). Существует двойной предел при т., п —¥ оо i(rm,n)™ 77, где 1.503 < г) < 1.5035.

Значительный интерес представляют оценки числа независимых множеств в регулярных и «почти регулярных» графах (то есть графах, в которых степени вершин либо попарно равны, либо лежат в сравнительно узком диапазоне). К задачам такого рода сводятся некоторые перечислительные проблемы теории чисел и теории групп. Например, перечисление множеств, свободных от сумм (МСС), в абелевых группах (то есть множеств А, таких, что А П {а + b | а, Ъ е А} = 0) сводится к перечислению независимых множеств в графах Кэли. Этот подход был применён Н. Ало-ном в [21] для получения асимптотики логарифма числа МСС в отрезке натуральных чисел. Позже, также с применением теории графов, А. А. Са-поженко [17] получил асимптотику числа МСС в отрезке натуральных чисел. Рабочим инструментом в статье [21] была следующая оценка для числа независимых множеств в регулярных графах.

Теорема (Н. Алон [21]). Для любого к -регулярного графа G на п вершинах число независимых множеств i{G) удовлетворяет неравенству i(G) < (1) где f(k) = О(к~01).

В доказательстве приведённой теоремы подсчёт числа независимых множеств в регулярных графах был сведён к подсчёту числа независимых множеств в почти регулярных двудольных графах. Такую возможность обеспечивала следующая лемма.

Лемма 1 (Н.Алон [21]). Для всякого k-регулярного п-вершинного графа существует остовный двудольный подграф, степени вершин которого лежат в интервале k/2 — 2y/k log2 к, к/2 + 2^/к \og2k .

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

А. А. Сапоженко предложил более простое доказательство оценки (1), улучшив, кроме того, остаточный член до f(k) — 0(Vk~l In к) и распространив оценку на квазирегулярные графы [16].

В работе [21] высказано следующее

Предположение (Н. Алон [21]). Наибольшим числом независимых множеств среди к-регулярных графов на п вершинах при 2к \ п обладает единственный с точностью до изоморфизма граф, представляющий собой объединение ^ непересекающихся полных двудольных графов.

Граф из формулировки гипотезы будем называть далее графом Алона.

Рис. 1. Граф Алона

Эта гипотеза остается недоказанной до сих пор (апрель 2009), хотя большинство исследователей не сомневаются в ее справедливости. Справедливость этой гипотезы означала бы в частности, что в (1) имеет место оценка f(k) = 0(k~1).

С помощью теоретико-информационного подхода Дж. Каном и А. Лоренцем в статье [32] была получена достижимая верхняя оценка числа независимых множеств в двудольных регулярных графах, что косвенно подтверждает гипотезу Алона.

Теорема 5 (Дж. Кан, А.Лоренц [32]). Пусть G — двудольный к-регулярный граф на п вершинах. Тогда i(G) ^ (2fc+1 - 1)2.

Отметим, что вопрос о единственности экстремального графа в теореме 5 до сих пор остаётся открытым.

Интересен вопрос о числе независимых множеств в графах, для которых известен размер наибольшего независимого множества. Это связано с довольно общим подходом в перечислительной комбинаторике, который может быть назван методом контейнеров [20]. Метод состоит в следующем. Пусть А и В — семейства подмножеств некоторого множества. Скажем, что семейство В является системой контейнеров для А, если для каждого A G А найдётся В € В, такое, что А С В. Тогда, очевидно, выполнено неравенство

Грубые на первый взгляд, такие оценки при подходящем выборе системы В позволяют получать асимптотику. Таким способом, например, А. А. Сапоженко получил решение проблемы Камерона-Эрдёша [17]. Вопрос о применимости метода контейнеров для задачи оценки числа независимых множеств в графах тесно связан с указанной выше задачей перечисления независимых множеств в графах с фиксированным числом независимости, поскольку семейство всех м. н. м. графа является системой контейнеров для семейства всех независимых множеств, и число независимости графа является прямым ограничением размера таких контейнеров.

В статье [1] была доказана следующая

Теорема 6 (В.Е. Алексеев [1]). Для любого графа G выполнено неравенство где п = n{G), а = a{G).

Неравенство (2) было использовано в [1] для оценки числа м. н. м. в графах, а в работе [18] — для получения верхних оценок числа независимых множеств в квазирегулярных графах с ограничением на число независимовев

2) сти и расширителях. Достижимая нижняя оценка числа независимых множеств в графах с фиксированным числом независимости получена в [38].

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

Диссертация состоит из трёх глав.

Первая глава посвящена оценкам числа независимых множеств в деревьях фиксированного диаметра. В разделе 1.1 вводится ключевое понятие ёмкости графа и даётся несколько других определений, доказываются встомогательные утверждения. В разделе 1.2 доказываются нижние оценки числа независимых множеств в деревьях диаметра 6,7,8,9. В частности, доказываются следующие теоремы:

Теорема (разд. 1.2, теоремы 8, 9). Любое дерево диаметра 6 на п вершинах содержит не меньше независимых множеств. Любое дерево диаметра 7 на п вершинах содержит не меньше

35(п-2)/7 независимых множеств. Любое дерево диаметра 8 на п вершинах содерэ/сит не меньше независимых множеств. Любое дерево диаметра 9 на п вершинах содержит не меньше независимых множеств.

В разделе 1.3 доказываются теоремы, характеризующие структуру экстремальных деревьев в проблеме Вестергарда. Дерево Т называется (n, d)-минимальным, если оно имеет наименьшее число независимых множеств среди всех деревьев диаметра dna,n вершинах. Через Ft будем обозначать лес, полученный из дерева Т удалением всех центральных вершин.

Теорема (разд. 1.3, теорема 10). Для произвольного фиксированного d существует конечное множество деревьев Add со следующим свойством. Для любого п и любого (n, d) -минимального дерева Т каждая из компонент леса Ft изоморфна некоторому дереву из М.&.

Через Т' обозначим такое дерево, что лес FT> является паросочетанием на шести вершинах. Пусть Т" означает дерево диаметра 6, такое, что лес Ft» является объединением четырёх пятивершинных цепей.

Теорема (разд. 1.3, следствие из теоремы 12). При d £ {6,7} и при всех достаточно больших п вида 7к + d — 5, к £ N, для любого (n,d)~ минималъного дерева Т все компоненты леса Ft изоморфны дереву Т'. При d е {8,9} и при всех достаточно больших п вида 21k-\-d—7, k EN, для любого (п, d) -минимального дерева Т все компоненты леса Ft изоморфны дереву Т".

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

В разделе 1.5 получено обобщение теоремы Воронина-Демаковой на случай g-арных деревьев при произвольном q. Обозначим через k число независимых множеств в полном g-арном дереве, имеющем к ярусов рёбер, или, что то же, диаметр 2к. Доказана следующая

Теорема (разд. 1.5, теорема 15). При q е {2,3,4} для Lq>k справедлива асимптотика при к оо:

Pq'lf > для некоторых констант f3q и jq.

При q > 5 справедлива асимптотика при к —> оо:

2к lq,2k ~ aq>0 ■ % , 02fc+l l>q,2k+l ~ aq,l'7q где константы aqfi и aqд удовлетворяют неравенству ск9;о > &q,i ■

Заслуживает внимания различный характер асимптотики величины iqj /с при q < 4 и q ^ 5.

Результаты первой главы опубликованы в [4, 8].

Вторая глава диссертации посвящена оценкам числа максимальных независимых множеств в графах заданного диаметра. В разделе 2.1 вводятся основные определения и доказываются некоторые вспомогательные утверждения. В разделе 2.2 получено полное описание графов с заданным диаметром, на которых достигается минимум числа м. н. м. Определим последовательность фп соотношением фп — Фп-2 + Фп-ъ и начальными условиями фо = ф\ = 1, Ф2 — 2.

Теорема (разд. 2.2, теорема 16). Для любого d, d ^ 4, и для любого графа G диаметра d выполнено неравенство im{G) ^ Фа+i ■ Если Im{G) = фл+1, то множество V{G) можно разбить на подмноэ/сества Vo, ., V,d, так, что при любом к, 2 ^ к ^ d, и любом г, 0 ^ г ^ d — k, в G отсутствуют рёбра между вершинами из V} и V^, и для всякого г, 0 ^ г ^ d — 1, подграф графа G, порождённый множеством Vi U Vi+1, является полным двудольным с долями Vi и Vi+i.

В разделе 2.3 приводится полное описание деревьев с заданным диаметром и числом вершин, на которых достигается минимум числа м. н. м. Тем самым получено существенное обобщение теорем Вильфа [44] и Сагана [41]:

Теорема (разд. 2.3, теорема 17). Для любого п-вершинного дерева Т диаметра d выполнено неравенство гм(Т) ^ M(n,d), где

При d ^ 9 существует единственное с точностью до изоморфизма дерево, на котором достигается указанная оценка (полное описание экстремальных деревьев при всех d см. в разд. 2.3).

Ф<1—1 + (2(^+1)/2 - 1)^.

2) при d ^ 4, п — d = 2k + 1, k > О, при d ^ 4, п — d — 2, при d ^ 5, d ф 7, п — d = 2k ^ 4, при d е {4, 7}, п - d = 2k ^ 4.

M(n,d) = <

Фй—2 + Фа,

2(n-d)/2фйъ

Результаты второй главы опубликованы в [9, 10, 11, 12]. В третьей главе диссертации исследуется число независимых множеств в графах с заданным размером максимального независимого множества. Неравенство (2) обращается в равенство при а\п (максимум числа независимых множеств достигается на графе UKn>a). Доказываемая в разделе 3.1 теорема 18 даст уточнение оценки (2), делающее её достижимой при всех возможных сочетаниях параметров п, а, а также описывает экстремальные графы.

Теорема (разд. 3.1, теорема 18). Для любого графа G, такого, что n(G) = — пи a(G) — а, выполнено неравенство i{G) ^ i(UKnia), обращающееся в равенство только на графах, изоморфных UКПА.

В разделе 3.2 получены оценки числа независимых множеств в деревьях и лесах с заданным числом независимости.

Теорема (разд. 3.2, теоремы 19). Для любых n, a (n ^ 2) среди всех деревьев на п вершинах с числом независимости а максимальное число независимых множеств имеют только деревья, изоморфные дереву, полученному из звезды Ki>a подразбиением (п — а — 1) рёбер.

Теорема (разд. 3.2, теорема 20). Среди всех лесов на п вершинах без изолированных вершин с числом независимости а максимум числа независимых множеств достигается только на лесах, являющихся объединением паросочетания на 2(п — а — 1) вершинах и звезды Ki^a-n+i ■

Раздел 3.3 посвящён оценкам числа независимых множеств в регулярных л-вершинных графах, число независимости в которых близко к п/2 (то есть к максимально возможному).

Теорема (разд. 3.3, теорема 22). Для сколь угодно больших К и N существуют к-регулярный п-вершинный граф G, такой, что к > К, п > N, и

Т) a(G) <-(l -Щк-1)),

71 logS{G)) >-(l + 0(fc"1)). С другой стороны, для любой константы в е (0, 1/2) для любого к-регулярного п-вершинного графа G, такого, что &{G) < |(1 — Q(k~0)), выполнено неравенство log2(i(G))<^(l-fl(*Te)).

В разделе 3.4 доказывается обобщение теоремы 5 на квазирегулярные двудольные графы:

Теорема (разд. 3.4, теорема 23). Пусть G — двудольный граф с долями А и В. Пусть степени вершин из А ограничены сверху числом к2, а степени вершин из В ограничены снизу числом к\. Тогда

Результаты третьей главы опубликованы в [3, 5, 6, 7].

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

1. Для произвольного d описана структура (п, d)-минимальных деревьев (теоремы 10,11, 12). Как следствие, получены асимптотически достижимые нижние оценки числа независимых множеств в деревьях диаметра 6, 7, 8, 9 (теоремы 8, 9, 13).

2. Получена достижимая нижняя оценка числа максимальных независимых множеств в графах фиксированного диаметра, приведено полное описание экстремальных графов (теорема 16). Получена достижимая верхняя оценка числа максимальных независимых множеств в деревьях фиксированного диаметра, приведено полное описание экстремальных деревьев (теорема 17).

3. Получена достижимая верхняя оценка числа независимых множеств в графах с заданным числом независимости, полностью описаны графы, на которых эта оценка достигается (теорема 18).

4. Получены оценки числа независимых множеств в регулярных графах с числом независимости, близким к максимальному (теорема 22).

1. Алексеев В. Е. Верхняя оценка числа максимальных независимых множеств графа // Дискретная математика. 2007. Т. 19. Вып. 3. С. 84-88.

2. Воронин В. П., Демакова Е. В. О числе независимых множеств для некоторых семейств графов // Труды IV Международной конференции «Дискретные модели в теории управляющих систем», Краснови-дово, 19-25 июня 2000 г., М.: МАКСПресс, 2000. С. 145-149.

3. Дайняк А. Б. О числе независимых множеств в графах с фиксированным числом независимости // Дискретная математика. 2007. Т. 19. Вып. 2. С. 63-66.

4. Дайняк А.Б. Уточнение оценки В.Е.Алексеева числа независимых множеств в графах // Проблемы теоретической кибернетики. Тезисыдокладов XV международной конференции (Казань, 2—7 июня 2008) / Под ред. Ю. И. Журавлёва Казань: Отечество, 2008. С. 25.

5. Дайняк А. Б. Оценки числа независимых множеств в графах с фиксированным числом независимости // Вестник Московского университета, сер. 15. Вычислительная математика и кибернетика. 2009. №2. С. 45-48.

6. Дайняк А. Б. О числе независимых множеств в деревьях фиксированного диаметра // Дискретный анализ и исследование операций. 2009. Т. 16. №2. С. 61-73.

7. Dainiak А. В. Sharp bounds for the number of maximal independent sets in trees of fixed diameter // arXiv:0812.4948vl. 12 pp.

8. Дистель P. Теория графов (пер. с англ.). Новосибирск: Изд-во ИМ СО РАН, 2002. 336 с.

9. Коршунов А. Д., Сапоженко А. А. О числе двоичных кодов с расстоянием 2 // Проблемы кибернетики. Вып 40. М.: Наука, 1983. С. 111-130.

10. Прасолов В. В. Многочлены. 3-е изд. М.: МЦНМО, 2003. 336 с.

11. Сапоженко А. А. О числе независимых множеств в расширителях // Дискретная математика. 2001. Т. 13. № 1. С. 56-62.

12. Сапоженко А. А. Доказательство гипотезы Камерона-Эрдеша о числе множеств, свободных от сумм // Математические вопросы кибернетики. Вып. 12. М.:Физматлит. 2003. С. 5-14.

13. Сапоженко А. А. О числе независимых множеств в графах // Вестник Московского университета, сер. 1, Математика, Механика. 2007. №3. С. 33-37.

14. Сапоженко А. А. Проблема Дедекинда и метод граничных функционалов // Математические вопросы кибернетики. Вып. 9. — М.: Наука, 2000. С. 161-220.

15. Сапоженко А. А. О методе контейнеров // Дискретная математика и её приложения. Сборник лекций молодёжных научных школ. Выпуск IV. / Под ред. А. В. Чашкина. М.: ИПМ им. М. В. Келдыша РАН, 2007. С. 11-25.

16. Alon N. Independent sets in regular graphs and sum-free subsets of finite groups // Israel J. Math. 1991. 2(73). P. 247-256.

17. Alon N., Spenser J. H. The Probabilistic Method. Third edition. Wiley-Interscience, 2008. 352 pp. (Русский перевод: Алон H., Спенсер Дж. Вероятностный метод. Пер. 2-го англ. изд. — М.: БИНОМ. Лаборатория знаний, 2007. 320 с.)

18. Calkin N., Wilf H.S. The number of independent sets in a grid graph // SIAM J. Discr. Math. 1998. 11. P. 54-60.

19. Chung F., Frank P., Graham R., Shearer J. Some intersection theorems for ordered sets and graphs // J. Comb. Th. Ser. A. 1986. 43. P. 23—37.

20. Croitoru C. On stables in graphs // Proc. Third Coll. Operations Research, Babes-Bolyai University, Cluj-Napoca, Romania. 1979. P. 55-60.

21. Eppstein D. Small maximal independent sets and faster exact graph coloring // J. Graph Algorithms and Applications (special issue for WADS'01) 2003. 7(2). P. 131-140.

22. Griggs J.R., Grinstead С. M., Guichard D.R. The number of maximal independent sets in a connected graph // Discrete Math. 1988. 68. P. 211220.

23. Hoyosa H. Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons //Bull. Chem. Soc. Jpn. 1971. 44. P. 2332-2339.

24. Hujter M., Tuza Z. The number of maximal independent sets in triangle-free graphs // SIAM J. Discr. Math. 1993. 6(2). P. 284-288.

25. Johnson D.S., Yannakakis M., Papadimitriou С. H. On generating all maximal independent sets // Information Processing Letters. 1988. 27(3). P. 119-123.

26. Kahn J., Lawrenz A. Generalized rank functions and an entropy argument // J. Comb. Th. Ser. A. 1999. 87. P. 398-403.

27. Lin S., Lin Ch. Trees and forests with large and small independent indices // Chinese J. Math. 1995. 23(3). P. 199—210.

28. Merrifield R. E., Simmons H. E. Topological methods in chemistry, New York, John Wiley к Sons, 1989.

29. Miller R. E., Muller D.E. The problem of maximum consistent subsets — IBM Research Report RC-240. 1960. J.T.Watson Research Center, Yorktown Heights, N.Y.

30. Moon J.W., Moser L. On cliques in graphs // Israel J. Math. 1965. 3. P. 23-28.

31. Nielsen J. M. On the number of maximal independent sets in a graph. Preprint. Research Series RS-02-15, BRICS. Aarhus, Denmark: University of Aarhus, Department of Computer Science, 2002. Юр.

32. Pedersen A. S-, Vestergaard P. D. Bounds on the number of vertex independent sets in a graph // Taiwanese J. Math. 2006. 6(10). P. 15751587.

33. Pedersen A. S., Vestergaard P. D. An upper bound on the number of independent sets in a tree // Ars Combinatoria. 2007. 84. P. 85—96.

34. Prodinger H., Tichy R. F., Fibonacci numbers of graphs // Fibonacci Quart. 1982. 20(1). P. 16—21.

35. Sagan В. Б. A note on independent sets in trees // SIAM J. Discr. Math. 1988. 1. P. 105-108.

36. Sagan В. E., Ying G. Ch., Meng К. K., Vatter V. Maximal independent sets in graphs with at most r cycles //J. Graph Th. 2006. 53. P. 270-282

37. Tsukigama S., Ide M., Ariochi H., Ozaki H. A new algorithm for generating all the maximal independent sets // SIAM J. Comput,. 1977. 3(6). P. 505517.

38. Wilf H. S. The number of maximal independent sets in a tree // SIAM J. Alg. Discr. Methods 1986. 7. P. 125-130.