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

АКАДЕМИЯ НАУК С и О : (ШИРОКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ -

Р

. На .разах рукописи КОСТОЧКА Ахоксандр Васильевич

УДК 519.17

ЖЬ'ЖЗОВАНИБ КОНСТРУКТИВНОГО И МСШНОСТНОГО ПОДХОДОВ ПРИ РЕЕЕНШ ЗКИРИШЫШХ ЗАД., л НА ГРАФАХ

01.С 09 - катематичесгаш кибернетика

Автореферат

диссертация на соискание „ ^еяой стеяэхп: доктора ^азиио-ьатемаигаеских наук

Новссибпрзк -

1990

Р^.ога выполнена в Ицсти./те математики СО АН СССР

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

профессор Леонтьев В.К.

доктор физико-математических наук, профессор, Мазуров Г .Д.

доктор физ^о-математических наук, профессор Тышкевич Р.И.

Ведущая организация: Московский Государси .шый университет

им/М.В.Лшоносова

Защита состоится _"______ 1990 г. в часов

на засе; :сш специализированного совета ДО02.23.01 при Институте математики СО АН СССР (630090, Новосибирск, 90, Университетский проспект, 4). ч

С диссертацией можно ознакомиться в библиотеке ' Института математики СО АН СССР.

Автореферат разослан "_ "_ 1990 г.

тчсхшй секретарь л^цяализированного .овета дав .23.01

доктор (1яз"".о-г.1атег.г тгсеских наук Е.А.Палютин

СВДАЯ ХАРАКТЕКЮТт РАБОТЫ

Актуальность теш, Экстремальны« задачи на графах, .г ■>. задачи определения наибольших и нага,, .ышс значений функций он графов, принадлежащее заданны;,? кассам, всзшнсапт как в с£ к разных прикладных работах по ян^матике, гак* -^нетике, технике, .химии, электронике, так и в различных областях математики: алгебре» теории вероятностей, топологии. Иаховденке этих экстре- ' мумов тесно связано с вопросами эффективной вычислгагасти соответствующих функций от графов. Известно, что задачи вичисл»ния многих таких функций являются ДОР-груднши. Но не всегда -ре-бувтся точные решения» Часто достаточно уметь тивно находить приближенные решения с гарантированныш сценками точности [4]. Построение таких алгоритмов нех одко удается осущестшть, исходя из конструктивных решений соответствующих, экстретлымх задач на подходящих классах графов. На: - мер, из дэказатель< -ва теореш Визинга о раскраске ребер графа можно извлек-, поли- . нок 1ьтй алгоритм раскраски ребер в число цветов, отличавде- , ! вся от оптимального.не более чем на единицу, В то же время , отыскание раскраски ребер графа в оэтгшаяьиое число ц^-та яв- Л лается /^Р-трудноГ задачей* .-

Традиционным способом подтверждения качества оценок или .функций от графов является построение экстремаль^-.. ила блта-кпх к таковым конструкций. Сйнако в ряде задач г^строониэ или доказательство свойств этих конструкций дредстаьдявт большие ' трудности или невозможно из-за их н, 1зхулярной структуры. Б : этой ситуацж иногда может помочь идея принципа Дирихле. Так, Шеннон в своей знаглег'-ой работе |*2Э} предложил метод построения контактных схем д-ш реализации булевых функций и показал, что существует "мало" такйх булаиос фунгащй от и переменных, для реализации которнхесть схеян, существенно лучшие,, чем со лученные этим методом. Отсюда следует0 чго существуют "плохие" булевы функции Конструктивное же построение последовательно- ' стей ^плохих" функций остается проблемой до сих йор.

Такое сочетание - конструктивные оценки и доказательства существования "плохих" прк ров из мощносуных соображений -оказалось плодотворным, В задачах о сложности реализаций булевых функций его последовательно применяют О.Б.Лупанов, С,В»Яб-

лоньлий и. их ученики, в э. ^тремалышх комбинаторных задачах -П.Эрдэ"', Б.Боллобаш, Да.Спенсер и другие.

Цаль работы. В диссертации сочетание конструктивного и копшостного подходов применяется для исследования оценок хро-шти^сного ч юла грсЛов через плотность и обхват, оценок чис-. да Хадвигера графов и задач ой окрестностям тюдхрафов графа И -мери—ч) куба.

На.учная новизна. В диссертации разработаны некоторые ог'-гинальние конст}* ч.ивные способы и последовательно применяются ; коцностные и.пеи для решения экстремальна за1" ч на графах.

Так, в а лаве I дан метод изменения вкладов вершин ^-мер-,ного куба, о помощью которого получены верхние оценки мощности ; 'Для окрестностей фильтров (т.е. множеств единиц какой-нибудь. , монотонной булевой функцда) и шгшепей б и-мерном кубе.. Для нижней с чки наибольшей мощности окрестности фильтра приведены мощноотные архуыенты, которые зат-зм использовались в работах Фюреди, Кана и Клейтмана [23] и ^ухрова {'

Основнь резу. ?атом гаавн 2 является теорем? 2.1, в кс-рой для близких к однородным графов дана верхняя оценка чис-; да связных подграфов, имеющих "малую" реС ,;ную окрестность. Как следствия из нее получены результаты о компонентах связно- ■ сти и паросочетакиях в случайных сстовных подграфах разрежен-.ззых графов. В частности, доказано усиление предположения Вебе-ра о совершенна ; паросочетаниях в случайных остовных подграфах £рафа п-мерного куба. .

В главе 3 получены новые оценки хроматического числа градов через плотность или обхват. Из них следует отметить улучшение старой (1959 г.) оценки Эрдёша ГТ7] для максимума хроматического числа п-вершинных графов заданного обхвата, асимп-тоттесг- точную верхнш оцен*. г хроматического числа дополнений гшфоз хорд чзрез мааяиос*ь и. описание креитичесг-х относительна к-выроаденности графов, не раскрашиваемых в к цветов.

Основными результатами главы 4 "влйэтся нахождение порядка минимума числа Хадвигат для графов с данной средней стернью и доказательство с„чествования в "плотных" графах малых ч-подграфов о заданным числом Хадшгера, откуда следует предг--дожение Эрл^ша Ц969 г.) о существо ваш: в таких графах малых ч репдсских:< '

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

