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

• Автор: Магомедов, Абдулкарим Магомедович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2011
• Место защиты: Махачкала
• Количество страниц: 183 с. : ил.

Содержание
Введение

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

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

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

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

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

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

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

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

1.2.2. ИР-полнота задачи о непрерывном расписании
1.2.3. Полиномиальная сводимость трех задач
1.2.4. ИР-полнота задачи уплотнения (0,1)-матрицы
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. Сведения об NP-полноте
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. Допустимый поток в сети N
4.1.2. Уточнения и замечания. Случай к = 2, т ф 0 (mod 2)
§4.2. Трудности уплотнения для предписаний длины к, т — к или тп
4.2.1. Каркас и пристройка расписания
4.2.2. Разбиваемая пристройка
4.2.3. Проблема выбора допустимого потока

ГЛАВА 5. Методы факторизации и бездефектных потоков
§ 5.1. Нагруженные расписания для предписаний длины 2, т — 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-предписапий

Следствие 1.1.1. Пусть cri, cr2 € Z+. Допустимый поток f вТ12, удовлетворяющий верхним и нижним потоковым ограничениям:
T,£±%-Xs* fi
<Т<Тг s 0 0 0 2 ’
разлагается на сумму из о потоков fi, являющихся допустимыми потоками в Т2 с верхними и нижними потоковыми ограничениями вида:
T.,xs9n a2Mjto Ст2 —> zk о °>sk >т
-Ч а2 s 0 0 к 0 и
Причем, поток Д следует выбрать как допустимый поток в сети:
гп „ „ sign f{e) 4j_ о-2 _ fT24 лг,
J - О >- Д/ о О—
°2 ' max(/(e)-((Ti-l), 0) max(/(e)-( Пусть условия теоремы 1.1.2 выполнены и / — максимальный поток
величины |A|pq в сети Т2- Изложим алгоритм вычисления Ej и Мг-j.
Алгоритм разбиения
Начало
1. <7i :=р;
2. Пока <7i ф 0, выполнять 3-11:

3. Вычислить поток g (g индуцирует Ef):

Я max(/-(t7i-l), 0) тах(/—(ег,-1)<7, 0) max(/-((Ti-l)g<5fe, 0)
4. / := / -9]
5. <72 := q;
6. Пока cr2 ф 0, выполнять 7—10:

7. Вычислить допустимый поток h в сети:
1 „ sign f(xs,yt)
1 1 ° > ° -ГГ~
тах(/-(сг2-1), 0) тах(/-(<г2-1), 0) тах(/—(о-2-1)$&, 0)
8. Вывод в качестве Му всех дуг (ж.,, у4). для которых Ь{х8,у) = 1;
9. д д — Ь
10. <72 := <72 - 1;

11. <71 := <71 — 1;

Конец