Минимальные циклы в заданных классах гомологий тема диссертации и автореферата по ВАК РФ 01.01.04, кандидат физико-математических наук Лаптева, Анастасия Владимировна

• Лаптева, Анастасия Владимировна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Лаптева, Анастасия Владимировна

Введение

1 Исследуемые объекты и используемые конструкции

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

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

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

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

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

§ 1.6.Двумерные замкнутые многообразия. Канонический и полуканонический базисы Ях (Р).

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

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

§ 2.2.Индексная вектор-функция и ее свойства

§ 2.3.Накрытия в терминах симплициальных схем

§ 2.4.Построение регулярного накрытия с группой автоморфизмов G = Hi(P).

§ 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] разработан алгоритм вычисления групп гомологий трехмерного симплициального комплекса, основанный на построении триангуляции Делоне. Другой метод решения аналогичной задачи предложен в серии работ [42], [43], [44].

Нематричным методам поиска циклов, порождающих базисы групп гомологий для двумерных многообразий, посвящены работы [6], [34], [35], [52].

В работе [53] с помощью процедуры, аналогичной коллапсиро-ванию, построен алгоритм нахождения графа разрезания, однако авторы не ставят задачу построения базисных циклов, а лишь находят граф, их содержащий.

Большая серия работ связана с применениями в вычислительных алгоритмах дискретного аналога теории Морса ([37], [38], [48], [50], [64], [66]). В частности, на основе подобных методов в [54], [67] предлагается один из способов устранения топологического шума, то есть топологических дефектов компьютерных моделей.

Диссертационная работа посвящена разработке методов вычисления минимальных циклов (абсолютных и относительных) в заданных классах одномерных гомологий триангулированных замкнутых многообразий, а также их применениям.

В частности, здесь получен отличный от [54], [67] способ локализации и устранения топологического шума в компьютерных моделях.

Построенная в диссертации индексная вектор-функция позволяет решать подобную [45], [46] задачу о гомологичности двух заданных одномерных цепей для любого n-мерного замкнутого многообразия.

Отметим, что в [36] приведен алгоритм индексации и основанный на нем метод поиска минимальных циклов в заданном классе абсолютных гомологий [х] € Н\{Р) ориентируемого замкнутого 2-многообразия Р. Но указанный алгоритм существенно использует двумерность многообразия Р и двусторонность простых одномерных циклов в Р и потому в общей ситуации неприменим.

Целью работы является разработка методов решения следующих задач:

1) индексация ребер триангулированного замкнутого п-мерного многообразия Р относительно заданного (п — 1)-мерного цикла г 6

Z„i(P); Л

2) построение симплициального регулярного накрытия р : Pj ->• Р с группой накрывающих преобразований G = Н\{Р)\

3) поиск цепей с Е С\{Р)) минимизирующих весовую функцию L : С\(Р) —> К на заданном подмножестве группы Ci(P);

Методы исследования. Использованы методы алгебраической и кусочно-линейной топологии, теории графов.

Научная новизна.

Все результаты работы, выносимые на защиту, являются новыми и получены автором самостоятельно.

