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

Магомедов, Абдулкарим Магомедович

Условия существования непрерывных расписаний тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Магомедов, Абдулкарим Магомедович АВТОР

доктора физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Махачкала МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Условия существования непрерывных расписаний»

Автореферат диссертации на тему "Условия существования непрерывных расписаний"

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

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

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

Автореферат

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

Москва - 2011

1 2 МАЙ 2011

4845952

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

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

профессор

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

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

профессор

Валерий Николаевич Шевченко,

доктор физико-математических наук, профессор

Владимир Рубенович Хачатуров,

доктор физико-математических наук, профессор

Эдуард Николаевич Гордеев

Ведущая организация: Государственное образовательное учреждение

высшего профессионального образования "Московский энергетический институт (технический университет)"

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

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

Автореферат разослан «jJ^O* апреля 2011 г.

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

доктор физико-математических наук (^Jj^^lУ^ РязаН0В

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

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

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

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

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

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

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

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

Результаты, полученные для задач интервальной и инциденторной раскраски графов, находят применение в вопросах жесткого уплотнения. В свою очередь, исследование задачи о непрерывном расписании способствует развитию некоторых направлений теории графов. Так, например, получены: новый подход к поиску наибольшей плотности подграфа, что, в свою очередь, находит применение в вычислении рейтинга сайтов и социальных сетей; новое доказательство теоремы об NP-полноте задачи о 3-раскраске графа; формулировка полиномиальной подзадачи известной NP-полной потоковой задачи; обобщение знаменитой теоремы Пстерсена о разбиении регулярного графа четной степени на 2-факторы ^ и т.д.

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

Важные результаты по теории расписаний получены также следующими авторами: C.B. Севастьянов, В.А. Перепелица, Э.Х. Гимади,

B.М. Котов, В.В. Топорков, А.В.Пяткин, A.C. Асратян, P.P. Камаляи,

C.J.Cassclgren, K.Giavo, H.M.Hansen, D.Hanson, C.O.M. Loten, В.Toft, B.B. Сервах. A.A. Лазарев и др.

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

Целью работы является исследование условий существования жёсткого уплотнения и разработка алгоритмов построения непрерывных расписаний путём анализа структурных свойств различных классов расписаний. позволяющих определить статус сложности задачи и, в случае уста' Pe tersen Л. Dir- théorie der regularen graphon //' Acta Alatli. 1891. 15. P. 193-220.

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

Методика исследований. В работе используются как известные методы, так и новые методы, разработанные автором. К числу известных относятся методы теории графов, комбинаторики, теории алгоритмов. Новые методы и подходы: метод «компьютерной формулировки» рекуррентных соотношений (гл. 1); метод построения непрерывного расписания длительности 4 (гл. 3), метод вычисления бездефектного потока, модификация метода '¿-факторизации (гл. 5), а также новый подход к вычислению наибольшей плотности подграфа (гл. б).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2007); V международная конференция по математическому моделированию, посвященная 75-лстию академика В Н.Монахова (Якутск, 2007); Всероссийская научно-нрактическая конфереренция "Информационные технологии в профессиональной деятельности и научной работе" (Йошкар-Ола,

2008); XV международная конференция "Проблемы теоретической кибернетики" (Казань, 2008); X Белорусская математическая конференция (Минск, 2008); IV Всероссийская конференция "Проблемы оптимизации и экономические приложения" (Омск. 2009); VIII Международная научная конференция "Дискретные модели в теории управляющих систем" (МГУ, 2009); III Всероссийская научная конференция "Методы и средства обработки ин-

формации" (МГУ, 2009); Международная научная конференция "Дискретная математика, алгебра и их приложения" (Минск, 2009); Internationa! conference "Optimization and applications" (Petrovac, Montenegro, 2009); XVIII международная школа-семинар "Синтез и сложность управляющих систем" им. академика О. Б. Лупанова (Пенза, 2009); X международная школа-семинар "Дискретная математика и приложения" (МГУ, 2010); XXIII Международная научная конференция "Математические методы в технике и технологиях" (Саратов, 2010).

Диссертация прошла апробацию на заседаниях семинаров: отдела математики и информатики Дагестанского научного центра РАН 11.02.2010 (руководитель И. И. Шарапудинов); отдела математических проблем распознавания и методов комбинаторного анализа сектора математических методов распознавания и прогнозирования ВЦ РАН 20.04.2010 (руководитель В.К.Леонтьев); кафедры математической кибернетики факультета ВМиК МГУ 22.05.2009 и 23.04.2010 (руководитель А. А. Саиоженко), вузов г.Махачкала 23.11.2010 (руководитель А. К.Рамазанов).

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

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

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

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

Формулировка задачи. Определения и обозначения. Исследуется задача о расписании обслуживания множества требований N ~ {1,... , п} в системе приборов L = {1,...,/}: статус сложности, условия существования, эффективные алгоритмы построения. Информация к расписанию задана семейством (I = {wi,...,a><} предписаний ш-, - неупорядоченных наборов (мультимножеств) с: элементами из множества N\ каждый í-й прибор должен выполнить операцию единичной длительности

над каждым элементом из u>i, г 6 L; условия частичного предшествования отсутствуют, в каждый момент времени каждое требование обслуживается не более чем одним прибором и каждый прибор обслуживает не более одного требования (условие перазделяе.иого доступа). Количество вхождений элемента j £ N в u>i обозначим через rep^j; repnj = rePw,ii

m = m(f2) = maxrepni-

Элементы множества N удобно называть буквами; (/ х т)-матрицу с элементами из множества {0,1,...,«} будем называть расписанием для семейства Л, если (1) в каждой г-й строке буквенные элементы составляют (2) в каждом столбце буквенные элементы попарно различны. Расписание будем называть непрерывным, если в каждой строке буквы размещены в подряд идущих ячейках. Уточним понятие жёсткого уплотнения: жёстким уплотнением (или, кратко, уплотнением) будем называть преобразование расписания к непрерывному виду с соблюдением свойств (1)-(2).

Всюду в дальнейшем предполагается, что выполнены неравенства ^ m(S1), 1 ^ г ^ I, обеспечивающие существование расписания длит ельности m(f}). Если repn 1 = - ■ • = герап, то семейств о Q и соответствующие расписания будем называть нагруженными. Наборы (предписания) мощности к будем называть кратко к-наборами (предписаниями). Сформулируем задачу о непрерывном расписании: сугцествует ли непрерывное расписание длительности т(П) для семейства предписаний Q ?

Семейство ii будем рассматривать как гиперграф с множеством вершин N, в каждом «ребре» ш; которого вершина из N может присутствовать несколько раз. Для наглядности будем применять двудольное представление гиперграфа, для чего соотнесем семейству П двудольный ассо-циирова.ипы.й граф G = (X,Y,E): X = {x'i,..., Y = {y\,..., yi}. в котором количество рёбер, соединяющих вершины Xj £ X и г/,; € У, равно rep^J. Отождествляя номер единицы времени обработки требования Xj прибором у,- и номер цвета ребра (Xj,y,), получим эквивалентную задачу о рёберной раскраске графа G = (X,Y,E). Если |o>i| = • ■ ■ = Ы = 2, то для каждого ш= (¿х,^) 6 П заменим в двудольном ассоциированном графе конструкцию из рёбер 0е»,, у»), (ж.;2,?/;) и вершины у, одним новым ребром (г,-,,ж»2). Полученный граф G = (X, Е) назовем графом, ассоциированиъш с Q. Если для степеней всех вершин т. б X и у 6 Y двудольного графа G = (X, Y, Е) выполнены ограничения вида dc;x a A, day b В, где а, Ь € {;$, =}; А,В £ Z+, то будем говорить, что G является (аЛ,ЬВ)-графом\ знак «=» подразумевается по умолчанию; если

значения dox или dey безразличны, применяются записи (*,ЬВ) или (аА, *) сотвстственно.

Правильной реберной раскраской графа G цветами 1,2,3,... называется отображение /: E(G) —> {1,2,3,... }, такое, что /(ej) / /(ег)для каждой пары смежных ребер е\ и ег- Если для каждой вершины графа цвета инцидентных ребер образуют некоторый интервал, правильная реберная раскраска графа цветами 1,2,3,... называется интервальной. Интервальная раскраска цветами из множества {1,2,...,£} называется интервальной i-раскраской, если каждый из цветов этого множества присвоен хотя бы одному ребру. Через A(G) обозначается наибольшая степень вершины графа G. '

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

В главе 1 рассмотрены вопросы построения, перечисления и интерпретации расписаний различных типов. Центральное место отведено вопросу сложности задачи о непрерывном расписании. Публикация результатов: § 1.1 - [12]; § 1.2 - [8], [5], [34], [14]; § 1.3 - [15]; § 1.4 - [47].

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

Через IgW обозначим множество ребер, инцидентных в графе G = (V,E) множеству W Ç V; Е{х,у) -- набор параллельных ребер с концами в вершинах х к у. Задача о двухстадийном расслоении

УСЛОВИЕ. Заданы целые положительные числа p,q, 7,<5i,..., <57 и связный (pg, С; рд)-граф G = (X, У, Е); множество У разбито на подмножества

У1,...,У>.

Вопрос. Существует ли двухстадийное расагоеиие множества рёбер Е? Другими словами, существует ли разбиение множества Е на такие подмножества Ei,..., Ер. что каждое Е-, (1 < г < р) является набором простых ребер и допускает разбиение на полные наросочетания Mij множества X с

множеством У (1 ^ j ^ q), в каждом из которых количество рёбер, инцидентных вершинам множества Yjt, не превышает 5k (1 < к ^ 7) ?

Теорема 1.1.1. Для существования двухстадийпого расслоения мио-о/сества рёбер Е графа G = (X, У, Е) необходимо и достаточно выполнение соотношений

\Е(х,у)\ < р, dGx = pq, dGy ^ pq, \hYk\ < pqk

для всех х е X, у 6 У и 1 ^ к ^ 7.

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

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

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

Теорема 1.2.2. Задача о непрерывном (I х т)-расписании остается NP-полпой и в следуюищх двух случаях: 1) когда требуется, чтобы в каэ/сдой строке равные буквы размещались рядом; 2) когда количество буквенных элементов в строке не превышает [пг/2].

