Сужение, К-дефицит и раскраска гиперграфов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Глава I. Свойства гиперграфа инвариантные относительно сужения ребер.

§ I. Сужение ребер и к-дефицит гиперграфа.

§ 2. Свойство Ж1(К,В) и сужение ребер гиперграфа

§ 3. Свойство и К-дефицит.

§ 4. Алгоритм вычисления К-дефицита.

Глава II. Раскраска гиперграфов.

§ 5. Оценка хроматического числа гиперграфа.

§ 6. Раскраска ребер гиперграфа в смысле

Нэш-Вильямеа.

§ 7. Матроиды на гиперграфах.

§ 8. Алгоритмы.

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

Особая роль теории графов и гиперграфов в решении этих и других проблем во многом обязана простым и наглядным формулировкам различных задач в терминах теории графов. Притом круг задач, охватываемых этой теорией необычайно широк, среди них как практические задачи, так и теоретические [20] . Непрерывному развитию теории графов и гиперграфов способствуют и проблемы, возникающие и в самой теории графов.

Возникновение теории графов как самостоятельного раздела математики часто связывается с проблемой четырех красок. Если кто-то в этом может и усомниться, то наверняка можно утверждать, что "Раскраска", как раздел теории графов, обязан своим появлением именно проблеме четырех красок, и во многом благодаря сложности ее решения [ 23,24,11,12,1^ .

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

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

Настоящая работа посвящена исследованиям по раскраске гиперграфа в смысле Эрдеша - Хайнала и обобщению на гиперграфы раскраски в смысле Нэш-Вильямса.

Напомним, что гиперграфом называется тройка Нв (XК) [б] , где А - множество вершин, Ц - множество ребер, а

Я - двуместный предикат, задающий инцидентность между вершинами и ребрами. Множество вершин, инцидентных заданному ребру ггеУ и множество ребер, инцидентных заданной вершине

- 5 ос<?Х» определяется соответственно:

ЛСЮ : К(ЧЧ) =1],

Шх) = £гге и : =

Раскраской гиперграфа Н К) в смысле Эрдеша

- Хайнала называется разбиение множества вершин X-Х^Х^и— , где V ' при этом К называется числом цветов. Другими словами, раскраской в смысле Эрдеша - Хайнала называется такая раскраска вершин, при которой нет одноцветных ребер. Наименьшее число цветов, в которое можно раскрасить в вышеуказанном смысле заданный гиперграф ^ , называется хроматическим числом и обозначается через Полновершинным суграфом (в дальнейшем просто суграфом) гиперграфа называется любой гиперграф //'-(Х, Я') » ГД0 11' и У гс) € X * и'^'&к) = Я О*; и)] (напомним, что Xх и' - декартово произведение множеств X, У' )•

Первую попытку решить проблему четырех красок предпринял английский адвокат Кемпе, который опубликовал свой результат в 1880 году. В 1890 году Хивуд [23] обнаружил ошибку в доказательстве Кемпе и перешел к рассмотрению поверхностей более сложных, чем сфера. Хивуд доказал, что хроматическое число любого графа, расположенного на сфере £р рода р , удовлетворяет условию

