авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Условия существования непрерывных расписаний

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

Магомедов Абдулкарим Магомедович УСЛОВИЯ СУЩЕСТВОВАНИЯ НЕПРЕРЫВНЫХ РАСПИСАНИЙ 01.01.09 Дискретная математика и математическая кибернетика

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

Махачкала – 2011

Работа выполнена на кафедре дискретной математики и информатики ГОУ ВПО “Дагестанский государственный университет”

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

Официальные оппоненты: доктор физико-математических наук, профессор Валерий Николаевич Шевченко, доктор физико-математических наук, профессор Владимир Рубенович Хачатуров, доктор физико-математических наук, профессор Эдуард Николаевич Гордеев

Ведущая организация: Государственное образовательное учреждение высшего профессионального образования “Московский энергетический институт (тех нический университет)”

Защита диссертации состоится в часов на заседании диссертационного совета Д 002.017.02 при учреждении Рос сийской академии наук Вычислительном центре им. А. А. Дородницына РАН (119333, г. Москва, ул. Вавилова, 40, конф. зал).

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

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

Учный секретарь е диссертационного совета, доктор физико-математических наук В.В. Рязанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Основное внимание в диссертации уделяется вопросам существования и построения так называемых непрерывных расписаний. Суть задачи о непрерывном расписании заключается в жстком уплотнении матрицы е с элементами 0, 1,..., n, в каждом столбце которой ненулевые элементы попарно различны, в преобразовании е к матрице тех же размеров, где:

е • набор элементов к каждой строке такой же, что в соответствующей строке исходной матрицы;

• в каждом столбце ненулевые элементы попарно различны;

• ненулевые элементы в каждой строке размещены в подряд идущих ячейках.

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

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

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

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

новое доказательство теоремы об NP-полноте задачи о 3-раскраске графа;

формулировка полиномиальной подзадачи известной NP-полной потоковой задачи;

обобщение знаменитой теоремы Петерсена о разбиении регулярного графа чтной степени на 2-факторы 1) и т.д.

е Исходными для исследования явились результаты ряда авто ров: S. A. Even, A. Itai, A. Shamir, S. Sahni, В.В. Шкурба, Т. А. Танаев, В. А. Струсевич, Ю. Н. Сотсков, D. R. Fulkerson, O. A. Gross и др.



Важные результаты по теории расписаний получены также сле дующими авторами: С.В. Севастьянов, В.А. Перепелица, Э.Х. Гимади, В.М. Котов, В.В. Топорков, А.В. Пяткин, А.С. Асратян, Р.Р. Камалян, C.J. Casselgren, K. Giaro, H.M. Hansen, D. Hanson, C.O.M. Loten, B. Toft, В.В. Сервах, А.А. Лазарев и др.

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

Целью работы является исследование условий существования жсткого уплотнения и разработка алгоритмов построения непрерывных е расписаний путм анализа структурных свойств различных классов рас е писаний, позволяющих определить статус сложности задачи и, в случае Petersen J. Die theorie der regularen graphen // Acta Math. – 1891. – 15. – P. 193–220.

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

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

Новые методы и подходы: метод компьютерной формулировки рекур рентных соотношений (гл. 1);

метод построения непрерывного расписания длительности 4 (гл. 3), метод вычисления бездефектного потока, модифи кация метода 2-факторизации (гл. 5), а также новый подход к вычислению наибольшей плотности подграфа (гл. 6).

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

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

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

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

2. Условия существования расписаний учебных занятий, удовлетво ряющих заданным ограничениям на количество аудиторий, и алгоритм раз биения исходных данных по “дням недели” и “академическим часам”.

3. Доказательство NP-полноты задачи о непрерывном расписании и задачи уплотнения (0,1)-матрицы. Структура непрерывного нагруженного расписания.

4. Условия существования непрерывного нагруженного расписания длительности 4.

5. Модификация теоремы о 2-факторизации регулярного графа.

6. Теорема о бездефектном потоке и процедура проверки его суще ствования.

7. Условия и алгоритм уплотнения для семейства, состоящей из предписаний мощности 2, m() 2 и m().

8. Доказательство непланарности простого (6, 3)-графа. Построение примера простого (6, 3)-графа, не допускающего рберной раскраски в два е цвета, где в каждой вершине степени 3 представлен только один цвет, а в каждой вершине степени 6 каждый из двух цветов представлен три раза.

9. Доказательство разрешимости за полиномиальное время задачи о непрерывном расписании для семейства 2-предписаний.

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

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

Всесоюзная научная конференция по моделированию и оптимизации учебного процесса с использованием ЭВМ (Московский Энергетический Институт, 1985);

Всесоюзный семинар “Системное моделирование произ водства, распределения и потребления” (Воронеж, 1986);

Всероссийская научно-методическая конференция “Компьютерные технологии в высшем образовании” (Санкт-Петербург, 1994);

Международный симпозиум “Ин теллектуальные системы” (МГТУ им. Баумана, Махачкала, 1994);

Всерос сийская научно-техническая конференция “Современные информационные технологии в управлении” (Махачкала, 2003);

Международная конферен ция “Современные проблемы математики” (Махачкала, 2004);

XIV меж дународная конференция “Проблемы теоретической кибернетики” (Пенза, 2005);

IX Международный семинар “Дискретная математика и е приложе е ния”, посвященный 75-летию со дня рождения академика О. Б. Лупанова (МГУ, 2007);

V международная конференция по математическому мо делированию, посвященная 75-летию академика В. Н. Монахова (Якутск, 2007);

Всероссийская научно-практическая конфереренция “Информаци онные технологии в профессиональной деятельности и научной работе” (Йошкар–Ола, 2008);

XV международная конференция “Проблемы тео ретической кибернетики” (Казань, 2008);

X Белорусская математическая конференция (Минск, 2008);

IV Всероссийская конференция “Проблемы оптимизации и экономические приложения” (Омск, 2009);

VIII Междуна родная научная конференция “Дискретные модели в теории управляющих систем” (МГУ, 2009);

III Всероссийская научная конференция “Методы и средства обработки информации” (МГУ, 2009);

Международная научная конференция ”Дискретная математика, алгебра и их приложения” (Минск, 2009);

International conference “Optimization and applications” (Petrovac, Montenegro, 2009);

XVIII международная школа-семинар “Синтез и слож ность управляющих систем” им. академика О. Б. Лупанова (Пенза, 2009);

X международная школа-семинар “Дискретная математика и приложения” (МГУ, 2010);

XXIII Международная научная конференция “Математиче ские методы в технике и технологиях” (Саратов, 2010).

Диссертация прошла апробацию на заседаниях семинаров: отдела ма тематики и информатики Дагестанского научного центра РАН 11.02. (руководитель И. И. Шарапудинов);

отдела математических проблем рас познавания и методов комбинаторного анализа сектора математических методов распознавания и прогнозирования ВЦ РАН 20.04.2010 (руководи тель В. К. Леонтьев);

кафедры математической кибернетики факультета ВМиК МГУ 22.05.2009 и 23.04.2010 (руководитель А. А. Сапоженко), вузов г. Махачкала 23.11.2010 (руководитель А. К. Рамазанов).

Публикации. По теме диссертации автором опубликованы три учеб ных пособия и 68 статей (включая тезисы и депонированные статьи).

В журналах из списка ВАК опубликованы 12 статей, три компьютер ные программы автора зарегистрированы в Федеральной службе по интел лектуальной собственности, патентам и товарным знакам (РОСПАТЕНТ).

Структура и объем диссертации. Диссертация состоит из введе ния, шести глав, содержащих в совокупности 19 параграфов, заключения и списка литературы (119 наименований). Полный объем диссертации 183 страницы.

Благодарности. Выражаю глубокую благодарность А.А. Сапоженко за постоянное внимание к работе. Считаю своим долгом поблагодарить В.К. Леонтьева, А.А. Вороненко и И.И. Шарапудинова за ценные советы и рекомендации.

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