Известно2', что задача о существовании у двудольного графа G = {X, У, Е) интервальной Д-раскраски NP-полна; с другой стороны, каждый двудольный граф G — (X, У, Е) с = 1 обладает очевидной интервальной Д-раскраской. Следующая теорема уточняет, при каком наименьшем значении задача об интервальной Д-раскраске приобретает содержательный характер.

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

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

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

Севастьянов. С. В. Об иптериальпой раскрашиваемое™ ребер .двудольного графа /У Метода дискретного апалима. 1990. Т. 50. С. 61 72.

JStockuieyer. L.J. Planar ,'i-colorability is NP-comp!ete / /' SIGACT Xews. 1073. Vol. 5. • No. 3. P. 19 25.

1D.R. Fulkerson, O.A. Gross. Incedcnce matrices and interval paplts ' Pacific J. Math. ■ 1965. - 15.

P. 8Я5 855.

УСЛОВИЕ. Заданы целые неотрицательные I, т. п и (/ х т)-матрица. М с элементами 0 и 1, каждый столбец которой содержит точно п единиц.

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

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

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

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

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

В § 1.4 рассмотрена задача «компьютерного подсчёта» расписаний с разделяемым доступом. Пусть п учебных групп пронумерованы по принципу постепенной градации специализации, так, что для любых двух групп, номера которых отличаются точно на единицу, может быть прочитана лекция длительностью в один академический час. Кроме лекционного типа, допускаются еще -занятия семинарского тина, каждое из которых проводится в учебной группе и продолжается два академических часа. Расписанию учебных занятий выделены академические часы 1,...,т. Если f и I обозначают соответственно номера академического часа и учебной группы соответственно, то: полузанятие — упорядоченная пара занятие •- неупорядоченный, набор двух нолузанятий вида (4. г), [I + 1, г) или г), (¿,г + 1); расписание — такой набор занятий, в котором каждое полузаня-тис (¿,г) включено точно в одно занятие; 1 < I < п, т. Задача:

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

Сформулированная задача встречается в литературе (и б олимиадах по программированию) в следующей формулировке: вычислить количе-

ство всевозможных покрытий матрицы М размеров т х п «плитками» 1 х 2 без пропусков и перекрытий. Известны рекуррентные соотношения для случаев п = 2,3 или Создана компьютерная программа, использующая метод динамического программирования, элементы символьных преобразований и арифметические действия со «сверхбольшими» целыми числами, способная составить систему рекуррентных формул и выполнить по ним соответствующие расчеты.

Пусть задан вектор (ки ..., к„) с наибольшим элементом г. В матрице М рассмотрим фигуру, образованную клетками

Мкл д ..., Мт.и ■ ■■, Мк„я,..., Мп.п\

количество покрытий данной фигуры и (в случае несимметричности) фигуры, соответствующей вектору {к„,... обозначим некоторой заглавной буквой латиницы с индексом г. В качестве примера приведем рекуррентные формулы, полученные компьютерным путем для случая п — 5 (конечной целью является вычисление значения Ст); для удобства восприятия в таблице указаны векторы (г — к\,..., г — кп).

О, = А^] + иг 10 0 12) К; = + К-1 1110 0

Щ = Ь, + + й;_2 00 1 0 0 1 Д=С';_1 + Д-1 10 0 11

А; = + П-1 <- Л--2 + В; 00112| = 1 0 0 0 0

1 1 0 0 0 6^= К; + О, + + Ь',-1 + с,-, 0 0 0 0 0

Через БтУп обозначено количество покрытий для матрицы т х п:

5ших-1 = 1154075100487723888159117233401970510843180361, Яшхз = 5568402462493007660191.

5«х5 = 55, = 1551295Ш40а1163779Ш2190726794553190537472693С928865464104.

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

1^1 = • • • = = р, герп 1 =:••• = герпп - тп(0.) = 2р.

Публикация результатов: §2.1 - [С], [15]; §2.2 - [4|, [6]; §2.3 - [5].

В § 2.1 определены два вида рёберной раскраски. Пусть (3 = (X, V, Е) - двудольный граф, ассоциированный с семейством П. Правильная реберная раскраска графа С называется непрерывной, если для каждого у € У цвета инцидентных рёбер образуют подинтервал из [1..ш]. Рёберную раскраску двудольного (др, ^ р)-графа в — (X, У, Е) в ц цветов будем называть разбивающей ц-раекраской (или ц-раскраскои), если каждой вершине х 6 X инцидентны но ррёбер каждого цвета, а в каждой вершине у 6 У представлен только один цвет.

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

М.: Мир. 11)98. 71Ш-.

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

Доказано, что из теоремы вытекает существование непрерывного расписания для нагруженного семейства 2-прсдписаний П, т(П) = 4. Таким образом, (др,< р)-граф в = (Х,У,Е) всегда допускает (/-раскраску в вырожденном случае р = д = 2. Начало параграфа является «точкой ветвления» исследования: продолжение параграфа посвящено направлению, определяемому равенством ц = 2 при произвольном р; другое направление — когда р = 2. а </ произвольно, — получило развитие (и завершение) в §5.1.

Задача о разбивающей 2-раскраске: для (2р, ^ р)-графа С = (Л', У, Е) ■требуется проверить существование рёберной 2-раскраски, такой, что любой вершине х 6 X инцидентны р рёбер каждого из двух цветов, а в каждой вершины у £ У представлен только один цвет.

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

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

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

Теорема 2.2.1. Простой (6,3)-граф С = (Х,У,Е) непланареп.

Задача построения (6,3)-мультиграфа, для которого разбивающая раскраска не существует, тривиальна. Например, таковым является граф, заданный списками смежных вершин: 2/1(0:1,ж^хО, уз^ьЯг.Яг). 2/3(Ж1, х2, х2), У4{хьх2, х2).

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

Граф Си ггри любой 2-разбинаю1цей раскраске с(у\) = ~с(у2)< с(уз) = -

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

С,

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

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

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

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

В связи с NP-полнотой задачи о разбивающей рёберной раскраске, в § 2.3 построен метод динамического программирования для проверки существования непрерывных расписаний. Вспомогательная задача: для каждого из п-наборов (fci, ...,k„). kj ^ [0, • ■ • >р]> проверить существование у семейства П подсемейства S, обладающего свойством repsj = kj Vj 6 N.

Произвольно выберем набор (/гь ...Д-„). Для Ki,..., кп е [0,... ,р]. i 6 L, обозначим через Т[г, к\,..., к,,] значение истинности утверждения: «в семействе { и>х,..., щ } найдется подсемейство S' такое, что reps'j = Kj для каждого j G N». Понятно, что ответ вспомогательной задачи определяется значением T[l, ki,..., fcn]. Приведем алгорим заполнения (п + 1)-мерной таблицы Т:

• T[l, ki, ...,кп] = true <=> (ki = ... = кп = 0) или (repUtj = Kj, Vj 6 N); Для i = 2,..., I:

• T\i — 1, ki, ...,«.„] = true T[i,ki, ...,k„] = true.]

• если T[i - 1, «!,...,«„] = false, то (T[i, «i,..., «„] = true

repUij < Kj Vj e N и T[i - 1, Ki - rep^l,..., кп - rep^n] = true).

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

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

Приведенная в §3.1 классическая NP-гюлная задача «Составление учебного расписания» 8' остается NP-полной даже в случае 3-х уроков, если имеются ограничения на доступные часы. Доказано, что для нагруженного расписания М длительности 3 уплотнение существует тогда и

6Pyatkin. Л. V. Interval coloring of (.'i,4)-hircgulill bipartite graphs having large cubic subgraphs J. of Graph Theory. 21)04. Vol. 47. No. 2. P. 122 128.

7 Aaratian. A. S. Casselgren, C. J. Some results on interval edge colorings of (n. /?}-biregular bipartite graphs

Department of Mathematics. - 2007. Linkoping University S-581 83 Linkdping, Sweden.

";S. Even. A. Itai; A. Shamir. On the complexity of timetable and integral multi-commodity flow problems / SIAM J. on Сотр. 1076. V. 5. No. 4. P. 691 703.

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

Измельчением Í2 семейства £2 = {u>.¿} будем называть такой набор букв, для которого

геШ3 = rep"'j' 6 Ni

Если количество букв в каждой строке нагруженного (I х т)-расписания М принадлежит некоторому множеству Q, то будем говорить, что М принадлежит классу Pqт'п.

Коль скоро для нагруженного семейства предписаний расписание всегда существует, вместо задачи построения непрерывного расписания для исходного семейства предписаний удобно рассматривать эквивалентную задачу уплотнения уже построенного нагруженного расписания. §3.2 посвящен условиям уплотнения расписаний класса -Р^з^.

Зададим функцию-множество Q на множестве {1,2,3,4}: Q(l) = {0,1}, Q(2) = {1,2}, 0(3) = {2}, <2(4) = {2}, и определим дуэт F = {F2,..., F¡} расписания М 6 Pj^jj}'-

F = {(2)l,...,(2)n}; Fi Cu;.,; e Q(|w,|); 1 < t < Z.

Теорема 3.2.1. Расписание класса P{fi'34] допускает уплотнение тогда и только тогда, когда обладает дуэтом.

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

Множество вершин: s-источник, X = {.гь..., a;,,}, Y = {yi, ...,y¡}, t-сток; множество дуг: {с = (s,xj), и(е) = с(е) = 2};

{е = (.х,- ,i/j), u(e) = 0, с(е) = min(2, гер^г)};

{е = t), и{е) = min{Q(|w,-|)}; с(е) = тах{<2(|ил;|)};

1 ^ г < п, 1 < j ^ I.

Теорема 3.2.2. Матрица М kjiüccü 3 тогда и только тогда обладает дуэтом, когда в сети N(M) существует допустимый поток.

В § 3.3 рассмотрела задача уплотнения расписания длительности 5 без 1-предиисаний. Следующая транспортная сеть >4(М) для М £ Mlj,

1 sí k se [m/2J, используется не только в формулировке теоремы 3.3.1, но и в последующих главах. При определении элементов сети предполагается, что 1 ^ г ^ п. 1 ^ j < /:

• множество вершин: 5 (источник), X = {.-г/ }, У = {у} }, I (сток);

• множество дуг: {(в,ж*)}, {(.т.ьу7-)}, {(%.*)};

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

ф, ж.;) -тп-2к\ с(ж^ щ) = гер^ц с(у¿) = тп - 2к\

• нижние потоковые ограничения: £•;) — т — «(ж,-,?/,) = 0;