ОД) * [з^Лр.(1) для Р&1 .В 1891 году Хеффтер [2Ь] обнаружил ошибку в доказательстве Хивуда и показал, что теорема верна только для / 6 • Через 78 лет, т.е. в 1968 году Рингель и Янгс [п,12] показали, что теорема верна для любого ив 1977 году Аппель, Хакен и Кох [1Э] доказали неравенство Хивуда для Р = 0 . Таким образом, была получена оценка хроматического числа через род графа. Отметим, что одновременно доказывалось и точность этой оценки.

Хотя настоящая работа не изучает раскраску пленарных графов, подробное описание истории теоремы Хивуда связано с тем, что слишком похожи друг на друга неравенство (I) и неравенство (5.11) теореме 5.7.

Другие оценки хроматического числа можно получать через степень графа. Теорема Брукса [22] утверждает, что

Г(4 гДе ~ степень графа £ . Обобщая теорему

Брукса, Бородин и Косточка [21] , Лоуренс [31] доказали, что Х(£) = (УН-[(№ИУ(1>ин)]1 где - плотность графа М , т.е. наибольшее число попарно смежных вершин. В [в] приводятся два обобщения теоремы Брукса на гиперграфы: $(Г(Н) и Х{Н)^(Н)Н (теорема Томеску [&] ), где (Г - сильная степень гиперграфа Н . Со степенями также связана и теорема Визинга - Вильфа [25,17] , утверждающая что 4 \)(/(/-) , где число Визинга - Вильфа определяется как максимум из минимальных степеней всех подграфов графа Z . Ершов и Кожухин /V/ оценивают хроматическое число графа через цикломатическое число гДе соответственно число ребер и вершин графа ¿, . Ниже (§5) будет показана связь между теоремой Визинга - Вильфа и теоремой Ершова и Кожухина и будет дано их обобщение на гиперграфы.

Для раскрасок графов в смысле Нэш-Вильямса известна теорема Нэш-Вильямса [20,32] , дающая точное значение хроматического числа данного графа. Эта. георема будет обобщена на гиперграфы.

Настоящая работа состоит из двух глав. В первой главе "Свойства гиперграфа, инвариантные относительно сужения ребер" исследуются два свойства гиперграфа, сохраняющиеся при сужении ребер.

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

Для произвольного натурального .числа К назовем К - дефицитом гиперграфа число где = Х(гс) = (зсеХ'/Я(х,и)=1} .

Сужением ребра иеУ гиперграфа Н—(Х,и)Я) по вершине СЮ назовем гиперграф ^их) » определенный следующим образом:

1.

2. у Фх. или, 2ГФЦ Яи^^) = Я (УГ) .

Гиперграф И'- (X, II • Я') назовем сужением гиперграфа если Н' получен из // путем последовательного сужения его ребер.

Основные вопросы, которые ставятся в § I состоят в следующем: как изменяется К - дефицит гиперграфа при сужении его ребер;

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

Очевидно, К -дефицит при сужении уменьшиться не может, поэтому ответ на эти вопросы дают следующие теоремы:

Теорема 1.1. Пусть Н-(/,и;£) - гиперграф, К - натуральное число, осеЖщ-, /Хсю) > //.к ; тогда

5; (//«; б .

Теорема 1.2. Пусть ~ гиперграф, К - натуральное число, а ребро гс^и таково, что (ХСЮ/ тогда в может быть не более одной такой вершины ос , что

5; (Нж) > <гА си).

Для К~1 и <Г/>(М) ■= утверждение теоремы 1.2 доказан» но М.сСогеа [гь] .

Заметим, что ограничение на мощность сужаемого ребра в теоремах 1.1 и 1.2 существенно только в случае, когда £к(н)<0 . Заметим также, что для ц-1 заданные ограничения необходимы (следствие 1.3). То, что из любых двух вершин по одной из них можно сузить данное ребро, дало возможность доказать следующий факт.

Теорема 1.3. Пусть //=(Х, £/;/?,) - гиперграф, К и £ -натуральные числа, а -и^Ц - произвольное ребро с л« / », * е-т -т)=,, (¡щ, [Щ.

Тогда для любых трех вершин Х(^) существует такая вершина ос б » что

Из этих результатов получается ряд интересных следствий, наиболее важным из которых является

Следствие I«6. Пусть ti-(XjUjR) - гиперграф с ¡/Mj>/Z для любого u^U ч а К и В натуральные числа, тогда Н можно сузить на граф так, что

Связь к - дефицита с известными характеристиками графа для устанавливают:

Теорема 1.5. Если - О $ то с» если о , то где ^(¿J

- цикломатическое число графа, £ - общее количество компонент связности, - количество компонент без циклов.

Второй параграф посвящен изучению свойства Гиперграф // = (X, U) Я) удовлетворяет условию dTl СК, В) если V У^Х : /У/^ -[к] М(У) £ ф/ + £ , где ( У) fи/Х(Ю s У//, а целая часть числа JL .

Теорема 2.1 аналогична теореме 1.2.

Теорема 2.1. Пусть к и £ целые числа, К>/1 и гиперграф (X, Z7; R) удовлетворяет свойству Ш (К в) • Тогда любое ребро -и e U с /Х(и)/ Л - ¿4-] можно сузить по какой-то вершине хе [У, г] для любых двух вершин V,* t Х(и) так, чтобы Hvx удовлетворял свойству

Теорема 2.2 аналогична теореме 1.3.

Следующие две теоремы решают, в некотором смысле, обратные вопросы:

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

- 10

Ответы дают следующие теоремы:

Теорема 2.3. Пусть К и I - целые числа, , £>, о , и гиперграф удовлетворяет свойству , тогда для любой вершины эсеХ и любых к+1 ребер

6 У^) = { -и £ и / А С = с ¿-/#7; I >к,к+1 . какое-то из щ можно сузить по вершине эс , не нарушая условие •

Теорема 2.4. Пусть К и £ целые числа, » и гиперграф удовлетворяет условию УП^К,^) .

Пусть далее хьХ - произвольная вершина с /II(х)/ ^ К+1 , ыки 6 Ус^) различные и гиперграф Н'-г Л г , 1 о\ связан, тогда какое-то из ребер 'Щ уг Ук-ц можно сузить по вершине х не нарушая условие Ш(к, г) •

Заметим, что без дополнительного условия (связность гиперграфа /У' ), которая вообще говоря, проверяется легко, теорема 2.4 не верна.

Третий параграф посвящен изучению связи /<- дефицита и свойства • Устанавливает эту связь:

Теорема 3.1. Для любых целых чисел /< и £ , / , гиперграф Н-0^)13} К) удовлетворяет свойству » тогда и только тогда, когда ^ Е »Из этой теоремы получаются ряд важных следствий. Приведем некоторые из них:

Теорема 3,3, Пусть Н-^^^Й.) - гиперграф, К - натуральное число и ¿¡<(Н) Ъ -К » тогда для любой вершины х &Х и любых кti ребер и^ . ►., ^ & ЦСх) с

ХС^О/ >уЛ. - [ (для всех £ ) и таких, что гиперграф и * * •

- II связень, существует ребро ^и^и^. - ■, такое, что

Теорема 3.4. Пусть Н=(Х,0;Я) - гиперграф, К - натуральное число, ¿*к(Н)>,гО » а - произвольная вершина, тогда в может быть не более к таких ребер о ¡м\>,х- [Ц^] , что &(ип)><тк(.Ю •

Теорема 3.6. Пусть , ^ , £ , - целые числа, К,* * ' £ >,-К, • /<я>/ / • £ • а гиперграф Н<КЩ с ¡ХСи!/для любого и (г и удовлетворяет условиям ШС^,^) и (X А) »Тогда Н можно сузить на граф (возможно с кратными ребрами) так, чтобы ^ удовлетворял и свойству ЦТ1(<КЬЕ1) и свойству

В параграфе 4 вводится понятие (к, /) - сочетание двудольного графа.

- Подмножество ребер кенигова представления [5]

Ю^ФДР) гиперграфа Н назовем (К О "

- сочетанием, если:

1. Каждая вершина х & ,Х инцидентна не более чем к ребрам из (X ;

2. Каждая вершина и е V инцидентна не более чем одному ребру из & .

Следующие теоремы сводят задачу вычисления К - дефицита к задаче вычисления (/к, /) - сочетания.

Теорема 4.1. Пусть 6} наибольшее (к, 1) - сочетание кенигова представления гиперграфа (Х,и*Я) , а £ - количество ненасыщенных вершин из £/.

Тогда, если ¿>0 , то <ТК(Н) — £ » а если ¿-О * то к О.

Теорема 4.3.Пуоть наибольшее (к, 4] - сочетание кенигова представления / = (Ху II) Р) гиперграфа Н~ (Х^ I/; й) насыщает все вершины из I] (т.е. его мощность равна /£// ) для всех х (г X » ¿х. - количество вершин ненасыщенных наибольшим (к, 4) - сочетанием в Нх. (гиперграф полученный из Н слабым удалением вершины х), Р=-шх¿х. * тогда если р>о , то (Гк(Н) — Р- К , если р^О , то (ГК(Н) ^-К . Для точного вычисления К - дефицита с^ 0*) ъщ £к(н)<-К можно воспользоваться теоремой 2. В заключении приводится алгоритм 4.1 для вычисления К - дефицита, составной частью которого является алгоритм 4,2 для нахождения наибольшего

К,4) - сочетания. Заметим, что оба алгоритма имеют полиномиальную сложность. Этим глава I заканчивается.