1. Предложен способ индексации одномерных симплексов триангулированного замкнутого многообразия Р относительно заданного цикла г € Zn-\(P). С его помощью строится гомоморфизм Jz : С\(Р) Z2, позволяющий вычислить индекс пересечения z с любым одномерным циклом полиэдра Р, а также индексная вектор-функция J : С\(Р) -У 1Т2 относительно базиса [г"-1],., [zгруппы гомологий Hn-i(P).

2. Построена симплициальная схема полиэдра Pj, симплициаль-но и регулярно накрывающего многообразие Р с группой накрывающих преобразований G = Н\{Р).

3. Разработаны методы минимизации весовой функции L : Ci(P) 1 на следующих подмножествах группы С\(Р) замкнутого многообразия Р:

• на множестве путей, соединяющих фиксированные вершины и имеющих заданный индекс;

• на множестве одномерных цепей, соединяющих вершину и многообразия Р с некоторым подполиэдром Q С Р и образующих класс относительных гомологий [х] Е Н\(Р, {и} U Q);

• на произвольном ненулевом гомологическом классе [ж] G Нг(Р).

4. Указан способ построения минимальных циклов, порождающих базис группы #i(P), дуальный заданному базису группы Нп-г(Р).

5. Найдены приложения полученных результатов, в частности, предложен способ выделения ручек и устранения топологического шума в компьютерных моделях поверхностей трехмерных тел.

Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Ее результаты могут быть использованы для вычисления топологических характеристик и элементов полиэдров, для изучения и обработки компьютерных моделей реальных объектов, а также при чтении спецкурсов.

Апробация. Описанные результаты работы были обнародованы на международной научной конференции "Актуальные проблемы математики и механики"(Казань, 26 сентября - 1 октября 2004 г.); на всероссийских молодежных научных школах-конференциях "Лобачевские чтения" (Казань, 2005г., 2006г.); на международных летних школах-семинарах по современным проблемам теоретической и математической физики "Петровские чтения" (Казань, 2005г., 2006г.); на III международной конференции по прикладной математике (Пловдив, Болгария, 12-18 августа 2006 г.); на региональной научной конференции "Современные вопросы геометрии и механики деформируемого твердого тела" (Чебоксары, 19-20 октября 2006г.); на научных семинарах по геометрии и топологии кафедры геометрии и высшей алгебры ННГУ (рук. доц. Н.И. Жукова и проф. Е.И. Яковлев, 2005г., 2006г.); на научном семинаре кафедры компьютерной топологии и алгебры Челябинского госуниверситета (рук. член-корр. РАН С.В. Матвеев, 2006г.).

Публикации и вклад автора. Результаты диссертации опубликованы в работах [8]-[16], [57], [58]. Отдельно этот список приведен в конце заключения. В совместных статьях [8], [9],[57],[58] научному руководителю Е.И. Яковлеву принадлежат постановка задачи и общее руководство работой. Все теоремы и их доказательства получены автором диссертации.

Краткое содержание работы.

Во введении обосновываются актуальность темы диссертации и ее научная новизна, определяются цели и задачи исследования, приводится краткое содержание диссертации.

Заключение диссертации по теме «Геометрия и топология», Лаптева, Анастасия Владимировна

Выход: циклы z{,., z\.

Описание алгоритма.

Шаг 1. Построение индексной функции. С помощью алгоритма 2.1 вычислим индексную вектор-функцию J : С\(Р) —У Щ, относительно базиса [а^],.,

Шаг 2. Построение полуканонического базиса [zj],. ., [z}}. Шаг 2.1. Положим q := 1.

Шаг 2.2. Если q = г — 1, то положим zq := xlq, := xlq+l и перейдем к шагу 3.

Шаг 2.3. Положим z* := xlq и р := q + 1.

Шаг 2.4. Если Ind(a;p, xlq) = Jq{Xp) = 1, то перейдем к шагу 2.6.

Шаг 2.5. Присвоим переменной р значение р+1 и повторим шаг

2.4.

Шаг 2.6. Вычислим определитель матрицы Bq, составленной из индексов пересечения Ind^1, ж]) = J3(x\), i,j G {q + 1,., г} \ {p}. Если detSg = 0, то вернемся к шагу 2.5. Иначе положим zq+1 := xlp.

Шаг 2.7. При р > q+1 положим xlp := xq+1, q := q+2 и вернемся к шагу 2 2.

Шаг 2.8. Переставим компоненты Jk, к = 1,.,г индексной вектор-функции J = (J1,., Jr) в соответствии с новым порядком циклов в базисе.

Шаг 3. Построение канонического базиса. Для всех к = 1,., г выполним шаги 3.1 - 3.5.

Шаг 3.1. Положим М = L(zl).

Шаг 3.2. Из последовательности S = {1,.,г} удалим элемент А;, а из оставшихся элементов получим подпоследовательность 5* = {«ij • • •, V-1} С S. Построим гомоморфизм Л : С\(Р) Z^-1, полагая = Jlq для всех q = 1,., г — 1.

Шаг 3.3. При четном к положим к* = к — 1, z* = z\v в противном случае положим к* — к, z* = 4+1 • Построим индекс I £ И2 1 по следующему правилу: Ik* := 1, Р := 0 для j £ {1,., г - 1} \ {А;*}.

Шаг 3.4. Для каждой вершины v £ У выполним цикл 3.4.1 - 3.4.3.

Шаг 3.4.1. С помощью алгоритма Дейкстры составим список К вершин и £ V(P), удовлетворяющих неравенству cIl(v, и) < М/2 (см. (3.3)). Из симплексов, все вершины которых лежат в К, построим подполиэдр Р* С Р.