= |0, еслиИ = Ь;

I тп — 2/с, если = тп - к или то.

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

Теорема 3.3.1. Нагружен!юс расписание М класса Р1^'^^ допускает уплотнение тогда и только тогда, когда ф 4, 1 ^ г ^ I, и в сети 7^2{М) суи^ествуст допустимый поток /.

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

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

Теорема 4.1.1. Для уплотнения матрицы М класса т) необ-

ходимо и достаточно существование в сети Х](М) допустимого потока /.

Теорема 4.1.2. При нечётном т для уплотнения матрицы М класса Р{2тп-2т} пе°бходимо и достаточно существование допустимого потока / в сети ]^2(М).

§ 4.2 изучена природа, трудностей, возникающих при уплотнении нагруженного расписания М класса (т нс кРатн0 Каркас (I х т)-расписаш1я М определяется как (/ х т)-мдтрица, обладающая следующими свойствами: 1) ..., а-} С 2) Ь\х = ••• = Р^ = Fj.rn.-M = ■ ■ ■ = Р).т =0, I j I; 3) множество букв каждого из столбцов к + 1,...,т — к, равно N. Пристройка Т расписания М определяется как (I х ш)-матрпца, в которой: 1) в каждой г-й строке буквенные элементы образуют поднабор из щ мощности - тп + 2к: 2) = ■ ■ ■ = Тц — 0, к + 1 ^ } ^ т — к\ 3) множество букв каждого из столбцов 1 ,...,к и тп — к + 1,..., т равно /V.

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

Теорема 4.2.1. Расписание М 6 P[km-km} обладает каркасом тогда и только тогда, когда существует пристройка.

Теорема 4.2.2. Расписание М е P\km-km) обладает пристройкой тогда и только тогда, когда в сети существует допустимый по-

ток.

Пристройка Т расписания класса ^[¿"„"„fc mj называется разбиваемой, если каждый 2£-буквснный набор строки пристройки допускает разбиение на два fc-набора, так, что семейство S. включающее как все исходные к-буквенные наборы отдельных строк, так и все вновь образовавшиеся наборы, допускает разбиение на два подсемейства, измельчение каждого из которых равно {(fc)l, (к)2,..., (к)п}. Пристройка расписания не всегда является разбиваемой.

Теорема 4.2.3. Расписание М е Р^'т-кт} допускает уплотнение тогда и только тогда, когда М обладает разбиваемой пристройкой.

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

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

главы.

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

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

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

Получена следующая модификация: двудольное представление гиперграфа G — (X, у2 u Y2T, Е), где степень каждой вершины из X и Y2Т равна чётному числу 2г, а степень каждой вершины из У\ равна 2, допускает разбиение на г регулярных подграфов степени 1.

Теорема 5.1.2. Пусть А = {аь ... ,ар} и В = {/3,,+ь ... ,Рр+д} - соответственно семейства 2г- и 2-иаборов, заданных на множестве N. Если

repAunj = 2r Vj е N,

то для каждого а,; существует (пред)разбиение па г 2-наборов а',... , а^, такое, что семейство 2-иаборов

R = {<*!, • • ■. <*i; .. ■; ..., аГр; Рр+и ..., /3;Ж/}

допускает (пост)разбиение на г подсемейств Ri,..., Rr, удовлетворяющих условиям: для каждого к — 1,..., г,

1) rePnhj = 2 Vje TV; 2)a^eRk Vt € {1,... ,p}.

При произвольном иредразбиении 2г-наборов а, на 2-наборы объединение последних с (3j образует семейство R 2-наборов, для которого выполняется условие: repaj = 2г Vj 6 N. Существование постразбиения семейства R на г подсемейств R)., для каждого из которых repnj = 2 Vj € N, следует из теремы Пстерсена. Но при этом, вообще говоря, при произвольном постразбиении найдутся 2-набора, полученные разбиением одного и того же Qi, но включенные в разные Rt, и RСуть утверждения теоремы заключается в существовании такого предразбиения, при котором всегда существует постразбиение, обеспечивающее, в частности, и выполнение последнего условия.

Теорема 5.1.3. Любое расписание М 6 Р^?," допускает уплотнение.

В §5.2 рассмотрена структура непрерывного расписания класса Ръм-й т и ассоциированного двудольного графа.

При т ф 0 (mod к) для непрерывного расписания Me ¡'l",l„' 1 к < m/2, выполняется тождество

Mi,k+i = • • • = MUn-k+1 = 0, если = к,

что существенно упростило формулировку условий существования непрерывного расписания в главе 4. При к = 2 и четном т соответствующее тождество не имеет места. По этой причине необходимо проверить, существует ли семейство ft' — {ш[,..., ш,'}, удовлетворяющее условиям:

1) uj'i с Шй l^i^l;

2) ИЛ™"4' ССЛИ Neim-2,m}; 1 ^ . ^

] 0 или 2, если |Wi| = 2,

3) iy= {(m-4)l,...,(m-4)n}.

В двудольном графе G — (X,Y,E), ассоциированном с расписанием М € ГД--.2 ?п}' обозначим подмножества множества У, образованные вершинами степени 2, т — 2 и т, через Уг, Ут-2 и Ут соответственно. Если Е' — подмножество множества Е, такое, что каждой вершине множества ХиУт_2иУт инцидентны то — 4 рёбер из £", а каждой вершине множества >2 — либо 0, либо 2 ребра из Е\ то порожденный множеством подграф графа G будем называть скелетом графа G.

Теорема 5.2.1. Для уплотнения расписания М 6 Pptm-^m} необходимо и достаточно существование скелета у ассоциированного двудольного графа G.

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

. , , . , . 10, если т нечётно;

если \u)j\ = 2, то u{yh t) = 0 и c{y.j,t) - <

12, если т четно.

Пару дуг е'= (xp,yj) и е" = (xt/, yj), инцидентных вершине т/у е Угj назовем гомологичной нарой. Целочисленный поток / в сети >Го(М) называется бездефектным, если f(e') = f(e") для всех гомологичных пар. Если для гомологичной пары дуг е! и е", инцидентных вершине г/, 6 У>, /(е') ф /(е"), вершину у^ назовем /-дефектом; множество /-дефектов обозначим /д.

Доказано. что ¿ля существования уплотнения расписания М € Р{2т-2 т] необходимо и достаточно существование в сети No(M) потоков: допустимого - при нечётном то и бездефектного — при чётном т. Проверка существования допустимого потока осуществляется стандартной процедурой; остается рассмотреть случай чётного т. Показано, что рассматриваемая подзадача известной NP-иолной задачи «Целочисленный ноток в сети с гомологичными дугами» разрешима за полиномиальное время.

Рассмотрим разбиение множества дуг Е ассоциированного с расписанием М графа G(M) на два непересекающихся множества, индуцированное потоком / в сети No (А/):

Ik = {eeE\f(e) = k}-, к = 0,1.

"Salmi. S. Computationally related problems ,7 SIA.M .Т. Comput., 1974. No ;l. P. 2(i2 279.

Пусть у — внутренняя вершина некоторого пути Т в графе й. Будем говорить, что для вершины V выполнено свойство чередования, если из любых двух последовательных рёбер пути Т, инцидентных вершине v, одно принадлежит /о, другое — /1; если К,0 С У2 — множество всех вершин графа С(М), для которых свойство чередования нарушено, путь Т будем называть (У2°, ^-чередующимся.

Теорема 5.3.1. Пусть / — допустимый поток в сети Хц(М) и /о Ф 0. Если в сети 1{д(М) существует некоторый бездефектный поток ¡р, то из произвольной вершины у 6 /о в множество /¿> - {у} найдется (У^0, /)-чередующейся путь.

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

Если /о = 0, то бездефектный поток найден; пусть /о ф 0.

Пока }о ф 0. выполнять действия:

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

если (У2°, /)-чередующийся путь из у^ в множество /о — {т/,} существует. то поменять для дуг е пути значенш1 /(е) на 1 — /(е), удалить концевые вершины пути из /о (и включить их в У®),

иначе завершить алгоритм с сообщением об отсутствии бездефектного потока.

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

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

Пусть й — семейство наборов, заданных на множестве /V; через обозначим количество различных букв в наборах семейства 5.

Теорема 6.1.1. Пусть IV] и Жг - такие семейства из 1- и 2-предписаний соответственно, что семейство IV — IV] и И^ является нагруженным. Непрерывное (I х т)-расписание для семейства IV существует тогда и только тогда, когда существует непрерывное (/ х т)-расписаиие для Щ : если т четно или ^(И7))! = п.

Для нечётного тп остается рассмотреть задачу для нагруженного семейства IV при условиях: \\Vil = п., |Аг(1)| < п, ограничившись при этом семейством И^, = рп. Показано, что при |ЛГ(1У1)| = п - 1 и т = 5

непрерывное расписание существует, а для случая ¡Л^И^)! = п — 2 получены необходимые и достаточные условия существования непрерывного расписания.

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

Теорема 6.1.2. Если т = 5, Щ = {(3)1,2,3,...,«}, Щ = {(2)1,. (5)2, (5)3, (4)4,..., (4)п}, то непрерывное (I х т)-расписание для семейства ]¥ = И^ и И-'г суи1,ествует тогда и только тогда, когда в ассоциированном с И^ графе вершины г>1,№ и соответствующее буквам 1. 2 и 3, принадлежат, одной и той же компоненте.