Апробация. Результаты диссергают докладывались на У (Новосибирск, 1980), УП (Иркутскс 1985} УШ (Горький, 1988) Всесоюзных конференциях по проблемам теоретической кгбернет. л, I, П и Ш Всесоюзных семинарах до дискретной матема""ке и её приложениям ('Москва, 1984, 1987, 1990), третьем и четвертом Международных семинарах по случайнг графам и вероятностям методам в комбинаторике (Познань, 1987, 1989), Международных конференциях "Теория графов" (Оберволъф . . ФРГ, 1986, 1988" четвертом Всесоюзном совещанл! по методам и программам решения опт1*"'тзацио;шшс задач на графах и сетях (Новосибирск, - J39), Первом Всемирном конгрессе общества математической статистики и теории вероятностей га,и Борнулли (Ташкент, 1986), Конференции по теории графо? (Айба, ГДР. 1984), Всесоюзной конвенции по прикладной логик^ (НовЬсибир..;, 1985)„ Всесоюзной школе по георйй графов и ее приложениям ^Новосибирск* 1986) в лекциях XXX с сшсгрз. Международного математического центра им. С,Банаха (Варшава» Î987) в а также на научно-исследоват-лских сеи!-карах Института математика СО АН ССГ Математического Института им» ВДоСтеклова, ВЦ АН Армянской ССР„ Московского гос-утшверситета,, Высией Технической Школы Ияьменау (ГДРЬ Рэсток-сксго университета (Г, )„ ' •

" Публикация» Основные результаты диссергациа опубликованы в ¡35-5?]»

Структура и объем работы » Диссертац я изложена на 225 страницах, состоит из введения, четырех глав и снисгл литера-•гуры (184 наименования)» В каздой главе использована своя нумерация параграфов0 утверждений;, лет и формул.

СОДЕИ Ж ДИССЕРТАЦИИ

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

^ главе I изучаются максимумы ^ и ыошнооти ок-

рестностей, соответственно, фщьтро" ы ант.,„пей в к-мерной кубе Q, а также максимум S (») мощности тени антицепи в 13.

Первая из э""'. задач изучалась в связи с работой Деметро-вича и Катоны [I4J о комбинаторных задачах, Е^-ншсащих при анс ;зе реляц шхых баз данных. Ошпалссь, что SJ<m R(ht)1

Порядок роста величины 'I найден в диссертации с по-

мощью следующих двух утверждений,

тесг-п и. а.1"1 - W *(у?■•> аи'} ,

... Теорема 1.2. яГ- азУЧоДО 2* ,

Теорема I.I доказана при помощи ■ощностнь.. аргументов, а для доказател ;тва '. ;ре.чы 1.2 построен метод измег :!ия вкла-,t,. .. Кцеи^обоих доказательств пригодились также для изучения вй-тачки §(И> к $У\) ,

В связи с заданием монотонных булевых функций при помощи по BOSMOKHOCTJX малого числа линейных неравенств "Зуевым [5] бил поставлен вопрос, является ли 5(*•'•) величиной порядка йЛЛ'ЙГ"? Оказалось, нет. .„лжше Коспанова [?], затем Кана, Клейтшна н <йоредк [23] и, наконец, Чухрова [8] нижняя оценка для SCvs) доведена до (0,7 + 2,'" . Кап, Клейтыан и ©среди {^выдвинули предположение, что теы не менее

К S'm) f' < i

Ц-У Г—>

. В диссертац.^ с использованием вышеупомянутого м тода из- ' ызненил вкладов доказаны несколько более сильные, чем вто "редполонение» утверждения.

Теорема 1.3. Для любг4> антицепи $ в 0 мощность ее те-r °bS не превосхох ^/ззд* oCfi)

Теорема 1.1, Мощность окрестности любой антицепи в 6 в превосходят (^ЗШ

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

■ е ; ■'■' *

n-однородннх графах, а такяе приложениям этих оценок к анализу случайна остовш:х подграфов таких графов. лсл'-зш, »"-о случайным остовным подграфом графа & « (У.Е > назттзае^ся такая случайная величина, значешшмг' которой язллигся схл'О ¿о подграфы графа , для каддого ребра а «Ê

P(eaEt<&f)}ep t

я для события и неза-

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

полных двудольных графов При этом, естественно, ис-

пользуется простая структура этих градов, Однако во кногпх задачах, в частности, задачах анализа надёжности се й, требуется исследовать случайные сстовнне ~дгрзфн графов, довольно далеких от полных,, Так, в ряде рабо* изучаются случайные основные подграфа графа w-мерного куба Q в связи с исслоло-ванностьи его свойств и разнообразием .. .глояенийо При этом л работах Буртина [2]„ Зрдёаа и Спенсера [22]0 Взбёра [3' Еол-лос .a [l05 II] а других основная трудность как раз п заключа-лас s в нахождении удовлетворительной верхней оценки для числа связных подграфов гвафа Q", иглещих "малую" реберную • крест-

еость,

Итак, центральным результатом глави 2 являет^" Террпма 2.1, Пусть Cie(v,£) - графв степени ¿аддоЗ jop-шины которого ке меньше И-2 и не больше м Пусть ед". f, i с \ „ Тогда число таких i-элементных А«¥ , что

п С(А} « связный " дграф,, ш превосходит МСто!'.))^^1^''" , .

Здесь и далее выражение E^l^Y) обозначает цножество ребер кулъгигра^л G, один конец которых принадлежит X „ а другой - Y ; выражение ) - подграф мулвгиграфа Q, порожденный множеством вершин â » Для оценку можно еще усилить.

Теорема 2.2„ Пусть г граф -мерного куба

и I « j <$ « Тогда число I -алементкых

•таких, что

- с

(1+ о(д5) е

и 9 ' ^Л) - связный подграф, не превосходит

0,4 ,

При ^ - ^ 1 порядок логаргфи донки в теореме 2.2 не., ^ читаем. От лил, что при д .сазательстве теорем 2.1 и ¿.2 попользуются 'пк конструктивное перечисление поддеревья, введенное Сапозь. .ко, так и мощностные соображения.

После ,т. 'газательства в параграфе 2.2 те ^ем 2„I и 2.2 в параграфа 2.3 обсуздаются свойства разрешенных мультиграфов, , принадлежащих некоторым семействам. В дальнейшем говорится, что 'последовательность ¿С-: *-однородных муль-

тиграфов состоит из разреженных мультиграфов, еоля

„ V " <■ о (VI ') ,

Одно из опис-чаеюг ?.еыейств, ^ * V <»»*) , строэтс* для

1 ивдугадап. Подсешйсгво (к,««) состоит из мех к-од-

нородных связных графов ка ь-г вершинах, 'каждый из граО-'-ч ■ С « при ^ иМ строится так: берутся два грг>-

фа (¡' и С': ко (Ц**») на непересекающихся ывояеот-

•вах взрпшн, и добавляются ребра какого-нибудь совершенного са-росочетания, кг ое ребро которого соединяет ^(С^} с- ,

Очевидно, при И >, ' грат О," принадлежит ^ „ I \ }\

»• Ледам 2.7, Пусть £ £ , Тохда -

а) С,- ~ у»,-однородный связный граф;

б) МС)1*УЛ ;

в) для любого -злеменгног Л ^У(Сг)

г) при 1 6 £ ^ <з(5' дая каадого ¿ -элементного А о?«;)

У-твергпеше в) '•той леммы обобщает известное иаопериметт, рнчеокое неравенстве Харае: для Я .

Р '

В параграфе 2.4 изучаются паросочетания в случайных ои-товннх подграфах и-однородных двудолышх ^азрежонних муль-тиграфов. Известно [2, 22], что для 0,ь г с ве-

роятностью, на стремящейся к нулю при и <« , есть и: лит-ванныв вершины. Значит, для р»* в с вероятность*), не стремящейся к нулю при V) -+ °о , нет совершенного паросс тания. Вебер ¡32] предположил, ч-. для любого фиксированного р > 0,5 вероятность наличия в Зр совер^.лного паросоче-ташш стремится к I при V» «*> . Следующий результат показывает справедливость предположения Вебера, усиленного в двух направлениях. и и)«

Теорема 2.3. Пусть {й",'£ )]„„^ - последовав .ь-ность двудольных V? -однородных разреженных нуль*- рафов с долями Xй и У*", V* = Х.* и У и и для ¿Vй выполняются условия ,

-И

I) кадкая вершина в и смелиа не менее чем с И - . другими вершинами (напомним, что в мулт~ -райах возможны краше ребра); • и

