+
Действующая цена700 499 руб.
Товаров:
На сумму:

Электронная библиотека диссертаций

Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО

Расширенный поиск

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

  • Автор:

    Сорочан, Сергей Владимирович

  • Шифр специальности:

    01.01.09

  • Научная степень:

    Кандидатская

  • Год защиты:

    2006

  • Место защиты:

    Нижний Новгород

  • Количество страниц:

    149 с. : ил.

  • Стоимость:

    700 р.

    499 руб.

до окончания действия скидки
00
00
00
00
+
Наш сайт выгодно отличается тем что при покупке, кроме PDF версии Вы в подарок получаете работу преобразованную в WORD - документ и это предоставляет качественно другие возможности при работе с документом
Страницы оглавления работы

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
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 € £а/£. Следовательно, множество вершин орграфа С можно разбить на такие под-

Рекомендуемые диссертации данного раздела

Название работыАвторДата защиты
Оптимальное управление отдельными классами гиперболических систем первого порядка Поплевко, Василиса Павловна 2010
Полиномиальные операторные представления конечнозначных функций Зинченко, Анна Сергеевна 2006
Оптимизация численных алгоритмов Михеев, Сергей Евгеньевич 2006
Время генерации: 2.123, запросов: 967