Исследование количественных характеристик наследственных классов ориентированных и цветных графов

• Автор: Сорочан, Сергей Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Нижний Новгород
• Количество страниц: 149 с. : ил.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
I. ОБ ЭНТРОПИИ НАСЛЕДСТВЕННЫХ КЛАССОВ ОРИЕНТИРОВАННЫХ И ЦВЕТНЫХ ГРАФОВ. МИНИМАЛЬНЫЕ ПО ВКЛЮЧЕНИЮ КЛАССЫ В СЛОЯХ С НУЛЕВОЙ И НАИМЕНЬШЕЙ ПОЛОЖИТЕЛЬНОЙ ЭНТРОПИЕЙ
Основные понятия главы I
1. Лемма о равномерном покрытии и существование энтропии наследственных классов ориентированных и цветных графов
2. Минимальные по включению наследственные классы ориентированных и цветных графов, имеющие нулевую энтропию
3. Наименьшее положительное значение энтропии наследственных классов ориентированных и цветных графов. Описание минимальных по включению классов в слое с этим значением
3.1. Двудольные орграфы, их матрицы и свойства
3.2. Наименьшее положительное значение энтропии наследственных классов орграфов. Минимальные по включению классы в слое с этим значением
3.3. Двудольные цветные графы
3.4. Наименьшее положительное значение энтропии наследственных классов цветных графов. Минимальные по включению классы в слое с этим значением
3.5. Разрывность множеств значений энтропии наследственных классов ориентированных и цветных графов
4. Двудольная энтропия наследственных классов двудольных цветных и ориентированных графов
Выводы к главе I
II. ХАРАКТЕРИЗАЦИЯ И РАСПОЗНАВАНИЕ ОРГРАФОВ ИЗ НАСЛЕДСТВЕННЫХ КЛАССОВ С НАИМЕНЬШИМ ПОЛОЖИТЕЛЬНЫМ ЗНАЧЕНИЕМ ЭНТРОПИИ
Основные понятия и содержание главы II

& 1. О связи характеризации наследственного класса орграфов с
характеризацией его дополнения и обращения
2. Характеризация классов, взаимно однозначно соответствующих классам двудольных и расщепляемых графов
3. Характеризация классов с пустыми долями
3.1. Класс Еа1£
3.2. Класс £1г£
3.3. Класс £с11£
4. Характеризация классов с пустой и полной долями
® 4.1. Класс Еа1С
4.2. Класс £1гС
5. Характеризация классов с пустой долей и долей, вершины которой порождают транзитивный турнир
5.1. Класс ЕаёТ
5.2. Класс Еа1Т
5.3. Класс £с11Т
5.4. Класс £1гТ
6. Характеризация двух классов транзитивно-двудольных ор-ф графов. Полиномиальная разрешимость задачи распознавания в тринадцати классах
6.1. Класс ТасГГ
6.2. Сложность распознавания орграфов в двенадцати классах
6.3. Класс Та1Т
7. Класс Т1гТ
7.1. Специальные транзитивно-двудольные турниры и их свойства
7.2. ХР-полнота задачи распознавания орграфов из класса транзитивно-двудольных турниров
Выводы к главе II

§ III. ОБ ЭНТРОПИИ КОМПОЗИЦИЙ НАСЛЕДСТВЕННЫХ КЛАССОВ ЦВЕТНЫХ ГРАФОВ
Основные понятия и содержание главы III
1. Композиции наследственных классов цветных графов и проблема вычисления их энтропии
1.1. Понятие композиции наследственных классов цветных графов
1.2. Проблема вычисления энтропии композиций
2. Значения энтропии композиций наследственных классов
ф 2.1. Анализ задачи квадратичного программирования, полученной в §1
2.2. Вспомогательные задачи квадратичного программирования и соответствие между ними
2.3. Исследование задач (I), (II) и (III)
2.4. Регулярные и нерегулярные композиции наследственных классов цветных графов. Вычисление их энтропии
2.5. Основные замечания и следствия из теоремы об энтропии композиций
3. Важнейшие свойства регулярных композиций
^ 3.1. Взаимосвязь между порожденной и порождающей композициями
3.2. Наследование свойства регулярности и следствия из него
3.3. Существование нерегулярных порожденных композиций
у некоторых регулярных порождающих композиций
4. Нижняя и верхняя оценки энтропии регулярных композиций
5. О минимальных по включению композициях наследственных классов цветных графов
6. О минимальных по включению регулярных (к + ^-композициях, содержащих заданную регулярную fc-композицию
| 6.1. Критерий регулярности порождающей композиции и
следствия из него
Сначала докажем, что для любых двух вершин х £ У и у £ У2 выполняется условие (у, х) ф ТД(7).
Предположим, что для вершины V £ У2 найдется такая вершина ш £ V-!, что ш т-и, (го,о) € ^(С) и (г/,ш) € -Е'(С'). Тогда если между вершинами кип нет дуг, то (7({гг, п, ш}) = Р£ы. Если же между и и V есть в точности одна дуга, то С{{д,п, го}) = 0 о То. Противоречие. Следовательно, для любых вершин х € У и у £ У2 справедливо (х,у) ф Е(С?) или (:у,х) ф Е{в).
Предположим теперь, что для вершины V € У2 найдется такая вершина ю £ У, что (и, ю) £ Е(С).
Допустим, что го ф гг. Тогда по доказанному (го, г;) ф Т((?). Следовательно, если между вершинами гг и г» нет дуг, то (7{{гг, о, го}) = 0 ->• 0 о СД. Если же между гг и о есть в точности одна дуга, то в зависимости от ее ориентации получаем, что (7{{гг, гг, го}) = СД —У К^11’1 или (7{{гг, гг, го}) = РфА Противоречие. Значит, (г?, го) ф Е(С).
Пусть го = гг. Тогда если предположить, что (о, гг) € 77(17), то (гг, гг) ф 7?((7) и получаем, что подграф орграфа (7, порожденный вершинами гг, о и любой вершиной из У — {гг}, изоморфен орграфу 0 ->■ 0 о СД или орграфу Р3а1Г. Значит, (о, гг) ф ТДСД.
Полученные противоречия доказывают, что для любых двух вершин х £ У и у £ У2 справедливо (у,х)фЕ(0).
Докажем, что подграф, порожденный множеством является пустым. Пусть существуют такие вершины г?1 € У2 и г?2 С Фг, г?1 Ф 02, что (г>1, гг2) € Е(С) или (г^гд) £ Е(0). Если в У есть вершина х такая, что {х,о{) £ Е(С) или (я?, гг2) £ Ефй), то по доказанному (г>1,ж) ф £((?) и (гг2,ж) ф Е'(С'). Следовательно, подграф С?({ж,г?1, гг2}) изоморфен хотя бы одному орграфу из множест-ва {02 -4 О,, г^", О, -4 О, о Оь г», О, -4 Если (г,»,) Ц Е(в)
и (ж,гг2) ф Е(С) для любой вершины х £ УД то из того, что в У есть по крайней мере две вершины щ и гг2, следует, что (7{{ггь гг2, оио2}) = Т2 + К$ы или в({щ,и2, ои о2}) = 2К$ы. Противоречие. Значит, подграф Ф7(У2) пустой. Поэтому (7 € £а1С.
Случай 2. В С нет двустронних дуг, т.е. (УД = 1.
Тогда (7 € Егее(М{), где АЦ = {К$ы, 02 -+ СД, Т3сИг, Т*г, Т'1,2Т2}. Очевидно, что Э М4, поэтому по теореме 14 (7 € £а/£. Следовательно, множество вершин орграфа С можно разбить на такие под-