• ?) для любого с ¿о.уи^!

Предположим, что п г -чдоттелуггь . (Р* ^ц-^ поломи ильных действительных чисе^ такова, ч.

-I)

/ И 00

Обозначим через ЗС« (соответстве: , ) множество тех

-.и г* ГУ»

версии из Xй (соответственно,-"У ), которые не являются изо-

лкроваиными в Ч ри . Тогда с вероятностью &-о(1) в £ есть паросочстание, с ' .еряачее Ьт-си ( ^ р,» \1 } ребер.

Содерглтолько, условие (I) обеспечивает стремление к нулю вероятности появления в "гилки", т.е. двух вершин сте-

пени I, смежных с одной и той же-версии .. Понятно, что н;шь-чле "шлют" с двумя вершинами из ^ ¡>„ означает отсутствие в Ч р„ паросочетанкя, покрывающего у . Значит, для большинства случайных остовных подграфов Ч ^ во шопа последовательностях двудольных с 'ородных мультиграфов отсутст!—я простых препятстшг;: ("вилок") уже достаточно для наличия паро-сочетания, локрыват'. его Уили

Лри любых фиксирована.л. 1с и ь*л любая последовательность (С"}^ /гае О" - двудольный грас^ из ^(Ь.м) для и ^Ц (в частности, последовательность ) вме-

сте с последовательностью . где

' р.л-1-i1. il + (Ьл >гЛ --,

4 ' У^ —>> с» »

удовлетлтзяют требованиям теоремы 2 Т. , у

Слцпствие 2.4. Для любой последовательности я1-5' двудольных И- дородных разреженных мультиграфов, ' удовлетворяющих условиям I) и 2) теоремы 2.3, и любе' такой последовав явности (.рк^к . что - '¡/и

1 ' <ру,*• ш

имеет место неравенство

Р ( имеет совершенное патюсочётан"л)

Р (С* не имеет изолированныхвершин)

Для последовательности , услови (2) эквивалентно

условию р-,л О, £Г , откуда следует предположение Вебера, Прадполокешге Вебера для А независимо от дг сертанта |_4б] дог.:.зьно Болдсбадем [II]. В этой работе тоже основная труд-ьоегь состоит в знке числа связных подграфов 0 , имеющих ■ "1т.лую" реберную окрестность. И оцени:, данной Болл^оашем, недостаточно для доказательства теоремы 2.3 или ее сужения на

Т

В этом не параграфе показано, что пт больших и и о*Д. "ломти все" двудольные И -однородные Ь-вершинные нульти-графы удр-тетзорявт условиям I) и 2) теоремы 2,3.

В параграфе 2,5 обоуэдаются размеры компонент "•зязности сдуча1.._а оотовных подграфов в ^-однородных разреженных псевдографах (в псевдографах, в отлично от графов, допускаются .^тль и кратные ребра). Нетрудно подсчитать, что дли любого фиксированного ' и .^обо^ последовательности Ю и-

оа.дородных разрьженных псевдографов вероятность отсутствия ( ч 4 )-элементных компонент связности ь стремится к

нулю "оо , с-.ж р -^(Л'Т" /и) '(в втом случае

■кг'шая котиунта имеет не о^лее ^ вершин) или

Вебер [зз] показал, что при 6 = QV! условия (3) хс ^ точно, чтобы в С?дочти наверное лда ровно одна (гигантская) компонента, содер:каи:ая более i вершин. Обобщением го-го результата является

Теорема 2.5. Пусть фиксировано нагурал&к* , а [С = (V" Е^)^ость последовательность -.пких ^-однерп^шп? разреженных псевдографов, что для кпддого выполнены

условия и

1) катдая вершила С смеша но менее, чем с и-г , .ругами вершинами; и

2) для литого с 0,5-и а |А| » С * ^ ] V " |

Если для последовательности {ри). положительных чисел справедливо (3), го с вероятность?; 1~о( 1) в есть ров"" одна компонента связности, имеюэдн более 4: верит.

Следствие 2.6. Боли последовательности {Си]и {рнЗГм удовлетворяют условиям теоремы 2.5 для 4 - * и

Юа-р/^и

.то ^(С^ связен) е

При фиксированных к любая такая поел довательно;тъ

{^ЗиТ^ • что ^ * ^ 1 ^ т,тч- 11 ^ » Удовлетворяет

требованиям I) и 2) теоремы 2.5, Соотношение (3) в этем случае принимает вид

2 и

Следствие 2.6 для таких последовательностей обобщает ана-логачний результат Эрдёша и Спенсера [2.., и Еоллобаша fiol для

<Г

' ги

В частности, для случайных остовных подграфов ири шо-

nix и -однородных разреженных псевдографов порог для р*. начиная с которого рп верняк связен, совпадает с порогом, начиная с которого не имеет изолированных вершин.

Известно, что при f н ~ Vw почти наверчое в каж-

дая ко'^онента связности содержит о (2*) вершин. Вебер показал, что при р»^ дочти наверное в есть ровно одна компонента связности с более чем i/pn вершинам . и эта компонента иглеет 2, (<-o(U) вершин. Теорема 2.2 позволяет усилить этот результат. В параграфе 2.6 доказана

Тег^ема 2.7. Пусть ' < р < i . Тогда с вероят- •

ностко 1- 0(1) в Q1! нет I-вершинных компонент овязн • сти для i/p < «. .

Далее показано, что в наибольшей компоне- 'в связности в } ловиях теоремы 2.7 имеется 2/'И - "CD) вершин и приведен (ослабленный) аналог теоремы 2.7 для и -однородных графов. , Результаты параграфов 2.4-2.6 изложены на языке модели^. Но почти все они переносятся на модель w-,.) , в которой рассматриваются все остовнке подграфы С? , содержащие розно W-i ^ ребер, аналогично тому, как это сделано в [46].

В третьей главе изучаются ве'рхк"^ оценки хроматического числа графов зрез отность (т.е. число вершин ттаибольшегз 1. шого подграфа) или обхват (т.е. длину кратчайшего цикла). Понятно, что плотность графа С является оценкой

снизу для его хроматического числа Jf- (£) . Оказалось, что верхней оценки для X(G) в терминах w(C) или даде об-'-хвата С (С ) дать нельзя. Здесь в свое время была продемонстрирована neper живность мощностного подхода. После многочисленных попыток разных авторов построить графы оо^ватов 4, 6, 7, 8 со сколь угодно большим хроматическим числом Эрдёш в .небольшой работе [17] показал, что для любых $ ^ 3 11 ^ "существуют графы обхвата g с хромаг ческиы числом

Однако во многих приложениях возникают графы специфической струг-уры. Например, задаче, определения наименьшего числа отеков, достаточного, чг'обн поручить из заданной перестановки первьь. И натуральных чисел перестановку (1,3.,..., и) , сводится к нахождения хроматического числа построенного по этой перестановке графа, которой всегда, сказывается графа.: пересе-^"чий хорд окружностг графов иа многих интересных в теоретическом или практическом отношении классов удается най-' -ке-гтэнвиадыг'е иерхнип оценки хроматического числа через плотность или т. В ,-^стеосг'-, для целого ряда классов графов • ^ лмеь? слысл изучение

В первом параграфе главы приводятся и осекаются ее результаты. ;

Основной результат параграфа 3.. лени в русле вышеупомянуто:! работы Л.Эрдёша [I?] , где било показано, что наго.тент ->е число вершин в графе об..^ата " хроматическим

числом к растет при !г-5>©® не быстрее, чем к2®*"£ . -г то же время нетрудно убедиться,, ?то к10'*'^1- % . Фак- '

тически был доказан следующий несколько более сильный результат типа теоремы Рамсея.

Теорема (Эрдёш0 [I?]). Пусть - минимум мопи.-^ти

наибольшего независимого множества вершин по всем ^-вершинным графа!.?0 не имеющим циклов длины I или менее. Тогда для любого действительного £ > о и ш л> целого при

«(<*,£)< и

дальнейших продвижений для а этом направлении! не

6Ш10' а (?\

Теорема 3.1. Для любого целого ь^З при

< И .

Одни« из следствий этого утверждения являете;. оценка .

2м к) „ Среди других следствий смети.! улучшение оценки Чааг наименьшего числа двудольных подграфов, достаточного для покрытия ребер любого -вершинного графа и улучшение оценки Дьярфаиа для „ где ТГг - класс графов, не содержащих в "^чесгве порожденного 4-вершинного подграфа два изолпроваюх-^с ребра. ' '