Формулировка задачи. Определения и обозначения. Ис следуется задача о расписании обслуживания множества требований N = {1,..., n} в системе приборов L = {1,..., l}: статус сложности, усло вия существования, эффективные алгоритмы построения. Информация к расписанию задана семейством = { 1,..., l } предписаний i неупо рядоченных наборов (мультимножеств) с элементами из множества N :

каждый i-й прибор должен выполнить операцию единичной длительно сти над каждым элементом из i, i L;

условия частичного предшество вания отсутствуют, в каждый момент времени каждое требование обслу живается не более чем одним прибором и каждый прибор обслуживает не более одного требования (условие неразделяемого доступа). Количество вхождений элемента j N в i обозначим через rep i j;

rep j = rep i j, iL m = m() = max rep j.

j Элементы множества N удобно называть буквами;

(l m)-матрицу с элементами из множества { 0, 1,..., n } будем называть расписанием для семейства, если (1) в каждой i-й строке буквенные элементы состав ляют i ;

(2) в каждом столбце буквенные элементы попарно различны.

Расписание будем называть непрерывным, если в каждой строке буквы размещены в подряд идущих ячейках. Уточним понятие жсткого уплот е нения: жстким уплотнением (или, кратко, уплотнением) будем называть е преобразование расписания к непрерывному виду с соблюдением свойств (1)–(2).

Всюду в дальнейшем предполагается, что выполнены неравенства |i | m(), 1 i l, обеспечивающие существование расписания дли тельности m(). Если rep 1 = · · · = rep n, то семейство и соответству ющие расписания будем называть нагруженными. Наборы (предписания) мощности k будем называть кратко k-наборами (предписаниями).

Сформулируем задачу о непрерывном расписании:

существует ли непрерывное расписание длительности m() для семейства предписаний ?

Семейство будем рассматривать как гиперграф с множеством вер шин N, в каждом ребре i которого вершина из N может присутство вать несколько раз. Для наглядности будем применять двудольное пред ставление гиперграфа, для чего соотнесем семейству двудольный ассо циированный граф G = (X, Y, E) : X = {x1,..., xn }, Y = {y1,..., yl }, в котором количество рбер, соединяющих вершины xj X и yi Y, е равно repi j. Отождествляя номер единицы времени обработки тре бования xj прибором yi и номер цвета ребра (xj, yi ), получим экви валентную задачу о рберной раскраске графа G = (X, Y, E). Если е |1 | = · · · = |l | = 2, то для каждого i = (i1, i2 ) заменим в дву дольном ассоциированном графе конструкцию из рбер (xi1, yi ), (xi2, yi ) и е вершины yi одним новым ребром (xi1, xi2 ). Полученный граф G = (X, E) назовем графом, ассоциированным с. Если для степеней всех вершин x X и y Y двудольного графа G = (X, Y, E) выполнены ограниче dG y b B, где a, b {, =};

A, B Z +, то будем ния вида dG x a A, говорить, что G является (aA, bB)-графом;

знак = подразумевается по умолчанию;

если значения dG x или dG y безразличны, применяются записи (, bB) или (aA, ) сответственно.





Правильной рберной раскраской графа G цветами 1, 2, 3,... назы е вается отображение f : E(G) {1, 2, 3,... }, такое, что f (e1 ) = f (e2 ) для каждой пары смежных рбер e1 и e2. Если для каждой вершины гра е фа цвет инцидентных рбер образуют некоторый интервал, правильная а е рберная раскраска графа цветами 1, 2, 3,... называется интервальной.

е Интервальная раскраска цветами из множества {1, 2,..., t} называется ин тервальной t-раскраской, если каждый из цветов этого множества присво ен хотя бы одному ребру. Через (G) обозначается наибольшая степень вершины графа G.

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

В главе 1 рассмотрены вопросы построения, перечисления и интер претации расписаний различных типов. Центральное место отведено во просу сложности задачи о непрерывном расписании. Публикация резуль татов: § 1.1 – [12];

§ 1.2 – [8], [5], [34], [14];

§ 1.3 – [15];

§ 1.4 – [47].

В § 1.1 семейство предписаний к расписанию задано двудольным гра фом G = (X, Y, E), в котором множество преподавателей Y разбито на несколько подмножеств, каждому из которых соотнесено целое положи тельное число, количество допустимых аудиторий. Исследуются условия разбиения множества рбер E на подмножества ( дни недели ), каждое из е которых, в свою очередь, допускает разбиение на паросочетания ( акаде мические часы ) с соблюдением заданных ограничений на мощности на боров рбер, инцидентных заданным подмножествам из Y ;

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

Через IG W обозначим множество рбер, инцидентных в графе е G = (V, E) множеству W V ;

E(x, y) набор параллельных рбер с е концами в вершинах x и y.

Задача о двухстадийном расслоении Условие. Заданы целые положительные числа p, q,, 1,..., и связ ный (pq, pq)-граф G = (X, Y, E);

множество Y разбито на подмножества Y1,..., Y.

Вопрос. Существует ли двухстадийное расслоение множества рбер E? е Другими словами, существует ли разбиение множества E на такие подмно жества E1,..., Ep, что каждое Ei (1 i p) является набором простых рбер и допускает разбиение на полные паросочетания Mi,j множества X е с множеством Y (1 j q), в каждом из которых количество рбер, е инцидентных вершинам множества Yk, не превышает k (1 k ) ?

Теорема 1.1.1. Для существования двухстадийного расслоения множества рбер E графа G = (X, Y, E) необходимо и достаточно вы е полнение соотношений |E(x, y)| |IG Yk | p, dG x = pq, dG y pq, pqk для всех x X, y Y и 1 k.

В § 1.2 доказана NP-полнота задач о непрерывном расписании и об уплотнении (0,1)-матрицы.

Теорема 1.2.1. Задача о непрерывном расписании NP-полна при n 2.

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

Теорема 1.2.2. Задача о непрерывном (l m)-расписании остается NP-полной и в следующих двух случаях: 1) когда требуется, чтобы в каждой строке равные буквы размещались рядом;

2) когда количество буквенных элементов в строке не превышает m/2.

Известно2), что задача о существовании у двудольного графа G = (X, Y, E) интервальной -раскраски NP-полна;

с другой стороны, каждый двудольный граф G = (X, Y, E) с |X| = 1 обладает очевидной ин тервальной -раскраской. Следующая теорема уточняет, при каком наи меньшем значении |X| задача об интервальной -раскраске приобретает содержательный характер.

Теорема 1.2.3. Задача об интервальной -раскрашиваемости дву дольного графа G = (X, Y, E) NP-полна при |X| 2.

Доказательство NP-полноты известной задачи Раскрашиваемость графа в три цвета, связанной со знаменитой проблемой четырех красок, получено Стокмейером Л. Ю.3) В § 1.2 приведено новое доказательство NP полноты данной задачи.

Как известно, задача о преобразовании (0,1)-матрицы путем переста новки столбцов к виду с размещением единиц в каждой строке в подряд идущих ячейках разрешима за полиномиальное время4).

Уплотнение (0, 1)-матрицы Севастьянов, С. В. Об интервальной раскрашиваемости рбер двудольного графа // Методы дис е кретного анализа. – 1990. – Т. 50. – C. 61–72.

Stockmeyer, L. J. Planar 3-colorability is NP-complete // SIGACT News. – 1973. – Vol. 5. – No. 3. – P. 19–25.

D. R. Fulkerson, O. A. Gross. Incedence matrices and interval graphs // Pacic J. Math. – 1965. – 15.

– P. 835–855.

Условие. Заданы целые неотрицательные l, m, n и (l m)-матрица M с элементами 0 и 1, каждый столбец которой содержит точно n единиц.

Вопрос. Существует ли (l m)-матрица, каждый столбец и каждая строка которой содержит в точности то же количество единиц и нулей, что и соответствующий столбец или строка матрицы M, при этом в каждой строке все единицы расположены в подряд идущих ячейках?

Теорема 1.2.5. Задача Уплотнение (0, 1)-матрицы NP-полна.

