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

• Автор: Дудов, Мурат Хусеевич
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Черкесск
• Количество страниц: 134 с. : ил.

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


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