В следующем параграфе сравниваются оценка для I ,5 ) к ^О^к , ■2») , где - класс графой, степень каждой-верши ■ ны которых не превосходит-' к „ а - ",сласс к-вырожденных графов. Напсыним, что граф 0 называется к-выроаденным, если в любом его подграфе найдется вердина» степень которой в €,' меньше Ь . Из определения следует „ что для любого к -вырожденного графа сутцег вует такай нумерация его верпь.а, при которой 'каждая вершина смеяйа менее чем о к вершинами, •имеющими меньшие номера. Отсюда вытекает тривиальный алгоритм

раскрасит любого к-зырозденного графа в не " у;ее чем к. цветов. <" «кем, что граф С является , ^ )~разлояшмым, ,если множество вершин Сг можно так разбить на подоножества Ч, ,.../что является Ц-выроядснннм для любо. го ; { 4 -с . Очевидно, хроматическое число любого разлокявдго графа не превосходит / Поскольку ...и ^ то и - Брукс [13] показал,что (и , к ^ = к при к"^ 3 . Бородин [I] усилил это увер;. • дение, доказав, то для любых натуральных Ц рЦ,,,. , Ь^Д с Ь 2 !< каздый граф £ с X »«(Сг) * Ц является {Ц, (1»г д) -разложимым. В работах ряда специалистов, •в том числе в кандидатской диссертации автор", уточнялись оценки '£{£[, при малых 3.

Теорема 3.6. Пусть для натуральных чисел Ц™^,1: выполняется не$. .енство

Тогда существует а...оритм сложности ■ ?орый стри-

. ¿л ..Дч^) -разложен::® любого и-вершинного графа С с , С Ы (С) ^ глХИ IЦ ,..Ь * К

Е частности, из теоремы 3.6 следует, что'

В связи с вышеизложенным можно было предположить,что значение ^О« , тоже меньше к при малых 6 . Оказалось, что ото не так, Бородин заметил, что ^ 2) = к , Но мок-

но показать и больше.

Теорема 3.7. Дкя любых целых I {■ Ъ } д ъ 3 существует V-выроздг-нщгй граф С обхватом не менее ^ и хрома-

тически;. чкслог к.

ч связи с этими результатами в параграфе 3.4 р сматрива-ется в некотором смысле промежуточный класс почти к-вы-

рождении/. (п, >- в.) графов, т.е. гр 'ов, которые не . являются )с-вцрозденшма, но поел- удаления любого ребра становятся та-овыми. Класс 9\. одержит все связные I- -однородные графы и содержится в . Поскольку, по определению, миокес о

И(С-) вг тин стег -и, большей к, в любом графе С« ^ является наеашеимым/то I олнив Н(С-) до какого-нибудь оссшалыюго независимо^ множества ^ ,, получим С ^ е * 1,

и < 1 . Следовательно, для ¿рхшх оцено:

хроматического числа п. к-в. графов через плотность или обхват можно использовать результаты о графах из . Еол; труд-

ной является задача описания п. к-в. графов, которг.е не окра--шивавтся в к цветов. По определены!- каждый такой граф яа. ется реберно-крптнчесхскм относительно раскраски. Теоре/?у Брукса'мо:шс трактовать как описание к~в. графов с пусти.! чь^/-жзством Н(С) вершин степени, большей к . оторые нельзя раскрасить в к цветов..Дирак [15] и Галлаи [25] окисали таете графы с 1ЩСД| < 1 . В рассматриваемом параграфе ■ списаны . для к Ъ все п. к-в. графы, которые нельзя окрасить в I-цветов. Оказалось, что удобнее описать все п. к-в. пгаергр которые нельзя раскрасить в к цветов, В дальнейшем будем называть такие гиперграфы к~исключи?ельньш.

Удобным инструментом стало пог~ те предписанной раскраски, введенное Визингом [з] и„ позднее, Эрдешем, Рабином я Тенором [21]. Назовем предписанием для графа. С- отображение Т множества У (С) во множество поданояестэ датуральчых чисел. Ра«- -краса | вершин О- согласуется с еР, если f для

вершины а &^/ (С) . Скажем, что связны!': гяперграф 6 о •'•; максимальной степенью вершин, не превосходящей к, является . ,. /?к~графом, если его вёрппшы нельзя раскрасить согласие пред- '' писании Ф*, где

¥*{*>=( »если Н**" \

, если аии^^О < к ,

Следуипий факт является кеболь: • обобщением теоремы Гад-лай [24], __ .

Лемма. 3.2. Пусть СК^'Л) . является -графом для некоторого % , ..^ичем Сг на есть полный графили нечетный цикл, Тогда блоки С моязю разбить на два подмножества и -Вг непересекающихся по вераянам блоков так, что блохе из. ¿В^ похсрывают V , а блоки аз !В-> .окрывавт все воргяяш стелена к ж только их. Все блоки из £Вг при этом являются перешейками. Каадый блок 3 <з является при к«2, паре-шейком, при к=»3 - нечетным циклом, при к^; - полным . к-верпинним графом, •

Заметши, что/здесь перешейками могут быть и гиперребра.

• Для к -исключительно о гиперграфа Са(У через Gft,] обозна'-~м гиперграф С<м( Ltz'), где

Е'-{ели| «ее Ь ъ 2} . Среди доказанных в параграфе 3.4 свойств ^-исключительных гкпергрпфоЕ G~(V,£) отметим "-юйство 4. Пусть е . telï 3 ,1e. г\Ц 2 . Тоща • е »¿nL является перешейком в G M .

Свг"отво 5. Су'"отдует компонг ->а связности CfL], являющаяся ¿^ -графом, яазовем такие компоненты -компонента:

Свойство 7„ "чл любой -компоненты в Gît ] ги-, перграф F(G ~г ), полученный из пу чи добавлешш

; рео^а ^ , содержащего вершины смежные хотя бы с

: одной вершиной йз ? s является к-исключительным гипер1рафом. .М" Из леммы 3.2 и. свойства 4 непосредственно следует

Утверждение .3.10. Пусть С^СЧЕ1) - связны!! ' 1<-исключительный : ерграф,- M((V) с {ад} „ Тогда ■ • j

1) является ^-графом;

2) если ё Е , W.«® , то л- ">о ê^îmJ, 4 для некоторой вершины с ^ 3 k-i » ^0 •^М1'' являетсл