Набор всех буквенных элементов строки, размещенных в подряд иду щих ячейках, назовем серией. Лестницей (l m)-расписания называется набор серий с суммарной длиной m и таких, что позиции элементов серий заполняют интервал [1..m]. Доказано, что размещение буквенных элемен тов в нагруженном непрерывном расписании образует набор лестниц.

В конце § 1.2 показано, что задача, возникающая при эксплуата ции параллельных каналов передач, сводится к задаче уплотнения (0,1) матрицы.

В § 1.3 полупустой цикл нагруженного расписания чтной длительно е сти для семейства 2-предписаний определяется как замкнутая ломаная из чередующихся вертикальных и горизонтальных отрезков, в угловых точ ках которой попеременно размещаются 0 и буква (одна и та же для данного цикла);

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

В § 1.4 рассмотрена задача компьютерного подсчта расписаний с е разделяемым доступом. Пусть n учебных групп пронумерованы по прин ципу постепенной градации специализации, так, что для любых двух групп, номера которых отличаются точно на единицу, может быть прочитана лек ция длительностью в один академический час. Кроме лекционного типа, допускаются еще занятия семинарского типа, каждое из которых прово дится в учебной группе и продолжается два академических часа. Расписа нию учебных занятий выделены академические часы 1,..., m. Если t и i обозначают соответственно номера академического часа и учебной группы соответственно, то: полузанятие упорядоченная пара (t, i), занятие неупорядоченный набор двух полузанятий вида (t, i), (t + 1, i) или (t, i), (t, i + 1);

расписание такой набор занятий, в котором каждое полузаня тие (t, i) включено точно в одно занятие;

1 i n, 1 t m. Задача:

вычислить количество различных расписаний.

Сформулированная задача встречается в литературе (и в олимиадах по программированию) в следующей формулировке: вычислить количе ство всевозможных покрытий матрицы M размеров m n плитками 1 2 без пропусков и перекрытий. Известны рекуррентные соотношения для случаев n = 2, 3 или 45). Создана компьютерная программа, исполь зующая метод динамического программирования, элементы символьных преобразований и арифметические действия со сверхбольшими целыми числами, способная составить систему рекуррентных формул и выполнить по ним соответствующие расчты. е Пусть задан вектор (k1,..., kn ) с наибольшим элементом i. В матрице M рассмотрим фигуру, образованную клетками Mk1,1..., Mm,1 ;

..., Mkn,n,..., Mm,n ;

количество покрытий данной фигуры и (в случае несимметричности) фигу ры, соответствующей вектору (kn,..., k1 ), обозначим некоторой заглавной буквой латиницы с индексом i. В качестве примера приведем рекуррент ные формулы, полученные компьютерным путем для случая n = 5 (конеч ной целью является вычисление значения Cm );

для удобства восприятия в таблице указаны векторы (i k1,..., i kn ).

Gi = Ai1 + Gi2 Ei = Ci1 + Fi 1 0 0 1 2 1 1 1 0 Hi = Ei + Fi1 + Hi2 Bi = Ci1 + Di 0 0 1 0 0 1 0 0 1 Ai = Gi1 + Fi1 + Ai2 + Bi Di = Ai1 + Bi 0 0 1 1 2 1 0 0 0 Fi = Ai1 + Hi1 + Ei1 Ci = Fi + Di + Bi1 + Ei1 + Ci 1 1 0 0 0 0 0 0 0 Через Smn обозначено количество покрытий для матрицы m n:

S1004 = 1154075100487723888159117233401976510843180361, S405 = 5568402462493067660191, S45 = 95, S1105 = 1551295864409116377994421907267945531905374726936928865464104.

В главе 2 рассмотрены условия существования непрерывного рас писания для нагруженного семейства p-предписаний, m() = 2p:

|1 | = · · · = |l | = p, rep 1 = · · · = rep n = m() = 2p.

Публикация результатов: § 2.1 [6], [15];

§ 2.2 [4], [6];

§ 2.3 – [5].

В § 2.1 определены два вида рберной раскраски. Пусть G = (X, Y, E) е – двудольный граф, ассоциированный с семейством. Правильная рберная раскраска графа G называется непрерывной, если для каждого е y Y цвет инцидентных рбер образуют подинтервал из [1..m]. Рберную а е е раскраску двудольного (qp, p)-графа G = (X, Y, E) в q цветов будем на зывать разбивающей q-раскраской (или q-раскраской), если каждой вер шине x X инцидентны по p рбер каждого цвета, а в каждой вершине е y Y представлен только один цвет.

Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ.

– М.: Мир, 1998. – 703 с.

Теорема 2.1.1. Для любого (4, 2)-графа G существует разбиваю щая рберная раскраска.

е Доказано, что из теоремы вытекает существование непрерывного рас писания для нагруженного семейства 2-предписаний, m() = 4. Таким образом, (qp, p)-граф G = (X, Y, E) всегда допускает q-раскраску в вы рожденном случае p = q = 2. Начало параграфа является точкой ветв ления исследования: продолжение параграфа посвящено направлению, определяемому равенством q = 2 при произвольном p;

другое направление когда p = 2, а q произвольно, получило развитие (и завершение) в § 5.1.

Задача о разбивающей 2-раскраске: для (2p, p)-графа G = (X, Y, E) требуется проверить существование рберной 2-раскраски, такой, что е любой вершине x X инцидентны p рбер каждого из двух цветов, а в е каждой вершины y Y представлен только один цвет.

Доказано, что для (2p, p)-графа G = (X, Y, E) следующие три за дачи эквивалентны: о разбивающей 2-раскраске, непрерывной раскрас ке и непрерывном расписании. В отличие от рассмотренного выше слу чая p = 2, в рассматриваемом контексте ответ на вопрос о существовании непрерывного расписания неоднозначен, как это видно из следующей тео ремы.

Теорема 2.1.2. Для любого p 2 найдется нагруженное семей ство p-предписаний = {1,..., l }, m() = 2p, такое, что непрерывное расписание для не существует.

В § 2.2 обсуждается природа препятствий к распространению на слу чай p 2 утверждения о существовании разбивающей раскраски, спра ведливого для (2p, p)-графа при p = 2. Принято ожидать, что в случае планарных графов сложность задач раскраски, вообще говоря, уменьша ется. В связи с проблемой уплотнения (l6)-расписания для нагруженного семейства 3-предписаний рассмотрен вопрос планарности ассоциирован ного (6, 3)-графа.

Теорема 2.2.1. Простой (6, 3)-граф G = (X, Y, E) непланарен.

Задача построения (6, 3)-мультиграфа, для которого разбивающая раскраска не существует, тривиальна. Например, таковым является граф, заданный списками смежных вершин: y1 (x1, x1, x1 ), y2 (x1, x2, x2 ), y3 (x1, x2, x2 ), y4 (x1, x2, x2 ).

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

GABD @FEC x4 u n GAB3 iii GAB @FED xC @FED C GABD @FEC kx x H kkknkn HH nnnnn  HH }  HHHeee uuns iiiHiiiikns uunns} ss nss } n ss} ss} e uukk kk n s } H niiii ui n H n Hn }}  nnnH sse}}kiukk nHnH ss nnHnH ss }}  HH  }} nnnnnssssk}}eennnnssssH nnnnnssss}}}  HH ii}kkke uuu H HH n s HH } n  iiiii k n e s u H GABD GFBC GFEC @FEC @FEC GFEC @FEC @FEC @FEC @FEC @FEC @ y9 @ y8 y7 y6 @ y5 y4 y3 y2 y y10 E inAi D kkABD nGABD sGABD nnABD GABD GABD GABD GABD } nn ii sss kk}} nn  s nn ssss }}   s kk n }i un ni Граф G0 : при любой 2-разбивающей раскраске c(y1 ) = c(y2 ), c(y3 ) = c(y4 ).

Он изображен на нижнем-правом рисунке и является комбинацией графа G0, изображенного слева, и четырех копий графа G0, изображен ного выше: G1, G2, G3 и G4. Доказательство опирается на свойства гра фов G0 и G0, сформулированные под соответствующими изображениями;

в этих формулировках цвета разбивающей раскраски обозначены -1 и 1.