Характерные для нечётного т — 2р + 1 проблемы проявляются, в общих чертах, в «пограничных условиях»: \\У\\ — п; гермх3 е {0,е И, уже при р = 2. Доказательство теоремы 6.1.1 опирается на критерий 2-факторизации графа. Для рассматриваемого случая соответствующий критерий неизвестен; его формулировка для графа С, ассоциированного с И^, является основной целью § 6.2.

Разбиение графа б = (IГ,Е) на остовные рёберно-нспсрсеекающиеся подграфы (?1 = (V, Е\) и <?2 = (V, Ег) обозначим /г = {С; = (I/,£,), г = 1,2}; сф) = <1,0>и - йс2У, ек(С1) = |£?1| - |£2|. Разбиение /г будем называть компромиссным, если |с/,(и)| ^ 1 Ч/г; 6 V и е,,{Сг) = 0.

Граф С -- (К, Е) будем называть частичио-4-регулярньш, если множество вершин допускает такое упорядочение V = {г^,..., г;,,.}, что при некотором к степень вершины и, равна: 5 при 1 < г < 2к; 2 при 2к < г < Зк; 4 при 3« < г < п. Предполагая, что вершины упорядочены нужным образом, частично-4-регулярный граф С? будем обозначать С = (УК,У,Е). где

Ук = {Уъ-.М-

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

Теорема 6.2.2. Пусть IV = И^ и - такой набор 1- и 2-предпхтаний, что = п и гер\\\] — {0,1,3} для любого _) 6 N. Если часгпичио-4-ркгулярный граф, ассоциированный с семейством. Н^. является связным и остовные рёберио-ч^пересекающиеся подграфы и <?2 в некотором компромиссном разбиении графа С также связны, то для

2.i

набора предписаний W существует непрерывное расписание.

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

Если к-й столбец (I х пг)-расипсання содержит лишь буквы, встречающиеся н расписании точно т раз, то расписание М будем называть к-разрео1сенныл1. Показано, что непрерывное (I х 5) -расписание для семейства 2-предписаний допускает преобразование к '¿-разреженному непрерывному расписанию.

Теорема 0.3.1. Непрерывное расписание для семейства 2-предписаний Í2, т(П) = 5, существует тогда и только тогда, когда

|П'| < 2JV(íi') для каждого П' С П.

В § 6.4 найдены необходимые и достаточные условия уплотнения расписания для семейства 2-иредиисапий в случае произвольного нечетного т.

Граф G = (У, Е'), где V' = {ь'ь • ■ ■, М. Е' = {еь..., е,} (и его двудольное представление), будем называть графом непрерывного расписания, если для семейства предписаний, ассоциированного с G", существует непрерывное (I х т)-расписание, где т = maxi¡u^ndcVi- Введем понятие одностороннего ра,списания: 1-разрежсннос (3-разреженное) непрерывное (/ х 3)-расгшсанис для семейства Í2 называется «левосторонним» («правосторонним»).

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

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

Будем говорить, что двудольный граф G = (X, У, Е) является (k¡, графом, если dex = k\ Vi G X, max,/ty <ку = fe.

Пусть р - целое положительное п в (2, 2р + 1)-графе G = (X, У, Е) существует множество Е' С Е, такое, что каждой вершине х € X инцидентно точно одно ребро, а каждой вершине у 6 У не более р ребер множества Е'. Подграф G' = {Х-, У, Е'), порожденный множеством ребер Е', называется р-каркасом графа G, если имеется вершина у € У, такая, что |/р{у}| — Р-

Пусть Р — {1,2.....р} и задана рёберная р-раскраека С: Е —> Р графа G - [X, У, Е), где для каждого i 6 Р имеется ребро е € Е : С{е) = г.

Количество рёбер i-го цвета, инцидентных вершине v, обозначим c(v,i). Рёберная р-раскраска (2, 2р +■ 1)-графа G = (X,Y,E) называется выровненной, сели: 1) в каждой вершине -х € X представлен точно один цвет; 2) для всех i,j е Р и у е Y: если day > 2, то \с(у, г) - c{y,j)\ ■< 1.

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

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

Приведем основной результат § 6.4.

Теорема 6.4.3. Пусть О. — семейство 2-предписаний ш;, заданных на множестве N: tn(f2) = 2р + 1; где р — некоторое целое положительное число. Непрерывное (I х т)-расписание для семейства Q существует тогда и только тогда, когда |Q'| ^ p|Ar(Q')|, Vfi' С Г2.

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

Литература

Основные публикации автора по теме диссертации

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

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

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

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

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

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

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

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

9. Магомедов, А. М. Условия существования непрерывных расписаний длительности пять [Текст] / А. М. Магомедов, А. А. Саиоженко /./

Вестник МГУ, сер. Вычислительная математика и кибернетика. - 2010. - Т. 34. - N 1. - С. 39-44.

10. Магомедов, А. М. Непрерывная Д-раскраска некоторых двудольных графов G с Д(G) - 5 и б ¡Текст] / А. М. Магомедов, Т. А. Магомедов, М. А. Магомедов // Вопросы современной науки и практики. Университет им. В. И. Вернадского. - 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 с.

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

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

Прочие публикации

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

17. Магомедов, A.M. Распознавание строчных букв кириллицы /' A.M. Магомедов, Т.А. Магомедов, М.А. Магомедов // Программа для ЭВМ. Свидетельство N 2010612224 о гос. регистр, прог. для ЭВМ от 02.03.2010.

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

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

20. Магомедов, A. M. Минимизация простоев ¡Текст] / / Тезисы Всесоюзного семинара «Системное моделирование производства, распределения и потребления». Часть 2. - 198G. - Воронеж. - 2 с.

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

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

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

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

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

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

- Санкт-Петербург. - С. Е56.

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

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

- Махачкала.

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

30. Магомедов, А. М. Условия связывасмости матрицы [Текст] / А. М. Магомедов, А. Рашайда /7 Вестник ДГУ. - 1998. - 2 с.

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

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

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

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

2003. - Махачкала, ДГТУ. - 4 с.

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

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

2004. - Махачкала. - С. 47.

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

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

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

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

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

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

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

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

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

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

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

48. Магомедов, А. М. NP-полнота задачи построения непрерывного расписания для специализированных процессоров [Текст] /7 Труды VIII международной конференции «Дискретные модели в теории управляющих систем», 6-9 апреля 2009 г., Москва, 2009 / Отв. ред. В. Б. Алексеев. В. А. Захаров. - 2009. М.: Издательский отдел факультета ВМиК МГУ им. М. В.Ломоносова; МАКС Пресс. - С. 203-205.

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