ошейком A ifl] „ ■ ' Наоборот,? пусть 2' - произвольный . '^-граф, a Sl^ и -множества1 блоков,- описанные в лемме 3.2. Тогда, добавив новую вершину f' соединив <•>?■ 2-ребраьи с каздой -ершиной »? степени в 2 и расширив любое количество ребер из

путем добавление, j них и? , получим к-исключительный гиперграф Сг с !H(OUl.

йтак, утверждение 3.10 характеризует все . к-исключлтель-,1ше .гиперграфн (k с £ i , а клесте со свойствами 5 и 7

дает полиномиальный алгоритм распозна: ния к-исключительных гаперграфов. Действительно, пу^ь на вход подан гиперграф Сначала : эверяем, является ли G п. k-в. гиперграфом. Пусть является. По Сг легко строчтса ^[L-] ; Если среди ••омпонент связности G-fL"] нет -компонент, то G на является к-чсключителышм. Если 2 - некоторая ? ^-компонента и то переходим к глперграфу FiCr,Z) с меньшим числом вершин. ;г т. |Н(СЛ| й | , и тяш<ймём утверждение 3.10. В частности, по лейте 3.2 при ^ к любой k-исключительный шпергр ' содержит по-^й к-'^ршанный подграф. Значит, при ■■'

Доказаны и более содержа?елт"ие ,,тверзденпя о струна..je 1с-исключительных гиперграфов.

Теорема 3.11, Пусть к s 4 и G^CV.f) - к-иск^ичителы Я гиперг-аф, С, Ф . Toi,., а

1) существует такая -:ризгаа & V , чт VMu>} иотгм разбить на подмножества ,,.. . подграф, порожден-' ный казздым из которых, изоморфен мд;

2) каздь-"* блок есть либо перешеек„ либо

К ¡с_1 и кадцая вершна u е G [Ï.] п. .жц зжит не болзо ч ;'• двум блокам CrfLl '»

3) число вершин з W(G-) равно числу компонент в ^ [ь] .

Те орет 3.12. ÏÏ ть - 2~исклвчителыш£ ; гипер-;

гг^ф. Тогда для тгиоГ компоненты связности • итаерграфя i CVlLI имеем

1) R смежна не более чем с двумя ■ -рпзлгамг из Н(С);

2) если R. c:.îe.,^ia с вершинами Ц, и t/Л i. H(G), .'О ла t-t^ . или и)г соединена с R ровно одним ребрсм. _ •

Следующий параграф лосвяае" изучении где ~ класс кра^в хорд, а - класс пх дополнении. Граф G г V(Ct)~{i>, называется графом пересечений .хорд

(или просто граоюм хорд), если для некоторого семейства F-{Uл?хотщ окруяност* вершины к смежны тогда и только тогда, когма Ц и К; пересекаются, т.е. имени обку» точку, не прсг-длежащую этой окружности.

Графы хорд под i .знши' названиями возникают з разнь1" разделах теории графов и приложении: при лзучешг задач ' -¿еорж! расписаний ; цепных дробей, :дЬских графов и уш-шодзгаярннх матриц. Задачи нахождения наибольших клик и а ЗС , s в "X рэ-иазот. за полиномиальное время, !адача ет хождения . роматячео-кого числа графов из MР-трудна, а сложность зтой задачи для графов из неизвестна. В это>. ситуации безусловно представляет интерес изучение и В этигл направлении известно стедутощее. Г тапетян [б] ' -казал, что

± 8 , i(-X ,U) й-О,s- k ( W+.d) • второй из эт:и результатов независимо доказали Дьярфаш и JïeXw«i. Дьярфапг Г, "б] нредлсяяд--, доказательство утвервдения ( U--0 . к

сожалению,- ле*лма,2 этой работы ошибочна. П* . исправлении получается оценка -V а* г) Ц -

В. расе:«; .-рстаемсй дассоргедяи на основе вдеи расслоения

дек?' ча

Krki

З.тз. т fCMAV£(U)-jQ(Wit --- v '

L i , если к нечетно.

Y.-з ;;ок'\з:.техг>с7г теоре::п 3.13 лог>"» полупить алгоритм оло:гчост;т' 0(v»%) дли paci._ .cick лгзСого л-серпянного гра^а Ь из 3£ с ^ при по:.:о-3! не более чей цветов.

■ Определи; ректорентно числа и (к (i} , i. (к, (L) ;

1)*u{u,<> = u. =о ;

2) при = * »V-vK* U

J помоз;ьы принципа Дирихле доказана

ie.fUJ

Тс ома 3.14. $[Х , V) Ъ U(k)> £(к) +Г u ( к, I) , гдэ

ГО, если ii четно, (.1. если к -счетно.

Значения функпхй ' ^(к} и К [к) совпадают при малых к. Разность MiikVUik) вс да меньпе 5"U/i2 . Следе- стельно„ ( X. , к.1) асимптотически равна к к .

•Ухе упоминалось, что ✓-1 . ,

; j еотюма о.

Теоге.-.-а 3.16. Если то >£(">*,к) is 0,Ук(&|к-г) . ...... ....... - ti.

Оценка теоремы З.Т ' тесравнима с 1 , ло все-таки не :б~ л' тся линейной по к . Значит, в X есть графи, устроенные 1 более сложно, чем графы из родственного класса SD - графов пересечений дуг окружности. Каралетян [б] показал, что = . = •

В параграфе 3.5 изучаются оценки хроматического числа -¿;афов через разреаенкость иг ополнений. Наполни;л, что разреженность графе. - зто ^мощность наибольшего числа ребер в Gr , никакие два из которых не принадлежат одному и тому ке го талу подграфу в &. Разреженность графа является оценкой снизу для ей (Л-) - наш- ашего числа' клик,покрнэаших

все ребра графа G , .Идя к^-'ДОхо графа Ç без все<. вер-

шин очевидш неравенства из(.Сг!< £ cc(<î' . w(C} î s cc(Cr) . Партасарати к Чоудутл [2бТ предполагал,., что -ля дюбог графа Ст без вс^иекнкх вери_-л

(4)

и, таким обозом, Oj(A) - ^(Ст) ^ , ¡.¿лй^: -i Дат-

. тон доказали справедливость (4) для ->афг-> Gr с 1>(q ) ^ Г , , Однако Эрдёи [¿о] показал, что (4) не выполняется для почти всех и-вершинных графов и, более того, для каждого .. начк- V,-лая с некоторого ,, существует такая положтелькая хонстак-^ си » что д 'любого Vj кайд зя И-вершинный : • '.'

*раф G-^ без Есескилсных Берлин с

В связи с этим возникают следукике Еопросы:

1) Чему равнс Ц - наиб "ьиее такое целое; число, \ о для' графов Ст с k(Q)* Ц выполняется (4)?

2) Чему 7 шо Ua , определенное абзацем зыае? " '

3) Как ыокно оценить свет"7 X (G) через Ц5-) ■ и чк-. ело вершин Cï , ' чш Ц ? Как растет С^ с росток Ч при U ^ со ? <

Эти bol. хш бн-^î сформулированы, в частности, в работах [19, 20]. * '..•'■■

Теорема 3.17» Если граф G- не имезг _ '-.гмеялых зерага л • /Со) î о , то /(a^ W^). « ■

Теорема 3.18. Пусть П >/• 10, и ^ G , С "IV и j - геже чтгела. Тогда для любого Vi-г данною графа Gr без зсесжкннх вершине ) * W имеем

щхъЫ-«'..

Следствие 3.19. Д,.„ С^, определенной в (5), лрк ^^ б справедливо неравенство сц

Теор; 1 3.20. Если обхват графа G не меньше-носы.. , то .. № f-fi . : ,.;.

Применив теперь теорему 3.1, пол4-"^, что. б и

' i/j - £ ". для люб х> > 0 , Д^ути слова!,ш, пли - й

происходи? «... -.'ественныи скачок. Если к (С} 5 , то

Если ка М 5 } - 6 . то ^(Сг) мояет бить соль угодно болъ-

пь...

Теорема 3 22. Для лпбсго ^7 справедливо неравенство со 1 -гЪ/С^-г4) . .

лгак, -- ~ г-П./(<[й-г) ^ С ^ ь {- 1/1}*}, Снова доказательства верхних оцс лс содержат ъ себе полинс!.:—льные алгоритмы растески.

Перед описанием . ^дсг-'лзкя глава ' -¡апомним несколько определений. £тяг'т-хяе:.1 рео^а (и,1>) - в графе 0- называется замена нергкн и к I? на новую в органу „ смежную

вераннаш, кг~орие смекни в. С« с и ели с „ Говорят, что граф С стягивается на граф И ее."И можно

■лучить из С^ - при поыода последовательности стягиваний ре-Сер к удалений версии п(клк) ребер. Числом Хадвпгера ^(С?) гра-'-а С- . называется наибольшее число вершин в полном графе, ка ..оторий стягивается Сг„ Число Хадвпгера является важной структучой характера :;кой графов, ¡¿асса работ связана с гипотезе:. .'.адвлгера о том, что число Улдвигера любого графа не меньше его хроматического числа. Теореыа о четырех красках является частным сдучаем этой гипотезы. Вагнер [31] ввел функция

к показал, что

. Гипотеза Хадвг 'ера эквивалентна у?верядетш, что и>(к)И' для .таЗого к. работы Мадера [27] слезет, что и?(к)> .

В главе 4 из., .шэтея экстремальные.эадачи о числе Хадвиге-ра. .'Лногхе специалисты, среди них Зыков „ Внзинг, Боллобаи, Ь'а-дер, Миллер, Дьори, кн' зсозались0 сколь ...ало цояет быть -гс-х Хадвигера у графов с данной средней степенью. В частности, каковы и =

Понятно, ЧТО ^Дк) при

