Математические модели и методы для векторной задачи о кликах

Математические модели и методы для векторной задачи о кликах

Автор: Тамбиева, Джаннет Алиевна

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

Научная степень: Кандидатская

Год защиты: 1999

Место защиты: Черкесск

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

Артикул: 259312

Автор: Тамбиева, Джаннет Алиевна

Стоимость: 250 руб.

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


В контексте рассмотренных выше оптимизационных постановок предлагаемый ниже алгоритм а2 представляет собой метод гарантированного нахождения какоголибо допустимого решения хе X задачи о 4кликах. У. Далее следует переход к определению множества дуг т. О согласно следующего правила орграф Н содержит дугу 1 асо тогда и только тогда, когда соответствующие ей гипервершины а у,У2,Уз,У4 И 0 М. Уз,Уд не содержат общих элементов, те. У2Уз4 ПуГ. Уз. Ориентация дуги определяется лексикографическим упорядочением гипервершин И Ощ, т. Из этого условия вытекает, что орграф Н является многодольным, т. ПРИМЕЧАНИЕ 3. Для орграфа Я И,0 с множеством гипервершин У сохраняем все термины и понятия, которые имеют место в теории графов для обыкновенных орграфов и графов. Ориентированные цикл и цепь называем соответственно контур и путь. Согласно своего определения граф не содержит контуров Термином ориентированная клика или орклика будем называть всякий полный подграф орграфа Н. Т.е. Я0 УУ0,О0 есть орклика орграфа Н ,Ч0с1Г,О0 О. Ф0 соединена дугой , Л оо или 4 а, о. Следуя общепринятому, число гипервершин УУ0 называем размерностью орклики Н0. Термином максимальная орклика называем орклику максимально возможной размерности. Максимальную орклику обозначаем через х УХ,Ох, IVх С И, А,сО К Кнх множество всех максимальных орклик в Н. Е, т. ПРИМЕЧАНИЕ 3. С учетом описанного выше лексикографического принципа определения дуг с1еП в главе 3 сформированы основные свойства орграфа И, позволяющие на начальном этапе решения исследуемой задачи отсеивать неперспективные клики и тем самым максимально облегчить поиск допустимого решения для задачи о 4кликах.

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

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.240, запросов: 244