Минимальные циклы в заданных классах гомологий

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

1 Исследуемые объекты и используемые конструкции 17 § 1.1. Полиэдры. Симплициальные отображения и действия

групп. Триангулированные многообразия

§ 1.2. Группы гомологий

§ 1.3. Барицентрические звезды и индексы пересечения

§ 1.4. Способы задания полиэдров. Обозначения входных

данных

§ 1.5.Коллапсирование. Алгоритм

§ 1.6. Двумерные замкнутые многообразия. Канонический

и полуканонический базисы Н{Р)

2 Индексная вектор-функция и накрытия

§ 2.1.Индексация относительно заданного (п — 1)-мерного

цикла и вычисление индексов пересечения
§ 2.2.Индексная вектор-функция и ее свойства
§ 2.3.Накрытия в терминах симплициальных схем
§ 2.4.Построение регулярного накрытия с группой автоморфизмов (7 = Нг(Р)
§ 2.5.Свойства построенного накрытия

3 Минимальные пути и циклы
§ 3.1. Весовые функции. Примеры
§3.2. Поиск минимального пути с заданным индексом, соединяющего заданные вершины
§ 3.3. Минимизация пути с заданными концами и индексом
на многообразии
§ 3.4. Минимизация пути из заданной вершины до заданного множества
§ 3.5.Построение минимальных циклов
§ 3.6. Построение дуального базиса из минимальных циклов
4 Двумерный случай. Приложения
§ 4.1. Вычисление базисных 1-циклов 2-многобразия без
применения матриц инциденций
§ 4.2. Построение минимальных циклов, порождающих канонический базис
§ 4.3. Выделение ручек и устранение топологического шума
Заключение
Литература

В последние два десятилетия сформировалась и активно развивается вычислительная топология, в которой соединяются два различных, хотя и связанных друг с другом направления. Первое - это использование компьютерных методов при решении тех или иных проблем самой топологии, например, классификации компактных трехмерных многообразий ([19]—[23], [60]—[63]). Второе направление можно обозначить как приложения топологии к задачам, связанным с компьютерным моделированием и компьютерной графикой.
Настоящая работа в большей степени относится ко второму из указанных направлений.
Существует много работ, в которых предлагаются различные подходы к вычислению топологических характеристик и элементов полиэдров. Можно отметить классический алгоритм для вычисления групп гомологий и их базисов произвольного симплициального комплекса, основанный на приведении матриц инциденций к нормальной диагональной форме ([5], [32]). В работах [39], [51], [56] предлагались различные его модификации.
Для поверхностей известен ряд методов, основанных на использовании представления ее в виде канонического многоугольника. Так, в работах [65], [59] предложен алгоритм поиска базиса одномерной группы гомологий замкнутой поверхности. С помощью канонического представления решаются задача построения базиса фундаментальной группы поверхности из петель минимальной длины ([40]) и задача определения гомотопности двух заданных кривых ([45], [46], [47]).
В работах [41], [49] разработан алгоритм вычисления групп гомологий трехмерного симплициального комплекса, основанный на построении триангуляции Делоне. Другой метод решения аналогич-

группы накрывающих преобразований А(Р). В силу (В1) группа (7 действует транзитивно на любом слое р-1(г>), V & Р. Поэтому предположение о том, что (7 - собственная подгруппа группы А(Р), влечет за собой существование в А(Р) элементов, оставляющих некоторые точки слоя р~1{у) неподвижными. Последнее невозможно; следовательно, б? = А(Р).
Как уже отмечалось, группа (7 действует транзитивно на любом слое р-1(н), V £ Р, а значит, р : Р —>• Р - регулярное накрытие с группой накрывающих преобразований С. □
§2.4. Построение регулярного накрытия с группой автоморфизмов (7 =
ЩР)
Рассмотрим п-мерный полиэдр Р, натуральное число г и эпиморфизм 7 : С{Р) —У Тиг, ядро которого содержит группу границ В(Р).
В ситуации, когда Р - замкнутое многообразие, примером такого гомоморфизма является индексная вектор-функция относительно некоторого базиса группы Я„_1(Р).
Пусть 5 = (V, К) - симплициальная схема полиэдра Р. Построим схему § = (V, К) следующим образом.
Положим V = V х (7, где (7 = Щ. Пусть г)0, ... ,г>т £ V,
где уг = (ьг,дг) для всех г = 0,1 т. Будем считать, что {г>о, VI,, йт} £ К, если выполняются следующие условия:
(Ш) {г0,щ г;т} £ К
(112) до+дг = J([vovг}) для любых г — I,... ,т, где 7([до^*]) _ индекс ребра [у0уг].