Глава П представляет собой применение результатов главы I к задачам раскраски гиперграфов. Теорема 5.2 Пусть / = (X, и) - произвольный граф, К и Е - целые числа, причем К ^ 4 £ - К Если для любого У^Х с 1У[>/1 выполняется неравенство

У) 4 к/у/ > то

- 13 где - количество таких ребер в , оба конца которых принадлежат У ; - число Визинга - Вильфа максимум из минимальных степеней всех подграфов графа Л ).

Теорема 5.3 Если граф /< - (X, и) удовлетворяет условиям теоремы 5.2, то

К(1() < я«*'* <)*+*

Для /<=/ теорема 5.3 представляет теорема Ершова и Кожу-хина . Из теоремы 5.2 следует, что теорема 5.3, и тем более теорема Ершова и Кожухина не улучшают оценку Визинга -- Вильфа [25] . Важность теоремы 5.3 состоит в том, что на основании следствия 1.4 получается

Теорема 5.7 Пусть Н-^О;!?)- гиперграф с //^(«о/^ для всех 11 , а К - натуральное число. Тогда

Следующая теорема оценивает хроматическое число гиперграфа через К - дефицит для двух различных значений К •

Теорема 5.9 Пусть Н-С^и^Я) - гиперграф, который можно сузить на обыкновенный граф с сохранением дефицитов

5с (V) и £ (Н) ; к < £ , К и Ц - натуральг ные числа, а ^(Н)^-К, . Тогда

УГи\ "

Следствие 5.2 Пусть К и £ - натуральные числа, К<И » а Н-СХ;^; - гиперграф такой, что Уъ^и> ¡ХС"]]

Уи^еЩ/ Х(«) л ХС*)/ ^ *, и тогда

Приведенный в параграфе 5 пример показывает, что если гиперграф не сужается на обыкновенный граф, то теорема 5.9 не верна. В заключение исследуется точность оценки из теоремы 5.7.

Теорема 5.11 Для любого натурального числа К и любого целого числа £ , ¿>/-К » существует граф ¿, с = Е

В параграфе б изучается раскраска ребер гиперграфа в смысг ле Нэш-Вильямса.

- К - раскраской гиперграфа в смысле Нэш

Вильямса, называется такое разбиение множества его ребер и = и^и . - и ик 9 ЫУ ==> ¿/. /? ¿/у - 0 что каждый полновершинный суграф = можно сузить на граф без циклов.

На основании теоремы 3.1 получаются и другие критерии К -раскрашиваемости.

Теорема 6.4 Гиперграф Н - (Х} и} - раскрашиваем в смысле Нэш-Вильямса тогда и только тогда, когда

Теорема 6.3 Гиперграф НК - раскрашиваем в смысле Нэш-Вильямса тогда и только тогда, когда