' к „ Высхлзывалось предположение, -в том тесле и яоллобапем >], что - к„ Осное'"!.! результатом главы ,4 является

доказанная в параграфе 4«2. '

Теорема 4.1» Для любого - к^З

Таким образом, найден порядок роста функции :: fyíH.

При этом оценки сверху получены мощноеткыми е""';.:ен основе доказательства нижней оценка приведен илтор;...м е::с сти O(U^kn) , ПОЗВОЛЯ. ЛЙ стянуть .ЛОбОЙ V>-BepjEnn-2i! rp'ip

о более чем kvo ~ ( ребраш на полный i.-aO с но

чем !í]í вершинами. В работе диссертрчта [2£j дакс лучшая константа в оценке снизу для , ч. . з теорс. - -i.!,

но докаэател. ^тво более сложное. К т^'у se позднее диссср.а'^а Томасон [30] для достаточно больших к из акжностшэс соображений вывел существенно -шуга константу в нкзней сцо. л.-ч

Из теоремы 4.1 непосредственно вытекаю? ■"■сколько утгер:.:-Д-ний. __

Следствие 4.2. u)(k) г к ,

Следствие 4.3. дя почти всех и. rpcQo"

гипотеза Хадвигера.

Замечание. Результат следствия 4.3 незавкстг-ю до/сазан Зр-дёшем, Боллобашем i. .Сатлином [ '1.

Следствие 4.4. При достаточно большое !< гипотеза лагг.-тера верна для ■ эчти всех графов с и ввргдз.'П л *10 рзбра-ми.

Следствие 4.5 Пусть Ni «с) - наименьшее число Хадг-лгора, которое мо;кет иметь к -связней граф. ' гда пород»»* росса г-г "ичины N(k) при к -?оо. равен к /\[(!о $ к .