50. Магомедов, А. М. Об одной специальной рёберной раскраске двудольного мультиграфа степени не больше 5 [Текст] // Методы и средства обработки информации: Третья Всероссийская науч. конференция, Москва, 6-8 октября 2009 г.: Труды конференции /' Под ред. Л. Н. Королева. - 2009. - М.: Издательский отдел факультета ВМиК МГУ им. М.В.Ломоносова; МАКС Пресс. - С.2С6.

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 Montcnegrian Acadcmy of Sciences and Arts University of Montenegro Dorodnicyn Computing Center Russian Academy of Scicnccs (http://wwu.ccas.ru/optima2009/abstracts_e.html) .

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

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

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

55. Магомедов, A.M. Условия построения непрерывного расписания для двухэлементных предписаний [Текст] // Математические методы в технике и технологиях - ММТТ-23: сб. трудов XXIII Мсждунар. науч. конференции.: в 12 т. /под общ. ред. В. С. Балакирева. 2010. Саратов: Сарат. гос. тех. ун-т. - Т. 2. С. 58-60.

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

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

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

Введение

Глава 1. Построение и жёсткое уплотнение расписания

§ 1.1. Двухстадийное расслоение

1.1.1. Определение двухстадийного расслоения.

1.1.2. Выровненные разбиения.

1.1.3. Доказательство теоремы о двухстадийном расслоении

1.1.4. Вычислительные аспекты.

§ 1.2. КР-полнота задачи о непрерывном расписании

1.2.1. Примеры и применения.

1.2.2. МР-полнота задачи о непрерывном расписании

1.2.3. Полиномиальная сводимость трех задач.

1.2.4. №-полнота задачи уплотнения (ОД)-матрицы

1.2.5. Приложите к задаче передачи сообщений.

§ 1.3. Эвристический алгоритм уплотнения

1.3.1. Сдвиги по полупустым циклам. Гипотеза.

1.3.2. Жадный алгоритм решения задачи уплотнения

§ 1.4. Перечисление расписаний

1.4.1. Расписание с разделяемым доступом.

1.4.2. Построение двоичного дерева покрытий.

1.4.3. Завершение построения двоичного дерева.

1.4.4. Помечивание вершин, вывод рекуррентных формул

1.4.5. Организация вычислений.

Глава 2. Разбивающая реберная раскраска

§2.1. Непрерывная и разбивающая раскраски

2.1.1. Непрерывное расписание и разбивающая раскраска

2.1.2. Расписание длительности 4 для нагруженного семейства 2-предписаний.

2.1.3. Разбивающая раскраска (2р,р)-графа.

§ 2.2. Планарность и раскрашиваемость

2.2.1. Непланарность простого (6, 3)-графа.

2.2.2. Нераскрашиваемый простой (6,3)-граф.

§2.3. Применение динамического программирования

2.3.1. Примеры р-предписаний.

2.3.2. Сведения об ^-полноте.

2.3.3. Решение методом динамического программирования

глава 3. Нагруженные непрерывные расписания малой длительности

§3.1. Расписание длительности

3.1.1. Формулировка задачи составления учебного расписания

3.1.2. Отсутствие временных ограничений.

§ 3.2. Расписание длительности

3.2.1. Примеры уплотнимых и неуплотнимых расписаний

3.2.2. Теорема о дуэте.

3.2.3. Решение за полиномиальное время.

§3.3. Расписания длительности 5 без 1-предписаний

3.3.1. Построение сети

3.3.2. Теорема об условиях уплотнения.

Глава 4. Нагруженные непрерывные расписания для предписаний с взаимно-простыми длинами к, т — к или т

§4.1. Нагруженные расписания при к ^

4.1.1. Допустимый поток в сети Ni.

4.1.2. Уточнения и замечания. Случай к = 2, т ^ 0 (mod 2)

§4.2. Трудности уплотнения для предписаний длины А;, т — к или т

4.2.1. Каркас и пристройка расписания.

4.2.2. Разбиваемая пристройка.

4.2.3. Проблема выбора допустимого потока.

Глава 5. Методы факторизации и бездефектных потоков

§5.1. Нагруженные расписания для предписаний длины 2, m — 2, га

5.1.1. Комбинаторная форма теоремы Петерсена о факторизации

5.1.2. Модификация теоремы о факторизации графа . . . .•

§5.2. Условия уплотнения

5.2.1. Структура непрерывного расписания для предписаний длины 2,т-2иш.

5.2.2. Скелеты расписания и ассоциированного графа

§ 5.3. Бездефектный поток

5.3.1. Сеть с гомологичными парами дуг.

5.3.2. Теорема о бездефектном потоке.

5.3.3. Вычисление бездефектного потока.

Глава 6. Расписание для семейства 2-предписаний

§6.1. Разделяющая факторизация

6.1.1. Непрерывное расписание для нагруженного семейства

1- и 2-предписаний.

6.1.2. Факторизация, разделяющая два смежных ребра

6.1.3. Условия непрерывного размещения 1- и 2-предписаний

6.1.4. Факторизация, разделяющая две пары смежных рёбер

§ 6.2. Условия существования компромиссного разбиения для частично-4-регулярного графа

6.2.1. Пограничные условия.

6.2.2. Компромиссное разбиение для частично-4-регулярного графа.

6.2.3. Применение к построению расписания.

§6.3. Непрерывные расписания длительности 5 для 2-предписаний. Вопросы существования

6.3.1. Преобразования размещений с пресыщенными столбцами

6.3.2. Непрерывные расписания для 2-предписаиий.

§ 6.4. Непрерывные расписания нечетной длительности для 2-предписаний

6.4.1. Односторонние расписания.

6.4.2. Рёберная р-раскраска двудольного представления

6.4.3. Характеризация непрерывных расписаний

6.4.4. Проверка условий. Задача вычисления плотности графа

Введение диссертация по математике, на тему "Условия существования непрерывных расписаний"

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

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

Пусть множество N = {1,., п} требований (деталей, учебных групп, заданий и т.п.) обслуживается в системе Ь — {1,.,/} приборов (станков, преподавателей, процессоров и т. п.). Исходные данные к расписанию обслуживания: для каждого прибора ъ £ Ь задано "предписание" щ (неупорядоченный набор, мультимножество) с элементами из множества N, над каждым требованием из прибор г должен выполнить операцию единичной длительности; условия частичного предшествования отсутствуют, в любой момент времени каждое требование обслуживается не более чем одним прибором, и каждый прибор обслуживает не более одного требования. Обслуживание без простоев «активных» (приборов и др.) и «пассивных» компонентов (требований и др.) будем называть обслуживанием без «прерываний» и «задержек» соответственно.

Обозначим: П = {и>\,., щ }, гер^ — коэффициент (количество вхождений) элемента jEN в гер^ = гер^, т{£1) — тах(герп>7'). Всюду в дальнейшем предполагается, что наиболь-з шее число операций, предписанных отдельным приборам, не превышает наибольшее число операций, предписанных выполнить над отдельными требованиями (вертикальные скобки «| |» применены, как и в монографии [38], и для обозначения мощности, что не приводит к путанице со стандартным применением для обозначения абсолютной величины числа): шг\ ^ т(Г2), У г е Ц для такого семейства ^ расписание длительности т(Г2) существует всегда. Если герп 1 = • • • = герпп, то расписание (и семейство Q) будем называть нагрусисегтым. Процесс преобразования расписания к гшпрерывному расписанию, т.е. к расписанию без прерываний, будем называть уплотнением или жестким уплотнением] там, где это не вызывает разночтений, уплотнением удобно называть и само непрерывное расписание.

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

Задача о непрерывном расписании: существует ли для семейства предписаний непрерывное расписание длительности т(Г2) ?

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

Задачи жесткого уплотнения находят применение не только в задачах о расписаниях, но и в задачах сжатия информации (результаты Booth К. S., Lueker G. S., Fulkerson D.R., Gross O.A. о матрице со свойством связности) и в задачах оптимизации передачи сообщений по многоканальной сети.

Они тесно связаны также с направлением интервальной раскраски графов, первоначально введенным в работе А. С. Асратяна и Р. Р. Камаляна [1]. Наиболее важные результаты в данном направлении получили А. С. Асратян, Р. Р. Камалян, С. В. Севастьянов, В. Г. Визинг, В. А. Пяткин.

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

Задачи жесткого уплотнения выступают катализаторами достижений в области теории графов. Так, задача о непрерывном расписании длительности т(С1) для семейства О двухэлементных предписаний эквивалентна задаче о минимальном количестве цветов при жесткой инциденторной раскраске [27]. Её исследованрхе, в частности, инициировало новый подход (отличный, например, от принятого в [12]) к вычислению наибольшей плотности подграфа, что, в свою очередь, находит применение в изучении рейтинга сайтов и социальных сетей. Исследование жесткого уплотнения для предписаний мощности 2, т(П) — 2 или т(0,) привело к обобщению классического результата [21] о разбиении регулярного графа четной степени на 2-факторы, а также к выявлению полиномиально разрешимой подзадачи известной МР-полной задачи о потоке в сети с гомологичными дугами [37]. Из результата об ЫР-полноте задачи о непрерывном расписании вытекает КР-полнота одного из вариантов задачи об интервальной раскраске. Результаты по жесткому уплотнению тем самым помогают решить некоторые задачи теории графов.

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

Обзор результатов по теме диссертации и место результатов автора среди них. Семейство Г2 = {а^ | г е Ь} суть гиперграф с множеством вершин в каждом «ребре» которого вершина из N может присутствовать несколько раз. Для наглядности будем применять двудольное представление гиперграфа, для чего соотнесем семейству О, двудольный ассоциированный граф (7 = (X, У, Е): X = {х±,., хп}, У = {т/х,., ?//}, в котором количество ребер, соединяющих вершины хц € X и у1 е У, равно Отождествляя номер единицы времени обработки требования х^ прибором уг и номер цвета ребра получим задачу о рёберной раскраске графа С = (X, У, Е), эквивалентную задаче о расписании для семейства

Правильной рёберной раскраской графа цветами 1,2,3,. называется отображение /: Е(С£) —> {1,2,3,.}, такое, что /(ех) ф Ц^) для каждой пары смежных рёбер в\ и е^. Если для каждой вершины графа цвета инцидентных ребер образуют некоторый интервал, правильная рёберная раскраска графа цветами 1,2,3,. называется интервальной.

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

А. С. Асратян и Р. Р. Камалян ([1], 1987) получили ряд результатов об интервальной раскраске графа, в частности, показали приложение задачи раскраски двудольного графа к устранению «окон» в школьном расписании. Предположительно, впервые на приложение задачи раскраски двудольного графа к устранению «окон» расписания указано в заметке А.М.Магомедова ([66], 1985).

Не всякий граф обладает интервальной раскраской; например, полный граф не является, очевидно, интервально раскрашиваемым. Двудольный граф G = (X, У, Е), в котором степени всех вершин из X равны а, а степени всех вершин из Y равны будем называть (а:, /?)-бирегулярным графом. Понятно, что (а, а)-бирегулярный граф G = (X, У, Е) обладает интервальной раскраской, поскольку множество рёбер Е допускает разбиение на а совершенных паросочетаний Е\,., Еа, поэтому для получения интервальной раскраски достаточно присвоить всем рёбрам каждого Ег цвет г. Нетривиальные примеры: интервальной раскраской обладают деревья и полные двудольные графы — результаты Н. М. Hansen ([13], 1992) и Р. Р. Камалян ([17], 1990), а также (2, /?)-бирегулярные графы: в случае четного ß — результат H.M.Hansen ([13], 1992), в случае нечетного ß — результат D.Hanson, С. О. M.Loten и В. Toft ([14], 1998) и, независимо, А. V. Kostochka ([19], 1995). Если выполнены дополнительные ограничения |o;i| — ••• = \üji\ = 2, то при четном m(Q) непрерывное расписание длительности т(0) существует всегда; при нечетном т(П) необходимые и достаточные условия существования такого расписания найдены Магоме-довым A.M. ([58],2010).

А. С. Асратян и Р. Р. Камалян ([2], 1994) доказали, что: 1) каждый ин-тервально раскрашиваемый граф G обладает правильной рёберной А((?)-раскраской; 2) задача о существовании интервальной раскраски регулярного графа является NP-полной. В работе Р. Р. Камаляна ([17], 1990) показано, что полный граф интервально t-раскрашиваем, если (и только если) а + Ъ - НОД(а, +

В статье ([16], 1995) T.Jensen и В. Toft сформулировали утверждение, что любой бирегулярный граф обладает интервальной раскраской. D. Hanson и С. О. М. Loten ([15], 1996) доказали, что для интервальной раскраски (а, Ъ)~ бирегулярного графа потребуется по меньшей мере а+6—НОД(а, Ъ) цветов. Так, для интервальной раскраски (3,4)-бирегулярного графа потребуется не менее 6 цветов; вопрос существования интервальной 6-раскраски для любого (3,4)-регулярного графа до сих пор остается открытым. Для (3,4)-бирегулярного графа G А. В.Пяткин ([22], 2004) доказал, что: 1) задача о существовании кубического подграфа, содержащего все вершины, степени которых в G равны 4, NP-полна; 2) если такой подграф существует, то граф G — интервалыю 6-раскрашиваем. Опираясь на первый из упомянутых результатов, А. С.Асратян и С. J. Casselgren доказали ([3], 2008) NP-полноту задачи о существовании интервальной 6-раскраски для (3, 6)-бирегулярного графа. В статье А. М. Магомедова ([85], 1991) обсуждается вопрос о роли кратных рёбер в качестве препятствий для интервальной 6-раскрашиваемости (3, 6)-бирегулярного графа и построен пример простого (без кратных рёбер) (3, 6)-бирегулярного графа, не допускающего интервальной 6-раскраски.

Ассоциированный с семейством Q двудольный граф G = (X, У, Е) будем называть (hi, ^ &2)-графом, а семейство — соответственно (ki, ^ &2)-семейством, если dGxj = ki Vxj е X; dGiji < к2 V^ G У. (0.1)

В статье А. М. Магомедова ([86], 1991) доказано, что задача о непрерывном расписании для (4, ^ 4)-семейства разрешима за полиномиальное время.

Отметим, что приведенное в [86] доказательство без существенных изменений переносится и на "близкое" утверждение о разрешимости задачи интервальной А(С)-раскраски двудольного графа G, A(G) = 4, за полиномиальное время. Это утверждение было сформулировано и доказано K.Giaro в ([11], 1997), где получен и существенно более сильный результат об NP-полноте соответствующей задачи при А(С) = 5. В заметке А. М. Магомедова ([66], 1985) рассмотрены необходимые условия раскраски для (5, ^ 5)-графа.

NP-полноту задачи об интервальной раскраске двудольного графа в общем случае доказал С.В.Севастьянов ([39], 1990). ChoY. и Sahni S. доказали ([6], 1981) NP-полноту задачи о непрерывном расписании при дополнительном условии: если начато обслуживание требования некоторым прибором, то до завершешш этого обслуживания (возможно, с задержками), другой прибор не может обслуживать данное требование. Доказательство NP-полноты задачи о непрерывном расписании в формулировке, несколько отличной от нашей, получили А. В. Струсевич и Е. Р. Ерошина ([40], 1989). Видоизменением рхдеи этих авторов А.М.Магомедов показал, что задача о непрерывном расписании является NP-полной даже при дополнительных ограничениях на мощности предписаний ([53], 2009).

Пусть расписание для семейства Q задана матрицей М размеров I х т с элементами из множества {0} U N: если Mi^ = j, то при j е N прибор г обслуживает требование j в момент времени к, при j = 0 прибор г в момент времени к не обслуживает никакого требования. Элементы мноэ/сества N всюду в дальнейшем будем называть буквенными элементами {или, коротко: буквами).

Пусть все буквенные элементы матрицы М заменены на единицы и требуется проверить, можно ли, с сохранением количеств нулей pi единиц в каждой линии (столбце или строке), преобразовать полученную матрицу к такому виду, где единицы в каждой строке располагаются рядом, в подряд идущих ячейках. Из результата Fulkerson D.R., Gross O.A. ([10], 1965) вытекает, что задача разрешима за полиномиальное время, если в таком преобразовании допускаются лишь операции перестановки столбцов. А.М.Магомедов показал (гл. 1), что при отсутствии ограничений на разрешённые операции задача становится NP-полной.

Если |cji| = • • • = \lüi\ = 2, то для каждого LJi = (¿i, ¿2) G О заменим в двудольном ассоциированном графе конструкцию из рёбер (ж^,^), (%i2,yi) и вершины yi одним новым ребром (х^, Х{2). Полученный граф G = (X, Е) назовем графом, ассоциированным с О; «половинки» нового ребра, инцидентные соответственно вершинам х^ и Х{2, называются сопряэ/сетсыми инциденторами (под инцидентором понимается упорядоченная пара, состоящая из вершины pi ргацидентного ей ребра). В докторской диссертацрш А. В. Пяткрша ([36], 2009) исследованы разнообразные аспекты задачи ин-циденторной раскраскр! — определения минимального числа цветов, в которые можно раскрасить все инциденторы графа с соблюдением заданных условий на цвета смежных (примыкающих к одной и той же вершрше) и сопряженных инцртденторов. Как показал А. В. Пяткин, модель инцидеитор-ной раскраски эффективна при исследованрш задачи передачи сообщенрШ в локальной сети связи [35]—[34] pi в задачах теории расписаний. В нашей ^термршологир! один из вопросов, поставленных в статье В. Г. Визинга ([27], 2005) формулируется как вопрос об NP-полноте задачи определения минимального количества цветов, позволяющих раскрасить инциденты неориентированного мультиграфа так, чтобы: а) все смежные инциденторы имели разные цвета; б) цвета любой пары сопряженных инциденторов различались точно на 1. Задача эквивалентна задаче о существовании непрерывного расписания длительности m(Q) для семейства Г2 из 2-предписаний.

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

Важнейшими для нашего рассмотрения явились результаты следующих исследователей:

• А. А. Сапоженко (идеи известной книги [28] по дискретной математике явились ключевыми для некоторых из рассмотренных в работе задач; кроме того, благодаря советам проф. А. А. Сапоженко исследованы несколько значимых для целостности работы задач),

• В. К. Леонтьев (работе «Дискретные экстремальные задачи 25» автор обязан первоначальными сведениями о проблеме NP-полноты),

• S. A. Even, A. Itai, A. Shamir (классическая задача о составлении учебного расписания аккумулирует ряд важных направлений исследования),

• S. Sahni (NP-полнота задачи построения оптимального расписания для трех приборов, когда требование, обслуживание которого начато некоторым прибором, не может обслуживаться другим прибором до завершения его обслуживания данным прибором),

• В. А. Струсевич и Е. Р. Ерошина (NP-полнота аналогичной задачи для не менее двух приборов в предположении, что в процессе обслуживания каждого требования не допускаются задержки),

• С. В. Севастьянов (доказательство NP-полноты задачи об интервальной раскраске графов явилось толчком к выяснению сложностного статуса ряда задач как теории графов, так и теории расписаний),

• D.R.Fulkerson и O.A.Gross (задача о матрице со свойством связности),

• В. Г. Визинг (вклад данного исследователя в теорию графов общеизвестен; в частности, исследование задачи об инциденторной раскраске имеет важное приложение к задачам о непрерывных расписаниях),

• А. В. Пяткин (задачи об инциденторной раскраске, о кубическом подграфе в (4,3)-бирегулярном графе и др.),

• А. С. Асратян и Р. Р. Камалян (интервальная раскраска различных видов двудольных графов),

• А. С. Асратян и С. J. Casselgren (задача о 6-интервальной раскраске (6,3)-брфегулярного графа и др.),

• К. Giaro (сложность задач интервальной раскраски двудольного графа G с A(G) = 4 и 5),

• Н. М. Hansen, D. Hanson, С. О. М. Loten и В. Toft (утверждение об интервальной раскрашиваемости двудольного (2, /3)-бирегулярного графа).

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

Методика исследований. В работе используются как известные методы, так и новые методы, разработанные автором для решения некоторых задач. К числу известных относятся методы теории графов (паро-сочетания в двудольных графах; реберно-вершинные инцидентные паросо-четания; потоки в сетях; разновидности ребёрной раскраски: правильной, непрерывной, интервальной, инциденторной), комбинаторики (разбиения; эвристические методы; методы динамического программирования), теории сложности вычислений (метод полиномиальной сводимости). Новые методы pi подходы: метод построения непрерывного расписания длительности 4 (гл. 3), метод вычисления бездефектного потока и модификация метода 2-факторизации (гл. 5), а также новый подход к вычислению наибольшей плотности подграфа (гл. 6).

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

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

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

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

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

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

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

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

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

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

7. Условия и алгоритм уплотнения для семейства предписаний длины 2, т — 2 и т.

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

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

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

Всесоюзная научная конференция по моделированию и оптимизации учебного процесса с использованием ЭВМ (Московский Энергетический Институт, 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, September 21-25, 2009); XVIII международная школа-семинар "Синтез и сложность управляющих систем" им. академика О. Б. Лупанова (Пенза, 2009); X международная школа-семинар "Дискретная математика и приложения" (МГУ, 2010); XXIII Международная научная конференция "Математические методы в технике и технологиях" (Саратов, 2010).

Диссертация прошла апробацию на следующих семинарах: на семинаре Отдела математики и информатики Дагестанского научного центра РАН 11.02.2010 (руководитель И. И. Шарапудинов); на семинаре Отдела математических проблем распознавания и методов комбинаторного анализа сектора математических методов распознавания и прогнозирования ВЦ РАН 20.04.2010 (руководитель В.К.Леонтьев); на заседаниях семинаров кафедры математической кибернетики факультета ВМиК МГУ 22.05.2009 и 23.04.2010 (руководитель А. А. Сапоженко), на межвузовском семинаре г. Махачкала 23.11.2010 (руководитель А. К. Рамазанов).

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

Под руководством автора по теме диссертации защищены две кандидатские диссертации (А.Рашайда — в 2000 г., А.З.Якубов — в 2003 г.), одна представлена к защите (М. М. Сиражудинов). Несколько студенческих работ, выполненных под руководством автора, удостоены дипломов региональных, российских и международных конкурсов.

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

Проследим основные маршруты графа исследования, формулируя попутно задачи, возникшие при рассмотрении различных аспектов проблемы существования непрерывного расписания.

В исходных данных к составлению расписания учебных занятий, наряду с семейством предписаний, обычно оговаривается ряд дополнительных ограничений. Наиболее часто встречаются ограничения двух типов: на промежутки времени, разрешеннные тем или иным преподавателям, или на аудитории, разрешенные для тех или иных занятий. Если ограничения первого типа могут служить причиной NP-пoлнoты задачи [9], то, как показано в §1.1, ограничения второго типа не оказывают столь существенного влияния на статус сложности задачи.

За исключением § 1.4, всюду в работе предполагается условие неразделяемого доступа. Своеобразие рассмотренного в §1.4 «компьютерного» решения задачи перечисления расписаний заключается в том, что программным путем сгенерирована система рекуррентных формул для определения мощности семейства всех расписаний для случая, когда параметр т (длительность расписания) принимает «малые» значения, а диапазон значений параметра п (количество учебных групп) «значителен»; например, т ^ 10, п > 100.

Если, например, при т = 5 вычисление начальных элементов рекуррентных последовательностей может быть без труда выполнено переборным путем, то при больших значениях т (например, т — 50 при п — 120) задача вычисления начальных элементов перерастает в нетривиальную проблему.

Задача: построить алгоритм (с последующим воплощением в компьютерной программе), способный решить задачу перечисления расписаний (в том смысле, который принят в § 1.4) для значений тип, достигающих нескольких сотен.

По определению непрерывного расписания, наименьшее значение длительности расписания, при котором условие непрерывности может нарушиться, равно 3. Результат п. 6.4.1 о том, что (2,^ 3)-граф С = (X, У, Е) является графом непрерывного расписания тогда и только тогда, когда существует полное паросочетаиие множества X с множеством У (теорема 6.4.1), используется в доказательстве одного из наиболее важных результатов работы — об условиях существования непрерывных расписаний нечетной длительности для семейства 2-предписаний О, (теорема 6.4.3 в §6.4).

Возможности успешного (с точки зрения существования эффективных точных алгоритмов) уплотнения расписания для семейства Q исчерпываются уже при т(Г2) .= 4: в п. 3.2.2 доказано, что нагруженное расписание класса Р1^2Ъ 4} Д0ПУскает уплотнение тогда и только тогда, когда обладает дуэтом; при т(Г2) = 4 задача о непрерывном расписании допускает решение за полиномиальное время. В § 3.3 задача решена при m(Q) — 5 для класса нагруженных семейств вида Р^ъАьу Заметим, что результат Giaro К. [11] об NP-полноте задачи при m{ß) = 5 не вполне исчерпывает рассмотрение. В частности, представляет интерес следующая задача.