-К.

Теорема 4.3 дает возможность сформулировать критерий К

- 15

- раскрашиваемости в терминах (К^) - сочетаний.

Теорема 6.5 Гиперграф Н-(Х/Ц'Я) К - раскрашиваем в смысле Нэш-Вильямса тогда и только тогда, когда для любой вершины х&Х кенигово представление ¿(Мх) гиперграфа имеет (к, 1) - сочетание, насыщающее все вершины из ¿7 .

В некоторых случаях бывает необходимым найти наибольший суграф Н' гиперграфа Н с ^ £ , хотя <ГК(Н)>£ .

Эта задача решается в параграфе 7.

Теорема 7.1 Пусть К - натуральное число, £ - произвольное целое число, - гиперграф с ¡Х(и)]^

Тогда гиперграф Мц1-(У>&кг) является матроидом [I, 13,8] , где

Ы-К/ХСМ!)

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

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

Теорема 7.2 Обыкновенный граф содержит полный К - вершинный подграф тогда и только тогда, когда матроиды Мц и $ имеют хотя бы один общий цикл, причем включение ^ О ^ равносильно тому, что множество вершин Х(К) порождает полный К - вершинный подграф, где £ = лф2-/ , 5= -< .

Теорема 7.3 Обыкновенный граф / - (X, О) содержит полный К - вершинный подграф тогда и только тогда, когда мат-роид \M-4i содержит цикл с ^ элементами, причем

У^и о IV/ = является циклом матроида ^¿¿/^ тогда и только тогда, когда Х(У) порождает полный подграф в , где £ = „/ .

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

Теорема 7Л Обыкновенный граф ¿ = (ХУ1/) содержит полный

К- вершинный подграф тогда и только тогда, когда наименьший цикл матроида содержит - элементов, где

Параграф 8 содержит три алгоритма. Алгоритм 8.1 раскрашивает вершины гиперграфа в смысле Эрдеша - Хайнала для гиперграфов с неотрицательным К - дефицитом. Алгоритм 8.2 раскрашивает вершины гиперграфов с произвольным К - дефицитом. Трудоемкость алгоритма 8.2 несколько выше трудоемкости алгоритма 8.1. Алгоритм 8.3 раскрашивает ребра гиперграфа в смысле Нэш-Вильямса. Доказывается корректность всех алгоритмов.

Заметим, что трудоемкость алгоритмов полиноминальна.

ЗАКЛЮЧЕНИЕ

Задачи, рассмотренные в настоящей работе можно разделить на два класса. Это классические задачи - раскраска вершин гиперграфа в смысле Эрдеша - Хайнала, раскраска ребер гиперграфа в смысле Нэш - Вильямса (хотя формулировка задачи на гиперграфах принадлежит автору, первоначальную формулировку для графов можно считать классической) и задачи, поставленные автором - исследование К -дефицита, исследование свойства Ш(к,е) •

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

1. Айгнер M., Комбинаторная теория, M., Мир, 1982.

2. Берж К., Теория графов и ее применение. М., "Иностранная литература", 1962.

3. Горгос И.М., Хачатрян М.А., Сужение ребер гиперграфа и некоторые оценки хроматического числа, Сб. "Методы исследования экстремальных задач". Киев, 1981, с.16-21.

4. Ершов А.П., Кожухин Г.И., Об оценке хроматического числа связных графов. Докл. АН СССР, 1962, 142, №2, с.270-273.

5. Зыков A.A., Теория конечных графов, -Наука, Новосибирск, 1969.

6. Зыков A.A., Гиперграфы. Успехи мат. наук, 1974, №6, с.89--154.

7. Зыков A.A., О некоторых свойствах линейных комплексов. "Математический сборник, М., Изд. АН СССР, 1949, 24, №2,с.163-188.

8. Комбинаторный анализ. Задачи и упражнения., Под ред. Рыбникова К.А., М., "Наука", 1982.