Шаг 3.4.2. Применяя алгоритм 3.1, либо построим цикл zv £ Zi(P#) с формальным индексом J*(zv) = I, проходящий через вершину v и имеющий наименьший вес L(zv) < М среди всех циклов, обладающих аналогичными свойствами, либо придем к выводу о его несуществовании.

Шаг 3.4.3. Если цикл zv будет найден, то положим z\ = zv и М = L(zv).

Шаг 3.5. С помощью алгоритма 2.1 пересчитаем к-ую компоненту вектор-функции J.

Конец алгоритма.

Теорема 4.2. Алгоритм 4-2 корректен. Гомологические классы циклов z\,., z\, полученных с помощью алгоритма 4-2, образуют канонический базис группы гомологий Н\(Р), а вес каждого цикла z\, к = 1,., г, минимален среди всех циклов, ему гомологичных.

Доказательство. Предположим, что либо q = 1, либо 1 < q = 2n + 1 < г и с помощью шага 2 алгоритма 4.2 из набора {х\,., жг} выбраны такие циклы z\,.,z\n, что Ind(z2Z1,z^) — 1 для всех I = 1 ,.,п. Рассмотрим матрицу Bq, составленную из индексов пересечения Ъ13 = Ш(х1п+г,xln+J), i,j € {l,.,r - 2п}, циклов ж*,., zj, не вошедших в набор {zj,., zln}. При этом, в силу невырожденности формы Ind на Hi(P) и согласно шагу 2.6, det Bq = 1.

Заметим, что матрица Bq является кососимметрической. Поэтому г—9+1 \ 2 detBi= (^Е , (4-2) где Uij - алгебраическое дополнение минора 2-го порядка, расположенного на пересечении столбцов и строк матрицы Bq с номерами 1 и j ([24], глава 1, §12). Из условия det Bq ф 0 следует, что, по крайней мере, одно из слагаемых в разложении (4.2) отлично от нуля. Пусть р' - номер этого слагаемого и р = q + p'. Тогда Ind(a^, х*) = 1 и det Bq+2 ф 0, где матрица Bq+2 получена из матрицы Bq вычеркиванием столбцов и строк с номерами 1 и р' = р — q.

Таким образом, построение полу канонического базиса корректно. Отметим важное обстоятельство. Для всех q = 1,3, .,г — 1 матрица Aq, составленная из индексов пересечения циклов zq,.,zl после завершения шага 2, получается из Bq перестановкой строк и столбцов. Поэтому det Aq = det Bq = 1.

Пусть с помощью шага 3 алгоритма 4.2 преобразованы первые к циклов z\,., z\, к Е {1,., г}. Покажем, что после этого гомологические классы циклов z\,.,z\ останутся линейно независимыми.

Согласно 3.1 - 3.5, после преобразования циклов z\,.,zl матрица Aq индексов пересечения всех циклов приводится к виду где I = maх{к,к*}, q = I -f 1, а звездочкой обозначены элементы матрицы Aq. При четном к имеют место равенства к = I и = аг1 = 0 для всех = q,., г.

Очевидно, det Лд = det Akq2- Пользуясь разложением вида (4.2), отсюда и из (4.3) получим равенство det Aq = det А* = det Поскольку det^9 = 1, то этим линейная независимость гомологических классов [z{],., [z*] доказана.

Таким образом, в случае к < г после шага 3.5 мы снова получим корректно определенную индексную вектор-функцию J и можем повторить цикл 3.1-3.5 для следующего значения параметра к.

В ситуации, когда к = г, матрица Aq имеет канонический вид. Следовательно, после завершения работы алгоритма 4.2 гомологические классы циклов z\,. образуют канонический базис группы #х(Р).

Пусть далее к £ {1,., г}, у Е ZX(P) и [у] = [z\], где z\ - цикл, полученный после завершения работы алгоритма. Рассмотрим индексную вектор-функцию J относительно базиса группы Е\ (Р), построенного перед шагом 3.1 для выбранного к. Тогда J(y) = J{z\), а значит, и J*(y) = J*{z\) = I

То, что цикл z\ имеет минимальный вес среди циклов z Е Z\(P)

О 1 . О 0 0 . О ^ 1 0 . О 0 0 . О

О 0 . О 1 0 . О

О 0 . 1 0 Щд . щг О 0 . О aqi * . *

4.3) / с формальным индексом «Д {z) — /, следует из построения на шаге 3.4 (см. теорему 3.4). Сокращая на шаге 3.2 индексную вектор-функцию J : С\{Р) —> Ъ\ до гомоморфизма Л : С\(Р) —> Z^-1, мы находим минимальный цикл в объединении двух гомологических классов. Тогда тем более найденный цикл минимален в своем классе гомологий.

Замечание 4.2. Построение канонического базиса группы гомологий Hi (Р) двумерного замкнутого ориентируемого многообразия Р - более сильный результат, чем нахооюденис базиса группы Н\(Р), дуального заданному базису группы #ni(P) (алгоритм 3.5), поскольку канонический базис дуален самому себе.

Рис. 4.2: Слева - 4 базисных цикла одномерной группы гомологий кренделя, выделенные разными цветами, справа - минимальные циклы, порождающие канонический базис одномерной группы гомологий.

4.3. Выделение ручек и устранение топологического шума

Пусть Р - триангулированное замкнутое и ориентируемое 2-многообразие рода т и Т{Р) - список его треугольников. Выделением ручки мы называем составление такого списка T(R) С Т(Р), что объединение R всех его элементов гомеоморфно ограниченному цилиндру, а объединение симплексов из дополнения Т(Р) \ T(R) представляет собой поверхность Р' рода га — 1с двумя компонентами края.

Предлагаемая схема выделения всех ручек поверхности Р состоит в следующем:

1. С помощью алгоритма 4.1 найдем циклы ., yr, г = 2га = rank Hi (Р), гомологические классы которых образуют базис группы

UP)

2. Воспользуемся алгоритмом 2.1 и вычислим индексную вектор-функцию Jo : Ci(P) —> относительно базиса [yi],., [уг] группы

UP)