s s •WWss G •aaWxWs xW s x aWs faxWW see j f axxx ss eeee •A`` yyy A qnnn P qq W P • uqq • • • efeeeeexjjs sjj• nnn W xxj ss zu yy z !! APP```!! AA nnnzzu PPP nnnyy WWW aa Wj x AyyP ! nnA qquq qqq •rrrfffaWssss efa W xs j j j aW sxx P` ! A  q uu n qyy  z jj r sssW qy n !yyynAnn!nuuuA z WW P •cccjsrrrfhaahhhh• s nnn qP ! `q ! Pqq` Az qqP  W nnnAAq!Puzzz` nnnn q yyyy  •y • • • •n •q 1  GAB2D GAB1D @FEC @FEC s fffWh GABD GABD @FEC @FEC yynuuuzP `` An qqqq y P  ! qqq ! P hW cchhrrraaW s y q u z n rs hh ! ff W nq   sh •hrrr ccc rraaffG n a a fWW a2 a1 r aa rr cc rrr W a { 1  ~~ f {  rr cc eeee  n eeeeee 1  ~~~ {{{ rr cc •    ne ee 1 ~~ {{ n n k k rrrc c r GABD {{{{ k k k @FEC GABD @FEC   GABD  @FEC GABD @FEC  ~ {{ n k c rc r n n kkk • k AS{ n kk b AG www  n b w  { kk GABD kSS tttt ff GABD k @FEC @FEC t GABDGGG  wwww zz h GABD @FEC B G zzzhwhh @FEC t k S k k { n n kkk tt z G w z S w z BG SS b t ff b1 f tfff hw ww GABD G tS t @FEC St GABD @FEC GG ffS fftttt f GABBDBhh Gzz @FECB GABD @FEC Sf fff BB G hhhh GGh zzz w h ff G c CXB zG C G ttS c1 ggGt zG GABD gG gg SS GABD @FEC Gg @FEC SS GABD BBXX GGG @FEC GABD @FEC ttg  zz G BBX G X S D d GG gg SS c2 hhhhhhvhh• m m m mv c2  DS B XX G 1 H d G g S hhhh mmmvv v BB XX G m vv  1 H ddd GG ggg SS hm SS G mmmm vvv SS BB XXXGG 1 H dddGG gg SS  • vv qqqq •Pi•w`wsPs•shhh!•wwwww iii  PP GAB2D GAB1D •vuqqvv| G @FEC @FEC |v B | XG g S GABD GABD @FEC @FEC vv  qqvvv 1 H || v  qq vv  q v|| iA PA u P `w• sh • d d uu q | d2 d1 PP iAi ``P!P!wAs ! w ii P u v i ` w  AwA qq u||ue qvvv uu eeee i P !Aw h!h ss PP AAii``PPwAww s ww  s hh ww i P ||e jjj •vvv eejuupppp • ! ` P ! ww |j j uu u PPA iiPA !hh iiiPP eeej uu www ss ! ee j ! ``` | j p u PA !iii !! w  •|||ppup P ssh PA www www hs i uu j p u Граф G0 : c(a1 ) = c(a2 ) или i jjjpp uu • • •peueeeeeeeee• • • jjjj pe u •puu jjjjj c(b1 ) = c(b2 ) при любой раз- e e ju jj uj бивающей 2-раскраске.

• G Простой (6, 3)-граф: 2 разбивающая раскраска не существует.

NP-полнота известной задачи Кубический подграф (о существова нии в заданном графе G = (V, E) непустого подмножества E E, такого, что в графе G = (V, E ) любая вершина имеет степень, равную 3 или 0) разве лишь в общих чертах объясняет сложность задачи о разбивающей раскраске (6,3)-графа. Следующие два замечательных результата проли вают свет на суть проблемы:

• А. В. Пяткин доказал6) NP-полноту задачи о существовании в (4, 3) графе G = (X, Y, E) кубического подграфа, включающего X.

• Полиномиальным сведением данной задачи к задаче об интервальной 6-раскраске (6,3)-графа A. S. Asratyan и C. J. Casselgren доказали7) е е NP-полноту.

В связи с NP-полнотой задачи о разбивающей рберной раскрас е ке, в § 2.3 построен метод динамического программирования для про верки существования непрерывных расписаний. Вспомогательная зада ча: для каждого из n-наборов (k1,..., kn ), kj [0,..., p], проверить су ществование у семейства подсемейства S, обладающего свойством repS j = kj j N.

Произвольно выберем набор (k1,..., kn ). Для 1,..., n [0,..., p], i L, обозначим через T [i, 1,..., n ] значение истинности утверждения: в семействе { 1,..., i } найдется подсемейство S такое, что repS j = j для каждого j N. Понятно, что ответ вспомогательной задачи определяет ся значением T [l, k1,..., kn ]. Приведем алгорим заполнения (n+1)–мерной таблицы T :

• T [1, 1,..., n ] = true (1 =... = n = 0) или (rep1 j = j, j N );

Для i = 2,..., l:

• T [i 1, 1,..., n ] = true T [i, 1,..., n ] = true;

• если T [i 1, 1,..., n ] = f alse, то (T [i, 1,..., n ] = true j j N и T [i 1, 1 repi 1,..., n repi n] = true).

repi j Теорема 2.3.1. Непрерывное (2n 2p)-расписание существует тогда и только тогда, когда T [2n, p,..., p] = true.

В главе 3 рассмотрены условия существования нагруженных непре рывных расписаний длительности 3, 4 и 5. Центральное место занимает уплотнение расписания длительности 4. Публикация результатов: § 3. [3];

§ 3.2 [7];

§ 3.3 [10].

Приведенная в § 3.1 классическая NP-полная задача Составление учебного расписания 8) остается NP-полной даже в случае 3-х уроков, Pyatkin, A. V. Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs // J. of Graph Theory. – 2004. – Vol. 47. – No. 2. – P. 122–128.

Asratian, A. S. Casselgren, C. J. Some results on interval edge colorings of (, )-biregular bipartite graphs // Department of Mathematics. – 2007. – Linkoping University S-581 83 Linkping, Sweden.

o S. Even, A. Itai, A. Shamir. On the complexity of timetable and integral multi-commodity ow problems / SIAM J. on Comp. – 1976. – V. 5. – No. 4. – P. 691–703.

если имеются ограничения на доступные часы. Доказано, что для нагру женного расписания M длительности 3 уплотнение существует тогда и только тогда, когда для семейства существует частичная трансвер саль (множество, включающее точно одну букву из каждого предписания длины 2 или 3), равная N.

Измельчением семейства = {i } будем называть такой набор букв, для которого j N.

rep j = repi j, i Если количество букв в каждой строке нагруженного (l m) расписания M принадлежит некоторому множеству Q, то будем говорить, l,m,n что M принадлежит классу PQ.

Коль скоро для нагруженного семейства предписаний расписание все гда существует, вместо задачи построения непрерывного расписания для исходного семейства предписаний удобно рассматривать эквивалентную за дачу уплотнения уже построенного нагруженного расписания. § 3.2 посвя l,4,n щен условиям уплотнения расписаний класса P{1,2,3,4}.

Зададим функцию-множество Q на множестве {1, 2, 3, 4}:

Q(1) = {0, 1}, Q(2) = {1, 2}, Q(3) = {2}, Q(4) = {2}, и определим ду l,4,n эт F = {F1,..., Fl } расписания M P{1,2,3,4} :

F = { (2)1,..., (2)n };

F i i ;

|Fi | Q(|i |);

1 i l.

l,4,n Теорема 3.2.1. Расписание класса P{1,2,3,4} допускает уплотнение тогда и только тогда, когда обладает дуэтом.

В теореме 3.2.2, обеспечивающей проверку выполнения условий тео ремы 3.2.1, используется следующая слоистая сеть N(M ), где u(e) и c(e) обозначают соответственно нижнее и верхнее потоковые ограничения по дуге e.

Множество вершин: s–источник, X = {x1,..., xn }, Y = {y1,..., yl }, t–сток;

множество дуг: {e = (s, xi ), u(e) = c(e) = 2};