9. Ope 0., Теория графов. М., "Наука", 1968.

10. Ю.Попков В.К., Представление графов. Препринт, 241, ВЦ СО АН СССР, Новосибирск, 1980.

11. П.Рингель Г., Янгс Дж., Решение проблемы Хивуда о раскраске карт., Сб. "Теория графов. Покрытия, укладки, турниры", М., "Мир", 1974, с.82-90.

12. Рингель Г., Янгс Дж., Решение проблемы Хивуда о раскраске карт: случай II., Сб. "Теория графов. Покрытия, укладки, турниры". М., "Мир", 1974, с.91-113.

13. Уилсон Р.Дж., Введение в теорию графов., -М., Мир, 1977.

14. Хачатрян М.А., 0 сужениях гиперграфа, сохраняющих дефициты., Сб. "Графы, гиперграфы и дискретные оптимизационные задачи", -Кишинев, "Штиинца", 1982, с.173-178.

15. Хачатрян М.А., Оценка хроматического числа гиперграфа и некоторых его суграфов. Сб. "Графы, гиперграфы и дискретные оптимизационные задачи". Кишинев, "Штиинца", 1982, с.179-184.

16. Хачатрян М.А., Обобщение дефицита и некоторые приложения, Сб. "Исследование операций и программирование", Кишинев, "Штиинца", 1982, с.168-172.

17. Харари Ф., Теория графов, М., "Мир", 1973.

18. Шнейдер А.А., Задачи на графы. Сб. "Алгоритмы решения логико-комбинаторных задач", Минск, 1979, с.102-105.

19. Appel К., Haken W., Koch J. Evry planar map is four colorable, 111. Math. J. № 21, 1977, p. 429-567.

20. Berge C. Graphes and hypergraphes, Amsterdam, 1975*

21. Borodin O.V., Kostochka A.V. On an Upper Bound of a Graphs Gromatic Number, depemding on the Graphs Deree and Density. Jurnal of comb. Teory Series В., 23(1977), p. 247-250.

22. Brooks R.L. On Coloring the Nodes or Network. Proc. Cambridge Ph: 1 . Soc., 60, 1946, p. 355-451.

23. Heawod P.J., Map coloring theorem. Quart. J. Math. Oxford, Ser. 2, 24(1890), p. 332-338.

24. Heffter L. Uber das Problem der Nachabargebiete. Math. Ann. 38. 1891, p. 477-508.

25. Szekeres G., Wilf H.S. An inequality for the cromatic number of graph. J. Combinatorial Theory, 4(1968) p.1-3.

26. Seymour P.D. On the two-colloring of hyporgraphs. Quart. J.- 99

27. Math., Oxford (3), 25 (1974), p. 303-312.

28. Tomescu I. Sur le problème du colorage de graphes généralisés. C.R. Ac.Se. Paris, 26?, 1968, p. 250-252.

29. Lor6a M. Hypergraphes et matroides. Cah. Cent.etud. rech. oper., 1975, 17, p. 2-4.29.bovasz L. A Generalisation of Konigs. Teorem. Acta Math. A с.Se.Hungaric al, 21, 1970, p. 443-446.

30. Lowler E.L. Matroid Intersection Algorithms, Mathematical Programming, 9(1975), P* 31-56.

31. Lowrens G. Govering the vertex Setof Graph with subgraphs of smoller degree Duscrete Math, 21(1978) p. 64-68.

32. Nash-Williams C.St.J.A. Decomposition of Finit Graphs into Forests., J.of London Math. Soc., 39, 1964, p.12.33»Edmonds J. Minimum Partition of a Matroid in to Independent

33. Subsets. Journal of Res. N.B.S.69, B.I965, p.67-72. 34,Хачатрян M.А., Сужение, К-дефицит и раскраска гиперграфов., "Кибернетика", 1983, № б, с. 19-22.