3. Применяя алгоритм 4.2, построим циклы zi,. ,zr, каждый из которых имеет минимальный вес в своем классе гомологий, а эти классы образуют канонический базис группы Hi(P) При этом, согласно шагу 3.6, мы получим также индексную вектор-функцию J : Ci(P) 1Т2 относительно базиса [z\],., [zr].

4. Для каждой пары циклов Z2k-i и Z2k, к = 1,., га, выполним следующие шаги:

4.1. Выберем основной цикл х G {z2k—1) %2к} и дополнительный цикл у £ {z2jfc-i, *2к}, У ф X (например, по длине).

4.2. Для каждой вершины уг, i = 1,., щ, основного цикла х в одномерном остове накрывающего полиэдра Pj найдем кратчайший путь уг, идущий из вершины (vt, 0) в вершину (г;,, J(y)), и положим

Уг=Р{Уг)

4.3. Начиная с треугольника, инцидентного ребру [vtvt+i] (г + 1 вычисляется по модулю пк), построим список Тг треугольников, расположенных между циклами уг и уг+1. Для объединения 11г симплексов из Тг вычислим группу

4.4. Построим максимальное по включению сильно связное объединение Rk областей Ut, для которых rankHi(Ut) ^ 1.

Выделение ручек используется, например, для локализации и устранения топологического шума в компьютерных моделях реальных объектов.

В ряде случаев компьютерные модели содержат топологические элементы (компоненты края, ручки, ребра ветвления, особые вершины), которых нет у исходных объектов. Совокупность этих лишних элементов, являющихся дефектами моделирования, принято называть топологическим шумом.

При устранении топологического шума наиболее сложной и интересной является задача локализации и удаления лишних ручек. Если выделенная ручка Rk является дефектом компьютерного моделирования, то исправление модели осуществляется удалением соответствующего ручке списка треугольников Tk(Rk) из общего списка Т(Р) и заклеиванием получающихся двух дыр.

Но ручка поверхности Р определена неоднозначно и ее можно менять. Для того, чтобы поверхность, полученная после ее удаления, оказалась более гладкой, область Rk целесообразно расширить.