{e = (xi, yj ), u(e) = 0, c(e) = min(2, repj i)};

{e = (yj, t), u(e) = min{Q(|j |)};

c(e) = max{Q(|j |)};

1 i n, 1 j l.

l,4,n Теорема 3.2.2. Матрица M класса P{1,2,3,4} тогда и только тогда обладает дуэтом, когда в сети N(M ) существует допустимый поток.

В § 3.3 рассмотрена задача уплотнения расписания длительно сти 5 без 1-предписаний. Следующая транспортная сеть Nk (M ) для l,m,n M P{k,mk,m}, 1 k m/2, используется не только в формулиров ке теоремы 3.3.1, но и в последующих главах. При определении элементов сети предполагается, что 1 i n, 1 j l:

• множество вершин: s (источник), X = { xi }, Y = { yj }, t (сток);

• множество дуг: {(s, xi )}, {(xi, yj )}, {(yj, t)};

• верхние потоковые ограничения (пропускные способности):

c(s, xi ) = m 2k;

c(xi, yj ) = repj i;

c(yj, t) = m 2k;

• нижние потоковые ограничения: u(s, xi ) = m 2k;

u(xi, yj ) = 0;

если |j | = k;

0, u(yj, t) = m 2k, если |j | = m k или m.

Замечание. Поскольку c(e) и u(e) целые положительные, то рассмат риваемые потоки можно считать целочисленными.

l,5,n Теорема 3.3.1. Нагруженное расписание M класса P{2,3,4,5} допус кает уплотнение тогда и только тогда, когда |i | = 4, 1 i l, и в сети N2 (M ) существует допустимый поток f.

В главе 4 рассмотрены условия существования непрерывного рас писания длительности m для нагруженного семейства = {1,..., l } с предписаниями длины k, m k и m, где k m/2 и m не кратно k (при k 1). Публикация результатов § 4.1 и § 4.2 [12].

В § 4.1 доказаны следующие две теоремы.

l,m,n Теорема 4.1.1. Для уплотнения матрицы M класса P{1,m1,m} необ ходимо и достаточно существование в сети N1 (M ) допустимого пото ка f.

Теорема 4.1.2. При нечтном m для уплотнения матрицы M клас е l,m,n са P{2,m2,m} необходимо и достаточно существование допустимого по тока f в сети N2 (M ).

§ 4.2 изучена природа трудностей, возникающих при уплотнении на l,m,n груженного расписания M класса P{k,mk,m} (m не кратно k). Каркас F (l m)-расписания M определяется как (l m)-матрица, обладающая сле дующими свойствами: 1) {Fj,k+1,..., Fj,mk } j ;

2) Fj,1 = · · · = Fj,k = Fj,mk+1 = · · · = Fj,m = 0, 1 j l;

3) множество букв каждого из столбцов k + 1,..., m k, равно N. Пристройка T расписания M определяется как (l m)-матрица, в которой: 1) в каждой i-й строке буквенные элементы образуют поднабор из i мощности |i | m + 2k;

2) T1,j = · · · = Tl,j = 0, k + 1 j m k;

3) множество букв каждо го из столбцов 1,..., k и m k + 1,..., m равно N.

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

l,m,n Теорема 4.2.1. Расписание M P{k,mk,m} обладает каркасом тогда и только тогда, когда существует пристройка.

l,m,n Теорема 4.2.2. Расписание M P{k,mk,m} обладает пристройкой тогда и только тогда, когда в сети Nk (M ) существует допустимый по ток.

l,m,n Пристройка T расписания класса P{k,mk,m} называется разбиваемой, если каждый 2k-буквенный набор строки пристройки допускает разбие ние на два k-набора, так, что семейство S, включающее как все исходные k-буквенные наборы отдельных строк, так и все вновь образовавшиеся на боры, допускает разбиение на два подсемейства, измельчение каждого из которых равно {(k)1, (k)2,..., (k)n}. Пристройка расписания не всегда яв ляется разбиваемой.

l,m,n Теорема 4.2.3. Расписание M P{k,mk,m} допускает уплотнение тогда и только тогда, когда M обладает разбиваемой пристройкой.

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

Сложность проблемы существования разбиваемой пристройки даже для случая пустого каркаса и k = 3, m = 2k = 6 уже рассматривалась в главе 2. При чтном m и k = 2 рассмотрение условий уплотнения матрицы е l,m,n класса P{k,mk,m} существенно усложняется, как будет видно из следующей главы.

В главе 5 рассмотрены связи задачи о непрерывном расписании для нагруженных семейств 2-предписаний (и их обобщений) с задачей факто ризации графа (и е обобщениями), а также с классической NP-полной е задачей о вычислении потока в сети с гомологичными дугами. Централь ное место занимает решение задачи о непрерывном расписании для нагру женного семейства предписаний длины 2, m 2 и m при чтном m.е Публикация результатов: § 5.1 [5], [53];

§ 5.2 [3], [15];

§ 5.3 [3], [15], [45].

Следующую теорему § 5.1 можно рассматривать в качестве комбина торной интерпретации теоремы Петерсена.

Теорема 5.1.1. Для любого нагруженного семейства 2 предписаний с чтным m() существует непрерывное расписание.

е Получена следующая модификация: двудольное представление ги перграфа G = (X, Y2 Y2r, E), где степень каждой вершины из X и Y2r равна чтному числу 2r, а степень каждой вершины из Y2 равна 2, до е пускает разбиение на r регулярных подграфов степени 2.

Теорема 5.1.2. Пусть A = {1,..., p } и B = {p+1,..., p+q } соответственно семейства 2r- и 2-наборов, заданных на множестве N.

Если repAB j = 2r j N, 1 r то для каждого i существует (пред)разбиение на r 2-наборов i,..., i, такое, что семейство 2-наборов 1 r 1 r R = {1,..., 1 ;

... ;

p,..., p ;

p+1,..., p+q } допускает (пост)разбиение на r подсемейств R1,..., Rr, удовлетворяю щих условиям: для каждого k = 1,..., r, k 1) repRk j = 2 j N ;

2) i Rk i {1,..., p}.

При произвольном предразбиении 2r-наборов i на 2-наборы объединение последних с j образует семейство R 2-наборов, для которого выполняется условие: repR j = 2r j N. Существование постразбиения семейства R на r подсемейств Rk, для каждого из которых repRk j = 2 j N, следу ет из теремы Петерсена. Но при этом, вообще говоря, при произвольном постразбиении найдутся 2-набора, полученные разбиением одного и того же i, но включенные в разные Rk1 и Rk2. Суть утверждения теоремы заключается в существовании такого предразбиения, при котором всегда существует постразбиение, обеспечивающее, в частности, и выполнение по следнего условия.

l,2r,n Теорема 5.1.3. Любое расписание M P{2,2r} допускает уплотне ние.

В § 5.2 рассмотрена структура непрерывного расписания класса l,m,n P2,m2,m и ассоциированного двудольного графа.

l,m,n При m = 0 (mod k) для непрерывного расписания M Pk,mk,m, k m/2, выполняется тождество Mi,k+1 = · · · = Mi,mk+1 = 0, |i | = k, если что существенно упростило формулировку условий существования непре рывного расписания в главе 4. При k = 2 и чтном m соответствующее е тождество не имеет места. По этой причине необходимо проверить, суще ствует ли семейство = {1,..., l }, удовлетворяющее условиям:

i i ;

1) i l;

m 4, если |i | {m 2, m};

|i | = 2) 1 i l;

если |i | = 2, 0 или 2, = {(m 4)1,..., (m 4)n}.

3) В двудольном графе G = (X, Y, E), ассоциированном с расписанием l,m,n M P{2,m2,m}, обозначим подмножества множества Y, образованные вер шинами степени 2, m 2 и m, через Y2, Ym2 и Ym соответственно. Если E подмножество множества E, такое, что каждой вершине множества X Ym2 Ym инцидентны m 4 рбер из E, а каждой вершине множества е Y2 либо 0, либо 2 ребра из E, то порожденный множеством E подграф графа G будем называть скелетом графа G.