Задача: является ли задача о непрерывном расписании длительности 5, в которой количество букв в каждой строке принадлежит множеству Q — {2,3}, NP-полной ?

Заметим, что если Q = {2} или Q = {3}, то задача разрешима за полиномиальное время. Неизвестно и решение следующей задачи.

Задача: существует ли класс задач |Q| > ¿)ля которого задача о непрерывном расписании разрешима за полиномиальное время ?

Теорема 1.2.1 об NP-полноте задачи о непрерывном расписании получила в п. 1.2.2 следующее уточнение: задача остается NP-полной даже в случае, когда требуется, чтобы в каждой строке все равные буквы размещались рядом, а также в случае предписаний длины не более [у] (теорема 1.2.2).

Задача: найти наибольшее к, такое, что задача о непрерывном расписании для семейства О. = остается NP-полной при \ш{\ ^ m(Q)/k.

В связи с доказанной в п. 1.2.4 теоремой 1.2.5 об NP-полноте задачи «Уплотнение (ОД)-матрицы» сформулируем следующую задачу.

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

Суть одной из "точек ветвления" исследования проста (лемма 2.1.4): при р = q = 2 для нагруженного семейства р-предписаний fl со свойством т = m(Q) = pq всегда существует непрерывное расписание длительности т.

• Направление 1: для фиксированного q = 2 задача исследуется при р = 3,4,.

Теорема 2.1.3 утверждает, что для произвольного р > 2 можно указать нагруженное семейство ^-предписаний Q, ш(Г2) = 2р, для которого непрерывное расписание не существует. Подчеркнем, что даже случай р = 3 представляет серьезные трудности. Перечислим некоторые из них. Стремлением выяснить роль кратных рёбер среди причин, препятствующих построению непрерывного расписания, объясняется рассмотрение вопроса непланарности простого (6, 3)-графа (теорема 2.2.1) и внимание, уделенное в §2.2 построению простого пераскрашиваемого (6, 3)-графа с количеством вершин, равным 60.

Задача: найти простой иераскрашиваемый (6,3)-граф с наименьшим числом вершин.

Итог в поиске эффективного точного алгоритма подводит приведенный в п. 2.3.2 результат A. S.Asratyan и С. J. Casselgren [3]: задача об интервальной 6-раскраске (6,3)-графа NP-полна. Этим фактом инициирован разработанный в 2.3.2 метод динамического программирования; аналогичное объяснение имеет и выяснение в §4.2 роли разбиваемой пристройки.

• Направление 2: постоянная длина предписаний принимается равной 2 и рассматриваются нагруженные семейства Г2 с т(Г2) = 2р. Итог данного направления подводит комбинаторная форма теоремы Пе-терсена о факторизации (теорема 5.1.1).

Этот, на первый взгляд, «завершающий» пункт является, в действительности, отправным сразу для нескольких направлений.

• С одной стороны, результат, достигнутый для семейств 2-предписаний Г2 с m(Q) = 2р, доведен до общего случая семейств 2-предписаний в §6.4, где рассмотрен случай нечетного m(Q): найдены необходимые и достаточные условия существования непрерывного расписания (теорема 6.4.3); в п. 6.4.4 предложено решение задачи вычисления плотности графа и построен эффективный алгоритм проверки этих условий. В отличие от подхода, предложенного в [12], алгоритм предоставляет принципиальную возможность учитывать структуру графа при оценке сложности.

Задача: пусть М(у,е) - время, требуемое для нахождения пропускной способности минимального разреза в сети с v вершинами и е ребрами; существует ли алгоритм вычисления в графе G — (V,E), \V\ — n, \Е\ — т, подграфа наибольшей плотности за время, меньшее, чем 0(М(п, п + т) logn) ?

• С другой стороны, представляется естественным расширить класс семейств с четным т(Г2) путем включения семейств, содержащих, наряду с 2-предписаниями, и предписания длины т-2ит. Отметим, что для случая нечетного т задача для семейств с предписаниями аналогичного типа решена в п. 4.1.2, где найдены необходимые и достаточные условия.

В случае четного т потребовались новые теоретико-графовые результаты: в §5.1 получены обобщения теоремы Петерсена о 2-факторизации (теоремы 5.1.2 и 5.1.3), в §5.2 изучена структура непрерывного расписания для нашего случая и задача сведена к существованию скелета расписания (теорема 5.2.1), а в § 5.3 разработан метод бездефектного потока, применением которого удалось установить, что рассматриваемая подзадача известной ЫР-полной задачи о максимальном потоке в сети с гомологичными дугами допускает решение за полиномиальное время. На основе перечисленных результатов сформулированы необходимые и достаточные условия существования непрерывного расписания.

• Для обозначения третьего направления укажем на простое наблюдение: теорема Петерсена о 2-факторизации связного графа четной степени т допускает элементарное доказательство, если т = 2к, к € Z+\ к — 2, 3,В самом деле, построим эйлеров цикл и пометим его последовательные рёбра чередующимися метками 1 и 2 (существенно, что число рёбер чётно). Затем повторим действия для каждого из двух остовных подграфов степени 2к~г, образованных 1- и 2-рёбрами соответственно, и так до тех пор, пока не получим остовные подграфы степени 2.

Данный подход с простым подготовительным разбиением на две части с последующими переразбиваниями, дополненный методом постепенного приближения к некоторому нужному свойству, достигаемому в заключительной итерации, применяется и в других местах работы: так, леммы 1.1.1 и 6.4.2 являются подготовительными для лемм 1.1.4 и 6.4.3 соответственно, которые, в свою очередь, используются в доказательствах теорем 1.1.1 и 6.4.3.

В связи с теоремой Петерсена напомним сформулированную в § 1.3 задачу.

Задача: заданы четное т и нагруженное (I х т)-расписание для 2-предписаний; верно ли, что такое расписание всегда можно преобразовать к непрерывному расписанию путем выполнения сдвигов по полупустым циклам?

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

Список источников диссертации и автореферата по математике, доктора физико-математических наук, Магомедов, Абдулкарим Магомедович, Махачкала

1. Асратян, А. С. Интервальные раскраски рёбер мультиграфа Текст. / А. С. Асратян, Р. Р. Камалян // Прикладная математика. - 1987. -Вып. 5. - Ереван: Изд-во Ереван, ун-та. - С. 25-34.

2. Asratian, A. S. Investigation on interval edge-colorings of graphs Text. / A. S. Asratian, R. R. Kamalian // J.Combin. Theory Ser. 1994. - В 62 P. 34-43.

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

4. Booth, K. S. PQ tree algorithms Text. // Doctoral Thesis, Dept. of Electrical Engineering and Computer Science. 1975. - University of California, Berkley C. A.

5. Brooks, R. L. On colouring the nodes of a network Text. // Proc. Cambridge Phil. Soc. 1941. - Vol. 37. - P. 194-197.

6. Cho, Y. Preemptive scheduling of independent jobs with release and due times on open, flow and job shops Text. / Y. Cho, S. Sahni // Oper. Res.,- 1981. V. 29,- No. 3. - P. 511-512.

7. Chvatal, V. Text. // Private communication. 1976.

8. Edmonds, J. Theoretical improvements in algorithmic efficiency for network flow problems Text. / J. Edmonds, R. M. Karp // Journal of the ACM. 1972. - 19. - P. 248-264.

9. Even, S. On the complexity of timetable and integral multi-commodity flow problems Text. / S. Even, A. Itai, A. Shamir // SIAM J. on Сотр.- 1976. V. 5. - No. 4. - P. 691-703.

10. Fulkerson, D. R. Incedence matrices and interval graphs Text. / D.R. Fulkerson, 0. A. Gross // Pacific J. Math. 1965. - 15. - P. 835-855.

11. Giaro, K. The complexity of consecutive A-coloring of bipartite graphs: 4 is easy, 5 is hard Text. // Ars Combin. 1997. - 47. - P. 287-298.

12. Goldberg, A. V. Finding a maximum density subgraph Text. // Technical Report Identifier: CSD-84-171.

13. Hansen, H. M. Scheduling with minimum waiting periods (in Danish) Text. // Master's Thesis, Odense University. 1992. - Odense, Denmark.

14. Hanson, D. On interval colourings of bi-regular bipartite graphs Text. / D. Hanson, C.O.M. Loten, B. Toft // Ars Combin. 1998. - 50. -P 23-32.

15. Hanson, D. A lower bound for interval colouring bi-regular bipartite graphs Text. / D. Hanson, C.O.M. Loten // Bull. Inst. Combin. Appl. 1996. - 18. - P 69-74.

16. Jensen, T. Graph coloring problems Text. / T. Jensen, B. Toft // Wiley-Interscience. 1995. - John Wiley & Sons, Inc., New York.

17. Kamalian, R. R. Interval edge-colorings of graphs Text. // Doctoral Thesis, Novosibirsk. 1990.

18. Karp, R. M. Reducibility among combinatorial problems Text. / R. M. Karp in R. E. Miller and J.W. Thatcher (eds.) // Complexity of Computer Computations. 1972. - Plenum Press, New York. - P. 85103.

19. Kostochka, A. V. Unpublished manuscript Text. 1995.

20. Malhotra, V. M. An 0(\V|3) algorithm for maximum flows in networks Text. / V.M. Malhotra, M. Pramodh Kumar, S.N. Maheshwari // Inform. Process. Lett. 1978. - 7. - P. 277-278.

21. Petersen, J. Die theorie der regulären graphen Text. // Acta Math. -1891. 15. - P. 193-220.

22. Pyatkin, A. V. Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs Text. // J. of Graph Theory. 2004. -Vol. 47. - No. 2. - P. 122-128.

23. Reinhard, D. Graph Theory Text. // Fourth Edition. 2010. - SpringerVerlag, New York. - 451 p.

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

25. Ullman, J.D. Complexity of sequencing problems Text. / J. D. Ullman in G. F. Goffman (ed) // Computer and Job Shop Theory. 1976. - New York: John Wiley. - P. 139-164.

26. Берж, К. Теория графов и ее применения Текст. М.: Наука, 1962.- 320 с.

27. Визинг, В. Г. Жёсткая раскраска инциденторов в неориентированных мультиграфах Текст. // Дискрет, анализ и исслед. операций. Сер. 1. 2005. - Т. 12. - N 3. - С. 48-53.

28. Гаврилов, Г. П. Задачи и упражнения по дискретной математике: Учеб. пособие. 3-е изд., перераб. Текст. / Г. П. Гаврилов, A.A. Са-поженко. - М.: ФИЗМАТЛИТ, 2005. - 416 с.

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

30. Гэрри, М. Вычислительные машины и труднорешаемые задачи. Текст. / М. Гэрри, Д. Джонсон. М.: Мир, 1982. - 416 с.

31. Найк, Д. Стандарты и протоколы Интернета Текст. М.: Издательский отдел «Русская редакция»ТОО «Channel Trading Ltd.», 1999. -384 с.

32. Новиков, Ф. А. Дискретная математика для программистов Текст.- СПб.: Питер, 2001. 304,

33. Ope, О. Теория графов Текст. М.: Наука. Гл. ред. физ.-мат. лит., 1980. - 336,

34. Плеханова, Н. С. Передача сообщений в локальной сети с двумя центральными ЭВМ Текст. / Н. С. Плеханова, A.B. Пяткин // Дискрет. анализ и исслед. операций. Сер. 1. 2002. - Т. 9. - N 2. - С. 91-99.

35. Пяткин, А. В. Некоторые задачи оптимизации расписания передачи сообщений в локальной сети связи Текст. // Дискрет, анализ и исслед. операций. 1995. - Т. 2. - N 4. - С. 74-79.

36. Пяткин, А. В. Раскраска инциденторов и другие задачи на графах: алгоритмический аспект Текст. / Докторская диссертация. 2009.

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

38. Свами, M. Графы, сети и алгоритмы Текст. / М. Свами, К. Тхула-сираман. М.: Мир, 1984. - 455 с.

39. Севастьянов, C.B. Об интервальной раскрашиваемости рёбер двудольного графа Текст. // Методы дискретного анализа. 1990. -Т. 50. - С. 61-72.

40. Танаев, В. С. Теория расписаний. Многостадийные системы Текст. / B.C. Танаев, Ю.Н. Сотсков, В. А. Струсевич. М.: Наука, 1989. -328 с.

41. Форд, JI.P. Потоки в сетях Текст. / JI. Р. Форд, Д. Р. Фалкерсон. -М.: Мир, 1966. 276с.

42. Основные публикации автора по теме диссертации

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

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

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

46. Магомедов, А. М. Двумерная графика в проектах Delphi Текст. // Вестник Дагестанского научного центра РАН. 2004. - N 18. - С. 5-8.

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

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

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

50. Магомедов, A.M. Уплотнение расписания с директивным сроком, кратным количеству занятий каждого преподавателя Текст. // Ма-тем. заметки. 2009. - Т. 85. - N 1. - С. 65-72.

51. Магомедов, А. М. О существовании компромиссного разбиения для частично-4-однородного графа Текст. // Матем.заметки (принята к печати на март 2011 г.).

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

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

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

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

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

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

58. Магомедов, А. М. Расписание с двухэлементными предписаниями Текст. // Известия Саратовского гос. университета. Новая серия. Серия Математика. Механика. Информатика. Принята к печати в 2011 г.1. Прочие публикации

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

60. Магомедов, А. М. Распознавание строчных букв кириллицы / А. М. Магомедов, Т. А. Магомедов, М. А. Магомедов // Программа для ЭВМ. Свидетельство N 2010612224 о гос. регистр, прог. для ЭВМ от 02.03.2010.

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

62. Магомедов, А. М. Сдвиг по полупустому циклу для уплотнения графика работы нескольких исполнителей Текст. // Деп. в ВИНИТИ N 7225-84.

63. Магомедов, А. М. Распределение элементов в фрагменте таблицы Кэли Текст. // Деп. в ВИНИТИ N 7222-84. 8 с.

64. Магомедов, А. М. К вопросу минимизации разделяющих нулей в строках матрицы Текст. / А. М. Магомедов // Деп. в ВИНИТИ N 7224-84. 8 с.

65. Магомедов, А. М. Раскраска графа с непрерывным спектром Текст. // Деп. в ВИНИТИ N 478-85.

66. Магомедов, А. М. Аналог теоремы Холла Текст. // Деп. в ВИНИТИ N 447-85. 7 с.

67. Магомедов, А. М. Теорема о п.н.п. с ограничениями Текст. // Деп. в ВИНИТИ N 7155В-85. 7 с.

68. Магомедов, А. М. Уплотнение булевой матрицы Текст. // Деп. в ВИНИТИ N 6530-85. 7 с.

69. Магомедов, А. М. Построение паросочетаний Текст. // Деп. в ВИНИТИ N 8409В-85. -8 с.

70. Магомедов, А. М. Составление школьного расписания на ЭВМ Текст. // Деп. в ЦНТИ Педагогика N 221-85. 18 с.

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

72. Магомедов, А. М. Минимизация простоев Текст. // Тезисы Всесоюзного семинара «Системное моделирование производства, распределения и потребления». Часть 2. 1986. - Воронеж. - (2с).

73. Магомедов, А. М. Выделение двух множеств непересекающихся двудольных паросочетаний Текст. // Деп. в ВИНИТИ N 7332-86. -9 с.

74. Магомедов, А. М. К вопросу о существовании непересекающихся паросочетаний Текст. // Деп. в ВИНИТИ N 7957-86. 4 с.

75. Магомедов, А. М. Выделение групп двудольных паросочетаний с ограничениями Текст. // Деп. в ВИНИТИ N 8069-В-86 Зс.

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

77. Магомедов, А. М. Уплотнение матрицы перестановок из шести столбцов Текст. // Деп. в ВИНИТИ N 8700-В87. 8 с.

78. Магомедов, А. М. Тривиальное учебное расписание Текст. // Деп. в ЦНТИ Педагогика. 1989. - 9 с.

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

80. Магомедов, А. М. Нахождение кратчайших периодических путей в графе Текст. // Деп. в ВИНИТИ 10.11.89 6759-1989. 8 с.

81. Магомедов, А. М. Об одном доказательстве КР-полноты задачи о 3-раскрашиваемости графа Текст. / А. М. Магомедов, Ш. М. Алиев // Деп. в ВИНИТИ 10.11.89 6760-1989.

82. Магомедов, А. М. Сильная ЫР-полнота задачи о матрице со свойствами псевдосвязности Текст. // Деп. в ВИНИТИ 6761-138910.11.89. -6с.

83. Магомедов, А. М. Псевдополиномиальный алгоритм решения задачи уплотнения матрицы для одного частного случая Текст. / А. М. Магомедов // Деп. в ВИНИТИ 6762-1989 (5с).

84. Магомедов, А. М. К вопросу об условиях уплотнения матрицы из 6 столбцов Текст. // Деп. в ВИНИТИ, 1991. 6 с.

85. Магомедов, А. М. Условия и алгоритм уплотнения матрицы из 4 столбцов Текст. // Деп. в ВИНИТИ 175-В92, 1992. 7 с.

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

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

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

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

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

91. Магомедов, А. М. К вопросу об оптимальном размещении ТЭЯ-программ Текст. // Вестник ДГУ. 1997. - 5 с.

92. Магомедов, А. М. Условия связываемости матрицы Текст. / А. М. Магомедов, А. Рашайда // Вестник ДГУ. 1998. - 2 с.

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

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

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

96. Магомедов, А. М. КР-полные проблемы интерфейса 1ЕЕЕ-1394 Текст. // Тезисы Всероссийской научно-технической конференции «Современные информационные технологии в управлении», ДГТУ. -2003. Махачкала, ДГТУ. - 4 с.

97. Магомедов, А. М. Равнодефицитное разбиение списка по элементу Текст. // Вестник ДГУ. 2004. - Зс.

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

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

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

101. Магомедов, А. М. Дефрагментация матриц с 2q и Зq ненулевыми элементами в строке Текст. // Региональная науч.-практ. конференция «Компьютерные технологии в науке, экономике и образовании», 17-19 ноября 2005. 2005. - 4с.

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

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

104. Магомедов, A.M. Условия существования расписаний малой длительности Текст. // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омский гос. ун-т, 29 июня 4 июля 2009 г. - 2009. - С. 148.

105. Магомедов, A.M. Разбиение семейства мультимножеств Текст. // Дискретная математика, алгебра и их приложения: Тез. докл. Между-нар. науч. конф. Минск, 19-22 октября 2009 г. 2009. - Мн.: Институт математики HAH Беларуси. - С. 101-102.

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