Эффективные алгоритмы на кодированных графах и их применение

Эффективные алгоритмы на кодированных графах и их применение

Автор: Дудов, Мурат Хусеевич

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

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

Год защиты: 1999

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

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

Артикул: 263904

Автор: Дудов, Мурат Хусеевич

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

Оглавление. Введение. Вычислительная сложность. Алгоритмы поиска. Алгоритмы поиска на кодированных графах. Кодирование графов. Операции на кодированных графах. Алгоритм поиска в глубину. Алгоритм поиска в ширину. Эффективные алгоритмы на кодированных графах. Алгоритм выделения связных компонент графа. Алгоритм выделения двусвязных компонент. Алгоритм построения кратчайшей цепи. Заключение. Приложение. Описание и постановка задач. Организация вычислительного эксперимента. ЛЛ оригм поиска оптимальной топологии электросети. Ьиблиофафический список. В 1 показано, что алгоритм построения дерева методом поиска в ширину может быть применен для построения кратчайшей цепи Ц0,4 между двумя заданными вершинами рафа 0 и V,. В главе 2 доказано теорема 8 что вычислительная сложность алгоритма поиска в ширину а 2 на кодированном рафе равна Оп, трудоемкость построения цепи рассматриваемым в разделе 3. Оп. В разделе 3. ВС известных классических алгоритмов при представлении графа матрицей смежности например, ВС алгоритма ХопкрофтаКарпа равна оп .


В главе 2 доказано теорема 8 что вычислительная сложность алгоритма поиска в ширину а 2 на кодированном рафе равна Оп, трудоемкость построения цепи рассматриваемым в разделе 3. Оп. В разделе 3. ВС известных классических алгоритмов при представлении графа матрицей смежности например, ВС алгоритма ХопкрофтаКарпа равна оп . В разделе 3. В известном алгоритме Эдмондса процедура построения увеличивающей цени организована как построение чередующегося но текущему паросочетанию дерева методом поиска в ширину из некоторых верппш уже построенного фрагмента дерева. При таком подходе одним из основных понятий, введнных Эдмондсом, становится цветок чередующийся по П цикл нечтной длины. Алгоритм Эдмондса решает проблему цветков на графе с помощью специальной процедуры их сворачивания. Сворачивание и восстановление цветков на графах, иродставленых матрицей или списками смежности, обуславливают повышение вычислзпслыюй сложности алгоритма построения максималь
ною паросочетания до 0п. Габов 1 устранил операции сворачивания и восстановления, записывая структуры цветков с помощью определенной процедуры расстановки меток и формирования специальных массивов, что позволило достичь сложности оп . Алгоритмы построения максимального паросочетания в работах 1 во многом аналогичны методу Габова и обладают в худшем случае не меньшей вычислительной сложностью. Предлагаемые в данной работе форма представления графа кодированная и алгоритмы поиска а, на, на кодированных графах позволили разработать алгоритм а7 построения максимального паросочетания, основанный на методе Эдмондса и обладающий вычислительной сложностью Сп2.

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

28.06.2016

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

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

15.02.2015

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

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


Все новости

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