l,m,n Теорема 5.2.1. Для уплотнения расписания M P{2,m2,m} необхо димо и достаточно существование скелета у ассоциированного двудольного графа G.

§ 5.3 посвящен проверке существования скелета. Пусть N0 (M ) сеть, которая получается внесением в сеть N2 (M ) следующих изменений:

0, если m нечтно;

е если |j | = 2, то u(yj, t) = 0 и c(yj, t) = 2, если m чтно.

е Пару дуг e = (xp, yj ) и e = (xq, yj ), инцидентных вершине yj Y2, назо вем гомологичной парой. Целочисленный поток f в сети N0 (M ) называется бездефектным, если f (e ) = f (e ) для всех гомологичных пар. Если для го мологичной пары дуг e и e, инцидентных вершине yj Y2, f (e ) = f (e ), вершину yj назовем f -дефектом;

множество f -дефектов обозначим fD.

Доказано, что для существования уплотнения расписания l,m,n M P{2,m2,m} необходимо и достаточно существование в сети N0 (M ) потоков: допустимого при нечтном m и бездефектного е при чтном m.

е Проверка существования допустимого потока осуществля ется стандартной процедурой;

остается рассмотреть случай чтного m.

е Показано, что рассматриваемая подзадача известной NP-полной задачи Целочисленный поток в сети с гомологичными дугами 9) разрешима за полиномиальное время.

Sahni, S. Computationally related problems // SIAM J. Comput., – 1974. – No 3. – P. 262–279.

Рассмотрим разбиение множества дуг E ассоциированного с расписа нием M графа G(M ) на два непересекающихся множества, индуцирован ное потоком f в сети N0 (M ):

fk = {e E | f (e) = k};

k = 0, 1.

Пусть v внутренняя вершина некоторого пути T в графе G. Будем говорить, что для вершины v выполнено свойство чередования, если из любых двух последовательных рбер пути T, инцидентных вершине v, одно е f1 ;

если Y20 Y принадлежит f0, другое множество всех вершин графа G(M ), для которых свойство чередования нарушено, путь T будем называть (Y20, f )–чередующимся.

допустимый поток в сети N0 (M ) и Теорема 5.3.1. Пусть f fD =. Если в сети N0 (M ) существует некоторый бездефектный поток, то из произвольной вершины y fD в множество fD {y} найдется (Y20, f )–чередующийся путь.

Пусть необходимое условие уществования бездефектного потока в се ти N0 (M ) выполнено: допустимый поток f существует. Изложим алгоритм проверки существования бездефектного потока в N0 (M ).

Если fD =, то бездефектный поток найден;

пусть fD =.

Пока fD =, выполнять действия:

выбрать произвольную вершину yj fD ;

если (Y20, f )-чередующийся путь из yj в множество fD {yj } суще ствует, то поменять для дуг e пути значения f (e) на 1 f (e), удалить концевые вершины пути из fD (и включить их в Y20 ), иначе завершить алгоритм с сообщением об отсутствии безде фектного потока.

В главе 6 рассмотрены семейства из 1- и 2-предписаний. Цен тральное место отведено решению задачи о непрерывном ненагруженном расписании нечтной длительности для семейства 2-предписаний. Публи е кация результатов: § 6.1, § 6.2 [2];

§ 6.3 [9];

§ 6.4 [2], [55].

В § 6.1 рассмотрены нагруженные семейства 1- и 2-предписаний, по лученные видоизменением приведенных в § 5.1 семейств с простой струк турой и с предопределенным существованием непрерывных расписаний.

Пусть S семейство наборов, заданных на множестве N ;

через N (S) обозначим количество различных букв в наборах семейства S.

Теорема 6.1.1. Пусть W1 и W2 такие семейства из 1- и 2 предписаний соответственно, что семейство W = W1 W2 является нагруженным. Непрерывное (l m)-расписание для семейства W суще ствует тогда и только тогда, когда существует непрерывное (l m) расписание для W2 : если m чтно или |N (W1 )| = n.

е Для нечтного m остается рассмотреть задачу для нагруженного се е мейства W при условиях: |W1 | = n, |N (W1 )| n, ограничившись при этом семейством W2, |W2 | = pn. Показано, что при |N (W1 )| = n 1 и m = непрерывное расписание существует, а для случая |N (W1 )| = n 2 по лучены необходимые и достаточные условия существования непрерывного расписания.

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

Теорема 6.1.2. Если m = 5, W1 = {(3)1, 2, 3,..., n}, W2 = {(2)1, (5)2, (5)3, (4)4,..., (4)n}, то непрерывное (l m)-расписание для семей ства W = W1 W2 существует тогда и только тогда, когда в ассо циированном с W2 графе вершины v1, v2 и v3, соответствующие буквам 1, 2 и 3, принадлежат одной и той же компоненте.

Характерные для нечтного е m = 2p + 1 проблемы про являются, в общих чертах, в пограничных условиях :

|W1 | = n;

repW1 j {0, 1, p} j N, уже при p = 2. Доказатель ство теоремы 6.1.1 опирается на критерий 2-факторизации графа. Для рассматриваемого случая соответствующий критерий неизвестен;

его формулировка для графа G, ассоциированного с W2, является основной целью § 6.2.

Разбиение графа G = (V, E) на остовные рберно е непересекающиеся подграфы G1 = (V, E1 ) и G2 = (V, E2 ) обозначим h = {Gi = (V, Ei ), i = 1, 2};

ch (v) = dG1 v dG2 v, eh (G) = |E1 | |E2 |.

Разбиение h будем называть компромиссным, если |ch (v)| 1 v V и eh (G) = 0.

Граф G = (V, E) будем называть частично-4-регулярным, если мно жество вершин допускает такое упорядочение V = {v1,..., vn }, что при некотором степень вершины vi равна: 5 при 1 i 2;

2 при 2 i 3;

4 при 3 i n. Предполагая, что вершины упорядочены нужным обра зом, частично-4-регулярный граф G будем обозначать G = (V, V, E), где V = {v1,..., v2 }.

Теорема 6.2.1. Связный частично-4-регулярный граф всегда допус кает компромиссное разбиение. Несвязный частично-4-регулярный граф G = (V, V, E) допускает компромиссное разбиение тогда и только тогда, когда в каждой связной компоненте графа G, не содержащей вершин мно жества V, количество рбер чтно.

е е Теорема 6.2.2. Пусть W = W1 W2 – такой набор 1- и 2 предписаний, что |W1 | = n и repW1 j = {0, 1, 3} для любого j N. Если частично-4-регулярный граф, ассоциированный с семейством W2, явля ется связным и остовные рберно-непересекающиеся подграфы G1 и G е в некотором компромиссном разбиении графа G также связны, то для набора предписаний W существует непрерывное расписание.

В отличие от § 6.1–§ 6.2, результаты § 6.3–§ 6.4 относятся к случаю ненагруженных семейств. В § 6.3 рассмотрена задача о непрерывном рас писании длительности 5 для семейства 2-предписаний.

Если k-й столбец (l m)-расписания содержит лишь буквы, встре чающиеся в расписании точно m раз, то расписание M будем называть k-разреженным. Показано, что непрерывное (l 5)-расписание для семей ства 2-предписаний допускает преобразование к 3-разреженному непре рывному расписанию.

Теорема 6.3.1. Непрерывное расписание для семейства 2 предписаний, m() = 5, существует тогда и только тогда, когда | | 2N ( ) для каждого.

В § 6.4 найдены необходимые и достаточные условия уплотнения расписа ния для семейства 2-предписаний в случае произвольного нечтного m.е Граф G = (V, E ), где V = {v1,..., vn }, E = {e1,..., el } (и его двудольное представление), будем называть графом непрерывного расписа ния, если для семейства предписаний, ассоциированного с G, существует непрерывное (l m)–pасписание, где m = max1 i n dG vi. Введем понятие одностороннего расписания: 1-разреженное (3-разреженное) непрерывное (l 3)-расписание для семейства называется левосторонним ( право сторонним ).