В параграфе 4.3 обсуздаются взаимосвязи чисел 7¿ sirv-графов и их дополнений. Традиционными яагяюпл задя-яг р-гга Нордхауза-.^здцуш о шксш.у<лах к »жвкмутх по вое:? И ным -рафам суммы и произведешь каких-нибудь хз^к/еп^стл;: графов и их дополнений. • > частности, Si. д-гка [3-1 ] цредлсчо-гсл, ЧТО Vwa/x {líCr)t^)|(V(ü)S =Hj=Vl Зтс незерно.

Теорема 4.7. Для любого И

vwaoc. {\ '&)[ -v\\=[r Д j ,

wvo,oc ij(Ç)! !v(aV; - и} ¡ ( i^./sf-1.

Для минимума cjwmh точное 'значение нг найдено. Не- -гесъе.,:-: 4.1 вместе с короткими мощноочтпгма расадениямз позж-лгл? ~ каза""г-

-hitg 4.8. Порядок роста величины »•а и {vjO*) * 'г(0)! IViG-)1, = И } при И оо -.авен И /^¿vTvT .

Для полнота графа w.ieev ^(KvO = И-4 Ока-

sujf ся, при для ЛРбого нетрг :;ального и -вершинного

ipxl.i Gt геллчяа ) больше и.

Торгу"1 4.9. Для не пустого и не полного графа

^(Crhjü^iVuivi-s)],

йьонка хеореук при ei<k и v»'ik + 3 достигается на получе. ■■jm кэ звезды ^ i, ¿o,s"nj подразбиением |_0,г ] се ребер ка цепи длины 2. Естествен вопрос:

iro гл улучшить ха, л:у теоремы 4,9 для таких графов С», что > к ? 2 ?

Утг-сртсггпе 4.10. Дот каяздого целого существует та-

кое с (1с) , что для лпбого графа Q с к и | = и

V 0(:Г и - с (к) .

Причем c(W < * к ■* с(к-1) .

Сколь велико г.ю.т.ет бить в утверждении

" ^(й) <k ^^^¡Vtol - с Гц"?

Г:з утверждения 4.10 следует, что Нетрудно

убедиться, что ^(t) < o,S к/( к-1) . Оказалось, что нахождение связано с зад1. .ей о минимальном числе !•:■ зависимости для т -аорешганх графов с числ- Хадвагера, мены:"'" к . 3 таеткоати, из р-^лшмта Дуле и Мейняля [1б] непосредственно получав

О.тегс-;?.:;^ 4.13. .Для лгбого целого ^ 3 и л^ого О с £ 4 i/з наедете; :акое с(к,с) , что для каждого .¿афа

с t^(G-) 1с справедливо неравенство

0,S|V(G)t(l-€ И/dfe-a)) - c(fc,£) .

Попутно доказано

Слолотр-из 4¡15. Вычисление числа Хадвигера уяе в классе -рафов диаметра 2 является А -'-трудной задачей.

Заверсгма^ параграф глава 4 развивает тему теоремы 4.1. Изучается, сколь велика долкна бить средняя степень вершин графа G , чтобы гарантировать наличие в С? "малых" подграфов

с числом Хадвигера не менее к. Известно, что гля ль .г-: €>о при и ъ Vi0(£) в любом Vi-веркгако:.; rp:r"'s Г. г fnw ] ребрами обязательно есть tjitoi дшш, к^ прот>:х:аь::;=.!й а , > не в л" б ом таком графе ест: вдклн дана., ¿гепьпей V-•

На конференции в Оке.орде (1969 г.) Эрдё: [is] ггргг-оло-uvl, что для каждого £ > О существуют таете С{£) i: и3(£ с) , для которых при И^и0(£(с) жобой И -зержн?:- ; rp&J с " | ребраш содер' -т* неплоский подграф на С(£) ворашшх. Нскг/.-зо, что любой граф <* с являс-.ся • ялосяан. Поэта..

следующий результат, в час~"осга, доказывает z вредя*?.« ■•rxnzic Эгп,сша,

Теорема 4.17. Д; любнх 1г>3 , О < £ £ 0,S сузеств.-о?

Ч-дП 18 c/(l<,e) i И И» (k, £) , ЧТО п:.., И^Ис'ЛО

любой И-вершинный rpatb с Ы1*6! робра:я содзтг:гг подхткгЪ G' С W И |V(G')(

Порядок роста оценки d{k,i) г; £ при с -- 5

улучать нельзя, а по U при t«-?co ' нельзя сделать лучг.е,чом kz. wHOBa доказателг",тво содер^т в себе полино:. 1:альк:ь': с:ггс-ритм нахождения "малых" подграфов С/ с 1?><3г') ^ к .

"?метпм, чтп в совместной работе автора и Л.Пг/Зэра [57] доказано более сильное, чем теорема 4.17, утверждение, но диссертации использована лишь m-ть, принадлежащая азтеоу. 3 параграфах 2.5 и 2.ь переработаны неопубтиковгшНЕе рззузьгагн, полученные со2'"?сгно с К.Вебером (ГДР), приношу Л. х-гзру -Г.Зеберу благодаркост. за согласие на использование огих "атс~ риале? в диссертации. Также благодарю сотруднг >в отдала . теоретическое чбернетиии Ш СГ .Ш СССР за вшшшая» п поддержку.

литература

1. Бородин O.E. О разлоаенш! графов на выроядашке подграфа // Методы дискретно анализа з уоряи графов и логических функций. - Новосибирск, i976. - Вып. 28. - С. 3-II.

2. Буртия Ю.Д. О вероятности связности случайного no.r а-фа /\-мерного куба // Проблемы передачи инсТюрмацли. - 1977. -т, 13, № 2- с. 90-95.

3. Визпнг В.Г. Раскрг-ча .ршик ip; .д в предписанию

тц // • лодн дискретного а длиза з теории кодов и о "ем. ,1'о-

1.оо;с<3:трс:-:/ 1976. - Зьш. 29. - С. 3-10.

•1. Гл:.:?.ди Э.Х., Глебов Н.И., Перепелица Т.А. 'ягорихмы с oüCHK-vtH для оэдач дксифегкой оотшгэации // Проблемы кибернетики. - 1975. - Bun. 31. - С. 35-42.

5. Г-уов Ю.Л. 0 предстаачеюш булевых функций системами .••ккиСтк неравенств // Кибернетика. - I9G5. - .9 5,- С. 7-9,40.

6. Клралегяк H.A. 0 совершенных, дуговых и хордояцх. гра-х: ¿втореф. дне. ... канд. физ.-мат. наук: DI.DI.0b - Новосибирск, 1934. - 9 с.

7. Коспанс Э.Ш. 0 покрытии шарами единичного радиуса, ■центры которых несравнимы // Методы дискретного анализа в ст. тезе управляющих ; тем. - Новосибирск, 1986. - Вып. 44. - С. 54-57.

8. Чухров И.П. 0 максимальной мощности тени антицепи // Л:скрег:'.ая математика. - 1989. - Т. I, У» 4. - С. 78-85.

•}. Bollobaa Б. Extremal graph, theory. - London et Ol.: Aeaa, Prcoo, 1978. r '"9 p.

1- Eollobao Б. Ine evolution of the cube / Annals of dir ecrjtü nathenatico, - Arastordan - How Yorks Horth-Holland P.Ü, 1933. -.I5. 91-93.

11. Eollob^B B. Ccapleto matchings 'n random subgraphs.of the cube // Randosj Structures and Algorithm. - 1990. - Vol.1.

12. Bolloban В., CatJ-'ч P.A., Erdoa P. Hadvdcer's conjecture io true for alnost evury gp?aph // European J. oi Combinatorics..- 1300. ~,V. 1. - P. 195-19Г '

13. Erookn II * . On colouring the nodos of a network // ?roc. СсаЪга^со Philoo. Soc. - 1941. - V. 37. - P. 194-197.

14. Ber.etrcvito J., Katona C.O.H. l:- ■влей coEbinat^^.ol рг'-'Ыэяз in relational . .ta base // Lect. liotes in Conput....oi, - re 1. V, 117, - P. 110-119.

15. Di 2ГЗ.С G«A. .theorem of H.L.Brooks and a conjecture of H.Hadv.icer // Proc. London I.'nth. Soo. (3). - 19r>7. - V.7, '.'о ?_S, - ?. 1C1-195.

16. buchet P., iieyniel H. On Hadwiger'a number and the stability lumber // Annals of discrete mathematics.-Ansterdam: :iortii-i'olland P.C., 1932. - V. 13. - ?. 71-74.

,17. Eraoa ?, Graph theory and probability // Canad. J. üath. - 1S.J. - V. 11. - P. 34-38.

10, ErdS" V, Soras Problems in Graph Rn;l

corabinatGrlal analynis // Ccmbina-f orial Mathe: "iiie and ita Applications (Pi-oo, Conf, Oxford, 1969"'. - London: Aoad Pra. ,t 1971. • P, 37-109.

15» Erdös P. "°roblei. , and reaulta in grt h theory // Tha';' theory and applioationa of grapbs, <- ITcw Yoz-k et al.s - Wilaya 1981 „ « P. 331-342. : \

JO, Erde P, On the covoring of the v-3rtic«s of a graph by cliques // J. Math. Res. Expoöitio. . - - V, 2, Ho 1.-

P» 93-96.

21. Erdös P„, Rubin A.L., ^aylcr K. Caoosability in/

grapha // Combinator. ja, graph 1 ..'¡oi'.y enö coiap-jtin-? (Rrocs, Weat'/•' Co^-st Conf., Art :!a, r ?.if. 1S7. ).- - 1?S0, - 1::5»157»

.22. Erdös Spencer J» Evolution öf the n-cwba // Comp. Math, wlth Appl. - 1°79. -,V. 5. - 7 39. ',*

23. iüredi 2., ¿.ahn J., Xlettman D,J, si>iu j cc-veivng,.. of the bypercube tvith inccraparable con(i«.es // Preprini SEK, 1968.•'" -4p..

. 24« GeCllai I. Kritische. Grnr.U*r., I // !3$gyar. iudo:.iany , . Ale ad -V;h„ int. Köal. - 196.'). - V.l. - P. 165-192. v;

25. C-cilled x>. Kritische G^h«^, II. // Ibid -- \r, 7. P. 373-395,

26. Gyarfi'.a A, On tha chromr.t Lo nwber of .Eiultipl 0 inter* val graphg anf ovarlap grapha // Diaoraxs Math. - 1,i5»-V. 55» " 2. ~.P, 161-166. " ,

. 27» Hader \7» Ho.uoraorphieaaTzo für Graphe // i.iath. Anna-len« - 196r . - B. 178. r 5. .54-168. ...

28» Parthaaaraty K.R,, Choudvm S.A. The edgs plaque cover p:umbi of producta o£ gr"->hs // Math. Phya. Sei., - 1976. « V, 10, Ho 3» - p. 255-26-1,,

29. Shannon C.E. The synth^sia of. two-temina"1 . switci^ns circuits // Bell System Tech. J,~ 1949.- V.28, N0 1,- P,59-98.

30. Chomason.A.G. Ar ¡xtremal fun- i<?n für oontraotions , of graphe //.Math, Proc, Cambridga Phi^-oa. F**o. -1984.- V«. 95. •? P. 261-265 .

.31. Wagner. K, Über, eine Eigenschaft dar £benon Konexe// Math, Annalen. -.1937» r B, 114, - 3.

32. Weber K. On the -"oli ton of« x .don.graphs in tha >.-eube t Grapha,; Hypnrgrap. and, ..pplioationa. -Teurer Te:,ite

sur Mathematik. - Leipzig» ТеиЪпег, 1935. - В.73.- S. 203-206.

33. Weber К. •.compononts o£ randora c- J-Pho i tho n-cuba //. Elektron. .Inronn, verarb. Kybernetik. - 1986. - B.22, ii 12.

- 7. ;oi-6n.

34. Zolinka 3. Hadv.icor nuobero of finite grapha // Uatli. S. vaca. - 976. - V. 26, lio 1. - P. 23-30.

РАБОТ' АВТОРА ПО TK.flü Г"СЕРТАВДИ

36. л'осго..л A.B. Верхние оценки типа Нордхауза-Гадду*,а для числа Хадзигет»а // Тез. докл. 1У Всесоюз. конф. по проблемам теоретической .лгбернетмки, Новосибирск, авг. IQ75 г. - Новосибирск, 1975. - С. 139-140.

36. Косточка A.B. Построение k-вырозденных к-хроматнче-сюпс; графов с любым обхватам // Тез. докл. У Всесоюз. конф. по щ. лемаы теоретической кябзрнетикп, Новосибирск, ишь, 1980,-Новосибирск, I9S0. - . I30-I3I.

3 . Косточка A.B. Модификация алгоритма Катлина // Методы к программы репезия оптимизационных задач на графах л сетях. -Ч. 2, Теория и алгоритмы. - Новосибирск, IS82. - С. 75-79.

33. Косточка А.В„ 0 минимуме чиелг. лдвигера для графов с данной средней степенью вершин // Методы диыгретного анализа в оценках сло-люсти управля их систем» - Новосибирск, IS82. -Вып. 38.-С. 37-58.

39. Косточка A.B. О ыакекмалы. мощности гранит. ильтра в И-мерном кубе ' Методы дискретного анализа в изучении реализаций логических функций. - Новосибирск, 1964. - Вып. 41. -С. 49-61.

40. Косточка A.B. оценка, хроматического числа графов хорд Через плотность // Тез. докл. УП Всесош. конф. по проблемам теоретической кибернетики, Иркутск, сент., 1985 г. - Иркутск, 1985. - Ч. I. - С. I0I-I02.

41. Косточка A.B. О покрытии кликами графов хорд // Тез. ;окл. Всесоюз. конф. по причиной логике, Новосибирск, окт. 1835 0 - Новосибирск, 1985. - 0. II6-II7.

42„ Косточка А„В. О максимуме хроматического числа W-вер-ьанннх гр'"юв с заданным обхватом // Тез. докл. I Всемирного конгресса об-ва ыатеы. статиста-' и теории вероятностей ем. Бе, гулли. - М„: Наука. - Т. 2. - С. 502.

43. Косточка А.В. О верхних оценках хроматического числа графов // Труды ¡1н-та матемс :ш: СО АН СССР. Т. 10. Модели v методы оптимизации. - Новосибирск: Наука, 1988. - С 204-226.

44. Косточка А.В. Вер^шя оценка • угости границы антиц -ги в »-мерном кубе // Дискретная математика. - IS69. - \ I» № 3. - С. 53-61. t 'J

45. Косточка А.В. Раскраска критических k -ныроэдепных графов // Тез. докл. 1У Есесоюз. совещания "Mei ,дн л про: гммч решения оптш. ¿анионных задач на графах и сетях", Новопибирск, окт., .1989. - Новосибирск, 1989. -Ч. ¿. - С. 55-56.■ •

46. Косточка А.В, Наибольшие парооочетания и ком знекты с таиости случайных суграфов и-мерного единичного ;нуб;. fj Методы дискретного анализа в изучении булевых "''дсопй и графоэ.';' - .'овосибирск, Ь89. - Jun. 48. - С. 23-39. . "f

47. Косточка А.В. Оценка числа связных подграфов, п.тевпдах малую реберную грант в графах с данн . максима. ш?ой о-е-пенью / Препринт Ш СО АН СССР. - Новосибирск, ^¿20, - ы I. -13 . '

48. Косточка А . О макет иной мощности границы Шперне-рова семейства // Доклады АН СССР. - 1990. - Т. 310, $ 3. -С. 5~о~:з8. ,

49. Косточка А.В. Нйнняя с -¡нка тгроиззедеяия чисел Хадви-> ■ гера графа и его дс олненпя // Комбинаторный анализ.. - Москва,; 1990, - Вып. 8. - С., 50-62.

50. KostL лка A,", On Haavriger numbers of a gruph and. itf complement // finite and infinite sets, - Amsterdam! Г rth-Holland. P.C.j 1981. - 537-545. ' ,.|y.

51. Kuatochlm A.7» Lo«.j bound of the Hadwiger number .of graphs by their average degree // Coinbiiifviorica. - 19S4.- 7,4» II 4. - P. 307-316. . ,

52. KostochJca A.7, On the nuat ~ of graph edges not "inr-taiiaed in common cliques // ui'apha5 Hypergrapha ш Applicaii-^. охш, Teubner-iexte sur Uathematilc. - Leipzig: Teubner,'19B5.

3, 73. - S. 110-114.. .

53. Kostochka A.7. Maximum set of,edse:' no two.covered by' p. clique // ombinatorioa. - 1985. - V. 5» Л 3. - P. 229-;. 5.

54« Koatoohka 4,V. On the minimm of +4o Hadv/iser timber for grapha vd-th a given mean degree of vertices,// MSS Translations (2)?'--198б. - V. 132., - P. 15--.2. ! - V

'' 55. Kpe.jchka A.V. über die chromatische ZoJil von Krois-grsvphon - und ihren Jfompleiaenton // Sagitscs'beri cht iiath. . For-oci -csinstifcut Ob«...voifach. iyS6. - Ü 28. - P. .„-13.

' ■ 56. Xoetoohka A.V. Upper bounia of the chromatic number oi.-5p.-phD via v-xiqua number with reatrx. ¿ions to graphs' atruc-turci //.Ibid, - 1988, - K 26. - P. 14.

57.-Xo oehks A.V«, Pybor L. Small opologioal , coraplote ~»bi^rapho of "dsnoo" grapho // Conbinatcrica. - 1988* - V. C, .. 1. - ?.:83-HSo'"? ' '

s

!T