Пусть yi,yi+1,. ,yi> - циклы, вошедшие в ручку Rk, 1 ^ I < V ^ пк, и п - целая часть числа (I' — /)/2. Обозначим символом S(Rk) список {п + 1, п - 1, п + 2, п — 2,., /} при нечетном I' — I и список {п + 1, п — 1, п + 2, п — 2,., /, /'} при четном I' — I. Для каждого j из S(Rk) с помощью шага 3.2 построим проходящий через вершину Vj цикл у' не имеющий общих ребер с уп и с циклами у',, построенными до у'у Символом R'k обозначим объединение треугольников, расположенных между циклами у[ и y'v, содержащее ручку Rk.

Удаление области R'k приводит к более качественному результату, чем при разрезании поверхности по одному приближенно кратчайшему нестягиваемому циклу на данной ручке или по двум близким к нему циклам ([65]).

По списку Tk(Rk) мы можем вычислить площадь и диаметр ручки Rk. После этого становится возможным определить отношение ее размеров к соответствующим размерам всей поверхности Р, что в ряде случаев позволяет оценить правильность отнесения данной ручки к топологическому шуму.

Рис. 4.3: Модель "Счастливый Будда". Пример ручки, являющейся дефектом моделирования.

Для проверки алгоритмов удобно использовать модели полученные в лаборатории компьютерной графики Стэнфордского университета с помощью 3D сканера, например, модель "Счастливый Будда". Указанная модель содержит 543652 вершины, 1087716 треугольников, 104 ручки, из которых только 5 - настояттще.

Рис. 4.4: Выделение и удаление лишней ручки.

Заключение

Основными результатами диссертации, выносящимися на защиту являются следующие:

1. Предложен способ индексации одномерных симплексов триангулированного замкнутого многообразия Р относительно заданного цикла z Е Zn-i(P). С его помощью строится гомоморфизм Jz : Ci(P) —У Z2, позволяющий вычислить индекс пересечения z с любым одномерным циклом полиэдра Р, а также индексная вектор-функция J : С\{Р) Z£ относительно базиса [z"-1],., [z"-1] группы гомологий Нп-\(Р).

2. Построена симплициальная схема полиэдра Р/, симплициаль-но и регулярно накрывающего многообразие Р с группой накрывающих преобразований G = Н\ (Р).

3. Разработаны методы минимизации весовой функции L : С\{Р) -> R на следующих подмножествах группы С\{Р) замкнутого многообразия Р:

• на множестве путей, соединяющих фиксированные вершины и имеющих заданный индекс;

• на множестве одномерных цепей, соединяющих вершину и многообразия Р с некоторым подполиэдром Q С Р и образующих класс относительных гомологий [ж] Е #i(P, {u} U Q);

• на произвольном ненулевом гомологическом классе [ж] Е Я,(Р).

4. Указан способ построения минимальных циклов, порождающих базис группы #i(P), дуальный заданному базису группы

Hn-i(P).

5. Найдены приложения полученных результатов, в частности, предложен способ выделения ручек и устранения топологического шума в компьютерных моделях поверхностей трехмерных тел.

Результаты диссертационной работы опубликованы в работах автора:

1. Лаптева, А. В. Методы поиска кратчайших 1-циклов в заданном классе гомологий / А. В. Лаптева, Е. И. Яковлев // Труды матем. центра им. Н.И. Лобачевского. - 2004. - Т. 25. - С. 159-160.

2. Лаптева, А. В. Алгоритмы для поиска минимальных одномерных циклов / А. В. Лаптева, Е. И. Яковлев // Вестник ННГУ. Серия Математика. - 2005. - Вып. 1(3). - С. 76-87.

3. Лаптева, А. В. Поиск минимального пути в заданном классе относительных гомологий / А. В. Лаптева // Труды матем. центра им. Н.И. Лобачевского. - 2005. - Т. 31. - С. 88-89.

4. Лаптева, А. В Метод устранения топологического шума в компьютерных моделях ЗБ-объектов / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. - 2006. - С. 47.

5. Лаптева, А. В. Индексная вектор-функция / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. - 2006. - С. 48-52.

6. Lapteva, А. V. Index Vector-Function and Minimal Cycles / A. V. Lapteva, E. I. Yakovlev // Lobachevskii Journal of Mathematics. -2006. - Vol. 22. - P. 35-46.

7. Лаптева, А. В. Алгоритм поиска минимальной одномерной цепи в заданном классе относительных гомологий / А. В. Лаптева // Вестник ННГУ. Серия Математика. - 2006. - Вып. 1(4). - С. 59-64.

8. Лаптева, А. В. Поиск минимальных одномерных циклов триангулированного многообразия / А. В. Лаптева // Современные вопросы геометрии и механики деформируемого твердого тела. Тезисы региональной научной конференции. - Чебоксары, 2006. - С. 25-26.

9. Lapteva, А. V. Minimal 1-Cycles Generating a Canonical Basis of 2-Manifold's Homology Group / A. V. Lapteva, E. I. Yakovlev // International Journal of Pure and Applied Mathematics. - 2006. - Vol. 31, No 4. - P. 555-570.

10. Лаптева, А. В. Построение дуального базиса из минимальных циклов / А. В. Лаптева // Труды матем. центра им. Н.И. Лобачевского. - 2006. - Т. 34. - С. 151-152.

11. Лаптева, А. В. Поиск минимальных относительных циклов на многообразиях с краем / А. В. Лаптева // Чебоксары: Чуваш-госпединститут. Вестник. - 2006. - N 5. - С. 96-100.

Список литературы диссертационного исследования кандидат физико-математических наук Лаптева, Анастасия Владимировна, 2006 год

1. Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман. - М-СПб.- Киев: Изд. дом "Вильяме", 2001.

2. Бредон, Г. Введение в теорию компактных групп преобразований / Г. Бредон. М.: Наука, 1980.

3. Дольд, А. Лекции по алгебраической топологии / А. Дольд. -М.: Мир, 1976.

4. Дубровин, Б. А. Современная геометрия. Методы теории гомологий / Б. А. Дубровин, С. П. Новиков, А. Т. Фоменко. М.: Наука, 1984.

5. Зейферт, Г. Топология / Г. Зейферт, В. Трельфалль. M.-JI.: ГОНТИ, 1938; Ижевск: НИЦ РХД, 2001.

6. Зинченко, В. Ю. Новый метод построения базисных циклов групп гомологий полиэдров / В. Ю. Зинченко // Труды Математического центра имени Н.И. Лобачевского. 2003. - Т. 21. - С. 118-120.

7. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. М.: МЦНМО, 2001.

8. Лаптева, А. В. Методы поиска кратчайших 1-циклов в заданном классе гомологий / А. В. Лаптева, Е. И. Яковлев // Труды матем. центра им. Н.И. Лобачевского. 2004. - Т. 25. - С. 159— 160.

9. Лаптева, А. В. Алгоритмы для поиска минимальных одномерных циклов / А. В. Лаптева, Е. И. Яковлев // Вестник ННГУ. Серия Математика. 2005. - Вып. 1(3). - С. 76-87.

10. Лаптева, А. В. Поиск минимального пути в заданном классе относительных гомологий / А. В. Лаптева // Труды матем. центра им. Н.И. Лобачевского 2005. - Т. 31. - С. 88-89.

11. Лаптева, А. В. Метод устранения топологического шума в компьютерных моделях ЗБ-объектов / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. -2006. С. 47.

12. Лаптева, А. В. Индексная вектор-функция / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. 2006. - С. 48-52

13. Лаптева, А. В. Алгоритм поиска минимальной одномерной цепи в заданном классе относительных гомологий / А. В. Лаптева // Вестник ННГУ. Серия Математика. 2006. - Вып. 1(4). - С. 59-64.

14. Лаптева, А. В. Поиск минимальных одномерных циклов триангулированного многообразия / А. В. Лаптева // Современные вопросы геометрии и механики деформируемого твердого тела Тезисы региональной научной конференции. Чебоксары, 2006. - С. 25-26.

15. Лаптева, А. В. Построение дуального базиса из минимальных циклов / А. В. Лаптева // Труды матем. центра им. Н.И. Лобачевского. 2006. - Т. 34. - С. 151-152.

16. Лаптева, А. В. Поиск минимальных относительных циклов на многообразиях с краем / А. В. Лаптева // Чебоксары: Чуваш-госпединститут. Вестник. 2006. - N 5. - С. 96-100.

17. Липский, В. Комбинаторика для программистов / В. Липский. М.: Мир, 1988.

18. Масси, У. Алгебраическая топология. Введение / У. Масси, Д. Столлингс. М.: Мир, 1977.

19. Матвеев С. В., Алгоритм распознавания трехмерной сферы (по А. Томпсон) / С. В. Матвеев // Математический сборник. -1995. Т. 186. N 5. - С. 69-84.

20. Матвеев, С. В. Алгоритмическая классификация 3-многообразий. Проблемы и результаты / С В. Матвеев // Труды Математического института имени В.А. Стеклова. -1999. Т. 225. - С. 264-275.

21. Матвеев, С. В. Алгоритмические и компьютерные методы в трехмерной топологии / С. В. Матвеев, А. Т. Фоменко. М.: Изд-во МГУ, 1991, 1998.

22. Матвеев, С. В. Компьютерная классификация расширенных диаграмм Хегора / С. В. Матвеев, В. В. Таркаев // Вестник Челябинского университета. Серия 3. Математика, механика, информатика. 2003. - N 2. - С. 146-152.

23. Матвеев, С. В. Табулирование трехмерных многообразий / С. В. Матвеев // Успехи математических наук. 2005. - Т. 60. N 4. - С. 97-122.

24. Окунев, JI. Я. Высшая алгебра / JI. Я. Окунев. М.: ОНТИ НКТП СССР, 1937.

25. Рохлин, В. А. Начальный курс топологии. Геометрические главы / В. А. Рохлин, Д. Б. Фукс. М.: Наука, 1977.

26. Рурк, К. Введение в кусочно линейную топологию / К. Рурк, Б. Сандерсон. М.: Мир, 1974.

27. Свитцер, Р. М. Алгебраическая топология гомотопии и гомологии / Р. М. Свитцер. - М.: Наука, 1985.

28. Спеньер, Э. Алгебраическая топология / Э. Спеньер. М.: Мир, 1971.

29. Стинрод, Н. Топология косых произведений / Н. Стинрод. М.: ИЛ, 1953.

30. Стинрод, Н. Основания алгебраической топологии / Н Стинрод, С. Эйленберг. М.: ИЛ, 1956.

31. Фоменко, А. Т. Наглядная геометрия и топология. Математические образы в реальном мире / А. Т. Фоменко. М.: Изд-во МГУ, 1992.

32. Фоменко, А. Т. Курс гомотопической топологии / А. Т. Фоменко, Д. Б. Фукс. М.: Наука, 1989.

33. Цишанг, X. Поверхности и разрывные группы / X. Цишанг, Э. Фогт, X. Д. Колдевай. М.: Наука, 1988.

34. Яковлев, Е. И. Быстрые алгоритмы вычисления групп гомологий и их базисов / Е. И. Яковлев, П. А. Гордиенко // Материалы VII Международного семинара "Дискретная математика и ее приложения". 2001. - С. 284 - 287.

35. Яковлев, Е. И. Алгоритмы для вычисления базисных циклов одномерной группы относительных гомологий / Е. И. Яковлев, О. В. Логинов // Вестник ННГУ. Серия Математика. 2003. -Вып. 1. - С. 132 - 142.

36. Яковлев, Е. И. Вычислительная топология / Е. И. Яковлев. -Нижний Новгород: Изд-во ННГУ, 2005.

37. Axen, U. Computing Morse functions on triangulated manifolds / U. Axen // Proceedings of the SIAM Symposium on Discrete Algorithms (SODA). 1999. - P. 850-851.

38. Axen, U. Auditory morse analysis of triangulated manifolds / U. Axen, H. Edelsbrunner // Mathematical Visualization. Berlin, 1998. - P. 223-236.

39. Chao, J. Cubical singular simplex model for 3D objects and fast computation of homology groups / J. Chao, J. Nakayama // Proc. IEEE. 1996. - P. 190-194.

40. Colin de Verdiere, E. Optimal System of Loops on an Orientable Surface / E. Colin de Verdiere, F. Lazarus // Proceedings of the 43rd Annual IEEE Symposium of Foundations of Computer Science. 2002. - P. 627-636.

41. Delfinado, C. An incremental algorithm for betti numbers of sim-plicial complexes on the 3-sphere / C. Delfinado, H. Edelsbrunner // Comput. Aided Geom. Design. 1995. - Vol. 12. - P. 771-784.

42. Dey, Т. К. Computational topology / Т. К. Dey, Н. Edelsbrunner, S. Guha // Advances m Discrete and Computational Geometry. -Providence, 1998. P. 109-143.

43. Dey, Т. K. Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space / Т. K. Dey, S. Guha // Proc. 28th ACM Sym-pog. Theory Comput. 1996. - P. 398-407.

44. Dey, Т. K. Computing Homology Groups of Simplicial Complexes in R3 / Т. K. Dey, S. Guha // Proceedings ot 28th Symposium of Theory of Computing. 1996. - P. 397-407.

45. Dey, Т. K. Optimal algorithms for curves on surfaces / Т. K. Dey, S. Guha // Proc. 35th IEEE Ann. Sympos. Found. Comput. Sci. -1995. P. 266-274.

46. Dey, Т. К Transforming Curves on Surfaces / Т. K. Dey, S. Guha // J. Comput. Sys. Sci. 1999. Vol. 58. - P. 297-325.

47. Dey, Т. K. A New Technique To Compute Polygonal Schema for 2-Manifolds with Application to Null-Homotopy Detection / Т. K. Dey, H. Schipper // Disc. & Сотр. Geom. 1995. - Vol 14. - P. 93-110.

48. Edelsbrunner, H. Morse-Smale Complexes for Piecewise Linear 3-Manifolds / H. Edelsbrunner, J. Harer, V. Natarajan, V. Pascucci // Proceedings of the 19th Annual ACM Symposium of Computer Geometry. New York, 2003. P. 98-101.

49. Edelsbrunner, H. Topological Persistence and Simplification / H. Edelsbrunner, D. Letscher, A. Zomorodian // Disc. Comput. Geom. 28. 2002. - P 511-533.

50. Forman, R. A discrete morse theory for cell complexes / R. Forman // Geometry, Topology and Physics for Raoul Bott. International Press. 1994. - P. 112-125.

51. Friedman, J. Computing Betti numbers via combinatorial Lapla-cians / J. Friedman // Proc. 28th ACM Sympos. Theory Comput.- 1996. P. 386-391.

52. Gu, X. Geometry Images / X. Gu, S. J. Gortler, H. Hoppe // Proc. SIGGRAPH'02. New York, 2002. - P. 355 - 361.

53. Guskov, I. Topological Noise Removal / I. Guskov, Z. Wood // Graph. Interf. 2001. - P. 19-26.

54. Hayat-Legrand, C. Computer calculation of the degree of maps into the Poincare homology sphere / C. Hayat-Legrand, S. Matveev, H. Zieschang // Experimental Mathematics. 2001. - Vol. 10. No. 4.- P. 497-508.

55. Kannan, R. Polynomial algorithms for computing the Smith and Hermite normal forms of integer matrix / R. Kannan, A. Bachem // SIAM Jour.Сотр. 1979. - Vol. 8. - P. 499-507.

56. Lapteva, A. V. Index Vector-Function and Minimal Cycles / A. V. Lapteva, E. I. Yakovlev // Lobachevskii Journal of Mathematics.- 2006. Vol. 22. - P. 35-46.

57. Lapteva, A. V. Minimal 1-Cycles Generating a Canonical Basis of 2-Manifold's Homology Group / A. V. Lapteva, E. I. Yakovlev // International Journal of Pure and Applied Mathematics. 2006. -Vol. 31, No 4. - P. 555-570.

58. Lazarus, F. Computing a Canonical Polygonal Schema of an Ori-entable Triangulated Surface / F. Lazarus, M. Pocchiola, G. Vegter, A. Verroust // Proc. 17th Annu. ACM Sympos. Comput. Geom. -2001. P. 80-89.

59. Matveev, S. V., Algorithmic classification of 3-manifolds and knots / S. V. Matveev // Gazette des Mathematiciens. 2001. - No. 89. - P. 49-61.

60. Matveev, S. V. Computer classification of 3-manifolds / S. V. Matveev // Russian Journal of Mathematical Physics. 2000. -Vol. 7. No. 3. - P. 319-329.

61. Matveev, S. V. Computer presentation of 3-manifolds / S. V Matveev // Lecture Notes in Computer Science. 2001. - Vol. 2243 "Digital and Image Geometry: Advanced Lectures". - P. 59-74.

62. Matveev, S. V., Computer recognition of three-manifolds / S. V. Matveev // Experimental Mathematics. 1998. - Vol. 7. No. 2. -P. 153-161.

63. Shinagawa, Y. Surface coding based on morse theory / Y. Shina-gawa, T. L. Kunii, Y. L. Kergosien // IEEE Computer Graphics and Applications. 1991. - Vol. 11. No. 5. - P. 66-78.

64. Vegter, G. Computational Complexity of Combinatorial Surfaces / G. Vegter, С. K. Yap // Proceedings of the 6th Annual Symposium on Computational Geometry. 1990. - P. 93-111.

65. Wood, Z. Semi-Regular Mesh Extraction from Volumes / Z. Wood, M. Desbrun, P. Schroder, D. Breen // Proceedings of Visualization. 2000. - P. 275-282.

66. Wood, Z. Removing Excess Topology From Isosurfaces / Z. Wood, H. Hoppe, M. Desbrun, P. Schroder // ACM Transactions on Graphics. 2004. - Vol. 23, No 2. - P. 190 - 208.