Теорема 6.4.1. (2, 3)-граф G = (X, Y, E) является графом непре рывного расписания тогда и только тогда, когда существует полное па росочетание множества X с множеством Y.

Теорема 6.4.2. Пусть G = (X, Y, E) (2, 3)-граф, ассоции рованное с G семейство 2-предписаний. Следующие утверждения равно сильны: G является графом непрерывного расписания;

существует пол ное паросочетание множества X с Y ;

для семейства существуют од носторонние расписания.

Будем говорить, что двудольный граф G = (X, Y, E) является (k1, k2 )-графом, если dG x = k1 x X, maxyY dG y = k2.

Пусть p – целое положительное и в (2, 2p + 1)-графе G = (X, Y, E) существует множество E E, такое, что каждой вершине x X инци дентно точно одно ребро, а каждой вершине y Y – не более p рбер е множества E. Подграф G = (X, Y, E ), порожденный множеством рбер е E, называется p-каркасом графа G, если имеется вершина y Y, такая, что |IG {y}| = p.

Пусть P = {1, 2,..., p} и задана рберная p-раскраска C : E P гра е фа G = (X, Y, E), где для каждого i P имеется ребро e E : C(e) = i.

Количество рбер i-го цвета, инцидентных вершине v, обозначим c(v, i).

е Рберная p-раскраска (2, 2p + 1)-графа G = (X, Y, E) называется выров е ненной, если: 1) в каждой вершине x X представлен точно один цвет;

2) для всех i, j P и y Y : если dG y 2, то |c(y, i) c(y, j)| 1.

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

Лемма 6.4.3. Пусть заданы целое положительное p и (2, 2p + 1) граф G = (X, Y, E). Если |S| p |(S)| для любого подмножества S множества X, то граф G обладает согласованными p-каркасом и p раскраской. Приведем основной результат § 6.4.

Теорема 6.4.3. Пусть семейство 2-предписаний i, заданных на множестве N ;

m() = 2p + 1, где p некоторое целое положитель ное число. Непрерывное (l m)-расписание для семейства существует тогда и только тогда, когда | | p |N ( )|,.

Указан новый подход к решению задачи нахождения наибольшей плотности подграфа. С применением полученного результата доказано, что проверка условий теорем 6.3.1 и 6.4.3 выполнима за полиномиальное время.

Литература Основные публикации автора по теме диссертации 1. Магомедов, А. М. Двумерная графика в проектах Delphi [Текст] // Вестник Дагестанского научного центра РАН. – 2004. – N 18. – С. 5–8.

2. Магомедов, А. М. Размещение неделимых 2-слов в матрице как за дача факторизации графа [Текст] // Вестник Дагестанского научного центра РАН. – 2006. – N 23. – C. 5–14.

3. Магомедов, А. М. Жесткий директивный срок для многопроцес сорного расписания без прерываний и отношений предшествования [Текст] // Вестник Дагестанского научного центра РАН. – 2007. – N 28.

– C. 5–11.

4. Магомедов, А. М. К вопросу оптимизации расписания [Текст] // Известия Волгоградского государственного технического университе та: межвуз. сб. науч. ст. – 2008. – Вып. 5. – N 8(46). – С. 40–43.

5. Магомедов, А. М. Уплотнение расписания с директивным сроком, кратным количеству занятий каждого преподавателя [Текст] // Ма тем. заметки. – 2009. – Т. 85. – N 1. – C. 65–72.

6. Магомедов, А. М. К вопросу о рберной раскраске двудольного гра е фа [Текст] // Дискретная математика. – 2009. – Т. 21. – Вып. 2. – С. 153–159.

7. Магомедов, А. М. Дефрагментация таблицы перестановок из четы рех столбцов [Текст] // Дискретная математика. – 2009. – Т. 21. – Вып. 4. – С. 95–104.

8. Магомедов, А. М. Непрерывное расписание для специализирован ных процессоров без отношения предшествования [Текст] // Вестник Московского Энергетического Института. – 2009. – N 5. – С. 14–17.

9. Магомедов, А. М. Условия существования непрерывных расписа ний длительности пять [Текст] / А. М. Магомедов, А. А. Сапоженко // Вестник МГУ, сер. Вычислительная математика и кибернетика. – 2010. – Т. 34. – N 1. – C. 39–44.

10. Магомедов, А. М. Непрерывная -раскраска некоторых двудоль ных графов G с (G) = 5 и 6 [Текст] / А. М. Магомедов, Т. А. Маго медов, М. А. Магомедов // Вопросы современной науки и практики.

Университет им. В. И. Вернадского. – 2010. – N 07–09 (30). – С. 51–57.

11. Магомедов, А. М. Непрерывность расписаний для 3-элементных предписаний [Текст] // Вопросы современной науки и практики. Уни верситет им. В. И. Вернадского. – 2010. N 10–12(31). – С. 82–89.

12. Магомедов, А. М. Расслоение множества рбер двудольного графа е [Текст] // Научно-технические ведомости СПбГПУ. Раздел Матема тика. – 2010. – N 4(109). – С. 150–155.

13. Магомедов, А. М. Задания по программированию и алгоритмы [Текст] – Махачкала: Изд-во ДГУ, 1989. – 25 c.

14. Магомедов, А. М. Теория трудоемкости алгоритмов [Текст] – Ма хачкала: Изд-во ДГУ, 1992. – 81 с.

15. Магомедов, А. М. Связное расписание [Текст] – Махачкала: Изд-во ДГУ, 1994. – 78 с.

Прочие публикации 16. Магомедов, А. М. Мультимедийное прочтение / А. М. Магомедов, Т. А. Магомедов, М. А. Магомедов // Программа для ЭВМ. Свиде тельство N 2010611946 о гос. регистр. прог. для ЭВМ от 15.03.2010.

17. Магомедов, А. М. Распознавание строчных букв кириллицы / А. М.

Магомедов, Т. А. Магомедов, М. А. Магомедов // Программа для ЭВМ. Свидетельство N 2010612224 о гос. регистр. прог. для ЭВМ от 02.03.2010.

18. Магомедов, А. М. Компьютерная карта РД. Программа для ЭВМ / А. М. Магомедов, Т. А. Магомедов, Т. И. Шарапудинов // Свиде тельство N 2010612223 о гос. регистр. прог. для ЭВМ от 24.03.2010.

19. Магомедов, А. М. Составление школьного расписания на ЭВМ [Текст] // В кн.: Материалы Всесоюзной научной конференции по моделированию и оптимизации учебного процесса с использованием ЭВМ. – 1985. – Москва.: Изд-во МЭИ. – 4 c.

20. Магомедов, А. М. Минимизация простоев [Текст] // Тезисы Всесо юзного семинара Системное моделирование производства, распреде ления и потребления. Часть 2. – 1986. – Воронеж. – 2 с.

21. Магомедов, А. М. Условия существования паросочетаний [Текст] // в сб. Функ. анализ, теория функций и их приложения. – 1987. – Махачкала: Изд-во ДГУ. – 4 c.

22. Магомедов, А. М. Программирование на языке ассемблера (уч. пособие, 57 c.) [Текст] // 1989. – Махачкала: Изд-во ДГУ.

23. Магомедов, А. М. О составлении факультетского учебного распи сания [Текст] // Сб. трудов ДГУ. – Махачкала. – 2 c.

24. Магомедов, А. М. Вопросы уплотнения факультетского учебного расписания [Текст] // Сб. трудов ДГУ. – Махачкала. – 1 c.

25. Магомедов, А. М. Семейство двудольных паросочетаний с ограни чениями [Текст] // В сб. Функ. анализ, теория функций и их прило жения. – 1993. – Махачкала. – 4 c.

26. Магомедов, А. М. Электронный справочник Алгоритмы и про граммы [Текст] // Тезисы Всероссийской научно-методической кон ференции Компьютерные технологии в высшем образовании. – 14– 18.03.94. – Санкт-Петербург. – С. Е56.

27. Магомедов, А. М. К вопросу о расписании мультипроцессорной си стемы [Текст] // Труды междунар. симпозиума Интеллектуальные системы. МГТУ им. Баумана. – 1994. – Махачкала. – 5 c.

28. Магомедов, А. М. Задачи дискретной математики в олимпиадах по информатике [Текст] // В кн.: Материалы 1-й научной сессии Да гестанского отделения Международной академии информатизации.

Часть II. Общетеоретические и спец. проблемы информатики. – 1995.

– Махачкала.

29. Магомедов, А. М. К вопросу об оптимальном размещении TSR программ [Текст] // Вестник ДГУ. – 1997. – 5 c.

30. Магомедов, А. М. Условия связываемости матрицы [Текст] / А. М.

Магомедов, А. Рашайда // Вестник ДГУ. – 1998. – 2 c.

31. Магомедов, А. М. Матрица расписания с двумя ненулевыми эле ментами в строке [Текст] // Вестник ДГУ. – 1999. – Вып. 4 – 4 c.

32. Магомедов, А. М. Согласование таблицы [Текст] / А. М. Магоме дов, А. Рашайда // Вестник ДГУ. – 2002. – 7 c.

33. Магомедов, А. М. Построчная оптимизация разреженной матрицы [Текст] // Вестник ДГУ. – 2002. – 1 c.

34. Магомедов, А. М. NP-полные проблемы интерфейса IEEE- [Текст] // Тезисы Всероссийской научно-технической конференции Современные информационные технологии в управлении, ДГТУ. – 2003. – Махачкала, ДГТУ. – 4 c.

35. Магомедов, А. М. Равнодефицитное разбиение списка по элементу [Текст] // Вестник ДГУ. – 2004. – 3 c.

36. Магомедов, А. М. К вопросу о маршрутизации [Текст] // Материа лы международной конференции Современные проблемы математи ки. – 2004. – Махачкала. – С. 47.

37. Магомедов, А. М. Дефрагментация разреженных матриц как зада ча разбиения графа на остовные подграфы специального типа [Текст] // В кн.: Материалы международной конференции Современные проблемы математики. – 2004. – Махачкала. – С. 48–54.

38. Магомедов, А. М. Неразрывное размещение наборов в строках мат рицы без повтора элементов в столбцах [Текст] // Вестник ДГУ. – 2005. – 6 c.

39. Магомедов, А. М. Дефрагментация матриц перестановок с сохране нием наборов элементов в линиях [Текст] / А. М. Магомедов // Про блемы теоретической кибернетики. Тезисы докладов XIV Междуна родной конференции. Под ред. О. Б. Лупанова. – 2005. – М.: Изд-во МГУ. – C. 99.

40. Магомедов, А. М. Дефрагментация матриц с q, 2q и 3q ненулевыми элементами в строке [Текст] // Региональная науч.–практ. конферен ция Компьютерные технологии в науке, экономике и образовании, 17–19 ноября 2005. – 2005. – 4 c.

41. Магомедов, А. М. Некоторые случаи дефрагментации матриц пере становок [Текст] // Материалы IX Международного семинара Дис кретная математика и ее приложения, посвященного 75-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18–23 июня 2007г) / Под редакцией О. М. Касим-Заде. – 2007. – М.: Изд-во механико-математического факультета МГУ. – C. 283–284.

42. Магомедов, А. М. Условия уплотнения расписания [Текст] // V международная конференция по математическому моделированию, посвященная 75-летию академика В.Н.Монахова: Тез.докл. Под ре дакцией И.Е.Егорова. – 2007. – Якутск: изд-во ООО РИЦ Офсет. – C. 65.

43. Магомедов, А. М. Условия дефрагментации матрицы с постоянным числом ненулевых элементов в строке и постоянным множеством эле ментов в каждом столбце [Текст] // Региональная науч.–практ. кон ференция Компьютерные технологии в науке, экономике и образова нии. – ноябрь 2007. – Махачкала, ДГУ. – 2 c.

44. Магомедов, А. М. Теоретико-графовый подход к задаче оптимиза ции расписания [Текст] / А. М. Магомедов, Т. С. Лугуев // Сборник материалов Всероссийской науч.–практ. конфереренции с междуна родным участием Информационные технологии в профессиональ ной деятельности и научной работе, г. Йошкар-Ола. – 2008. – Т. 1.

– С. 200–202.

45. Магомедов, А. М. О модификации характеризации Бержа [Текст] // Проблемы теоретической кибернетики. Тезисы докладов XV меж дународной конференции (Казань, 2–7 июня 2008г). Под редакцией Ю.И.Журавлева. – 2008. – Казань: Отечество. – С. 77.

46. Магомедов, А. М. О вычислительной сложности частного случая задачи построения расписания [Текст] // X Белорусская математи ческая конференция: Тез. докл. междунар. науч. конф. Минск, 3– ноября 2008 г. – 2008. – Часть 5. – Мн.: Институт математики НАН Беларуси. – C. 92.

47. Магомедов, А. М. Магомедов Т.А. Компьютерный вывод рекур рентных формул разбиения прямоугольника [Текст] // X Белорус ская математическая конференция: Тез. докл. междунар. науч. конф., Минск, 3–7 ноября 2008 г. – 2008. – Часть 4. – Мн.: Институт матема тики НАН Беларуси. – С. 44.

48. Магомедов, А. М. NP-полнота задачи построения непрерывного расписания для специализированных процессоров [Текст] // Тру ды VIII международной конференции Дискретные модели в теории управляющих систем, 6–9 апреля 2009 г., Москва, 2009 / Отв. ред.

В. Б. Алексеев, В. А. Захаров. – 2009. – М.: Издательский отдел фа культета ВМиК МГУ им. М. В. Ломоносова;

МАКС Пресс. – С. 203– 205.

49. Магомедов, А. М. Условия существования расписаний малой дли тельности [Текст] // Материалы IV Всероссийской конференции Проблемы оптимизации и экономические приложения, Омский гос. ун-т, 29 июня – 4 июля 2009 г. – 2009. – C. 148.

50. Магомедов, А. М. Об одной специальной рберной раскраске дву е дольного мультиграфа степени не больше 5 [Текст] // Методы и сред ства обработки информации: Третья Всероссийская науч. конферен ция, Москва, 6–8 октября 2009 г.: Труды конференции / Под ред.

Л. Н. Королева. – 2009. – М.: Издательский отдел факультета ВМиК МГУ им. М. В. Ломоносова;

МАКС Пресс. – C. 266.

51. Magomedov, A. M. Continuous school timetable with duration of 4 and 5 [Text] // International conference Optimization and applications (OPTIMA2009) September 21–25, 2009, Petrovac, Montenegro. The Montenegrian Academy of Sciences and Arts University of Montenegro Dorodnicyn Computing Center Russian Academy of Sciences (http://www.ccas.ru/optima2009/abstracts_e.html).

52. Магомедов, А. М. Применение теоремы о разбиении гиперграфа к задаче жесткой оптимизации расписания [Текст] // В кн: Материалы XVIII международной школы–семинар Синтез и сложность управля ющих систем им. ак. О. Б. Лупанова (Пенза, 28 сентября – 3 октября 2009 г.) / под ред. О. М. Касим-Заде. – 2009. – М.: Изд-во механико математического факультета МГУ. – С. 61–62.

53. Магомедов, А. М. Разбиение семейства мультимножеств [Текст] // Дискретная математика, алгебра и их приложения: Тез. докл. Между нар. науч. конф. Минск, 19–22 октября 2009 г. – 2009. – Мн.: Институт математики НАН Беларуси. – C. 101–102.

54. Магомедов, А. М. Два частичных паросочетания в двудольном гра фе специального вида [Текст] // Межд. школа-семинар Дискретная математика и приложения, – МГУ. – 1–6 февраля 2010.

55. Магомедов, А. М. Условия построения непрерывного расписания для двухэлементных предписаний [Текст] // Математические методы в технике и технологиях - ММТТ-23: сб. трудов XXIII Междунар.

науч. конференции.: в 12 т. /под общ. ред. В. С. Балакирева. – 2010.

– Саратов: Сарат. гос. тех. ун-т. – Т. 2. – С. 58–60.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.