advertisement

Изчисляване на хомологични групи на симплициални комплекси в R3

63 %
38 %
advertisement
Information about Изчисляване на хомологични групи на симплициални комплекси в R3

Published on August 9, 2008

Author: JD_DECART

Source: slideshare.net

Description

Изчисляване на хомологични групи на симплициални комплекси в R3


Отбор Елементите

Маргарита Ганева

Милана Жилевa

Людмил Ненов

Станимир Тодоров

Йорданка Дърмонска

Стоян Симов

Александър Попов
advertisement

Изчисляване на хомологични групи на си мплициални комплекси в R 3 Отбор Елементите Маргарита Сергеева Ганева Милана Василева Жилевa Людмил Георгиев Ненов Станимир Тодоров Тодоров Йорданка Рангелова Дърмонска Стоян Симеонов Симов Александър Сергеев Попов

Въведение Приложения: представяне на плътни модели чрез симплициални комплекси изчисляване на структурна информация относно симплициални те комплекси в 3D пространството молекулярната биология компютърно насоченото производство

Приложения:

представяне на плътни модели чрез симплициални комплекси

изчисляване на структурна информация относно симплициални те комплекси в 3D пространството

молекулярната биология

компютърно насоченото производство

Нашата цел е : да ви запознаем с нов подход за анализиране на симплициалните комплекси в Евклидовото 3-пространство R 3 Ще обърнем внимание на : изчисляването на хомологичните групи и изобразяването на елементите им методи от топологията, които се използват за анализ на триангулираните 3-многообразия в R 3 , а впоследствие биват прилагани и върху произволен симплициален комплекс след преобразуване то му към хомотопично на него 3-многообразие

Нашата цел е :

да ви запознаем с нов подход за анализиране на симплициалните комплекси в Евклидовото 3-пространство R 3

Ще обърнем внимание на :

изчисляването на хомологичните групи и изобразяването на елементите им

методи от топологията, които се използват за анализ на триангулираните 3-многообразия в R 3 , а впоследствие биват прилагани и върху произволен симплициален комплекс след преобразуване то му към хомотопично на него 3-многообразие

Класически алгоритми привеждане на матрици в канонична форма: нормална форма на Смит Делфинадо и Еделсбрунер : изчислява числата на Бети на симплициалния комплекс в R 3

привеждане на матрици в канонична форма: нормална форма на Смит

Делфинадо и Еделсбрунер : изчислява числата на Бети на симплициалния комплекс в R 3

Нашият алгоритъм базиран на първоначално използваните методи от топологията може да бъде приложен върху комплекс, симулирано преобразуван към 3-многообразие, хомотопично на него общо представяне на алгоритъма: определяме ранга на хомологичните групи и зчисляваме геометрични реализации на множество от генератори, които формират базис от първичната и вторична хомологични групи

базиран на първоначално използваните методи от топологията

може да бъде приложен върху комплекс, симулирано преобразуван към 3-многообразие, хомотопично на него

общо представяне на алгоритъма:

определяме ранга на хомологичните групи

и зчисляваме геометрични реализации на множество от генератори, които формират базис от първичната и вторична хомологични групи

Съдържание: Ще разгледаме основни необходими дефиниции Ще посочим важни теореми Ще покажем как резултатите от тях се отнасят до симплициалните комплекси Накрая ще ви запознаем с алгоритмите и техните сложности

Ще разгледаме основни необходими дефиниции

Ще посочим важни теореми

Ще покажем как резултатите от тях се отнасят до симплициалните комплекси

Накрая ще ви запознаем с алгоритмите и техните сложности

Топологични пространства и карти топологично пространство т опологи я oтворено покритие на топологично пространство компактно топологично пространство свързано множество к омпонент на множество в ътрешност , затворена обвивка , граница непрекъсната функция

топологично пространство

т опологи я

oтворено покритие на топологично пространство

компактно топологично пространство

свързано множество

к омпонент на множество

в ътрешност , затворена обвивка , граница

непрекъсната функция

хомеоморфни множества карта, размерност на карта потапяне n- мерно Евклидово пространство, d- мерно реално полупространство , затворена d- топка, ( d-1 ) - сфера ограничено подпространство хомотопия хомотопични карти хомотопична еквивалентност

хомеоморфни множества

карта, размерност на карта

потапяне

n- мерно Евклидово пространство, d- мерно реално полупространство , затворена d- топка, ( d-1 ) - сфера

ограничено подпространство

хомотопия

хомотопични карти

хомотопична еквивалентност

Симплекси к - симплекс стена, костена, същинска стена барицентрични координати барицентър ориентация на симплекс ориентиран симплекс

к - симплекс

стена, костена, същинска стена

барицентрични координати

барицентър

ориентация на симплекс

ориентиран симплекс

Симплициални комплекси симплициален комплекс подлежащо пространство (носител) размерност на симлициален комплекс подкомплекс главен симплекс Ойлерова характеристика подразделение

симплициален комплекс

подлежащо пространство (носител)

размерност на симлициален комплекс

подкомплекс

главен симплекс

Ойлерова характеристика

подразделение

симплициална карта барицентрично подразделение триангулация триангулируемо топологично пространство

симплициална карта

барицентрично подразделение

триангулация

триангулируемо топологично пространство

Многообразия хомеоморфизъм d- многообразие граница на d- многообразие затворено d- многообразие

хомеоморфизъм

d- многообразие

граница на d- многообразие

затворено d- многообразие

Групи и хомоморфизми функция ƒ: G -> H – хомоморфизъм мономорфизъм, епиморфизъм и изоморфизъм Абелева група a*b = b*a за всяко a, b от G фактор група G/H класове на еквивалентност на елемнтите в G циклична група

функция ƒ: G -> H – хомоморфизъм

мономорфизъм, епиморфизъм и изоморфизъм

Абелева група

a*b = b*a за всяко a, b от G

фактор група G/H

класове на еквивалентност на елемнтите в G

циклична група

Хомологични групи и числа на Бети j-верига - функция c: K j -> Z c = ∑ c(σ) • σ , където σ  K j верижна група граничен оператор граничен хомоморфизъм дефинира се чрез: (∑ c( σ ) • σ ) = ∑ c( σ ) • σ

j-верига - функция c: K j -> Z

c = ∑ c(σ) • σ , където σ  K j

верижна група

граничен оператор

граничен хомоморфизъм

дефинира се чрез: (∑ c( σ ) • σ ) = ∑ c( σ ) • σ

верижен комплекс образ, ядро | } j- граница j- цикъл Ще докажем, че

верижен комплекс

образ, ядро

| }

j- граница

j- цикъл

Ще докажем, че

j- та хомологична група H j = Z j / B j генератор хомологичен клас на j- цикъл j- то число на Бети още една дефиниция на Ойлерова характеристика χ( C* ) = ∑ i (-1) i rank(C i ) rank(C i ) = |{ σ  K | dim σ =I }| χ ( H*(C*) ) = ∑ i (-1) i rank(H i ) = ∑ i (-1) i β i

j- та хомологична група

H j = Z j / B j

генератор

хомологичен клас на j- цикъл

j- то число на Бети

още една дефиниция на Ойлерова характеристика

χ( C* ) = ∑ i (-1) i rank(C i )

rank(C i ) = |{ σ  K | dim σ =I }|

Последователност на Майер – Виеторис т очна редица - възможно безкрайна последователност от групови хомеоморфизми такава че Im φ q +1 = Ker φ q , за всеки индекс q . а ко K 1 , K 2 , и L са подкомплекси на симплициален комплекс Т, такива че K 1 U K 2 = T и K 1 ∩ K 2 = L , то тогава съществува точна редица наричана последователност на Майер – Виеторис за (K 2 , K 2 ).

т очна редица - възможно безкрайна последователност от групови хомеоморфизми

такава че Im φ q +1 = Ker φ q , за всеки индекс q .

а ко K 1 , K 2 , и L са подкомплекси на симплициален комплекс Т, такива че K 1 U K 2 = T и K 1 ∩ K 2 = L , то тогава съществува точна редица

наричана последователност на Майер – Виеторис за (K 2 , K 2 ).

Затворено допълнение в S3

Повърхнини род на повърхност плътен 3-тор дръжковидно тяло Теорема за плътния то р : Даден е тор S в R3. Тогава или или е плътен тор.

род на повърхност

плътен 3-тор

дръжковидно тяло

Теорема за плътния то р :

Даден е тор S в R3. Тогава или или е плътен тор.

Възли и свързване възел обкръжаваща изотопия изходна карта еквивалетни възли тривиален възел свързани повърхнини (възли) възлеста повърхност

възел

обкръжаваща изотопия

изходна карта

еквивалетни възли

тривиален възел

свързани повърхнини (възли)

възлеста повърхност

3-многообразия в R 3 Имаме симплициален комплекс, потопен в R 3 , и изчисляваме хомологичните му групи чрез нагъване на комплекса до 3-многообразие в R 3 . М е компактно свързано триангулирано 3-многообразие в R 3 . Границата bd(M) е непресичащо се обединение на r ориентируеми повърхности S i с род g i съответно . И нтуитивно геометрично описание на М .

Имаме симплициален комплекс, потопен в R 3 , и изчисляваме хомологичните му групи чрез нагъване на комплекса до 3-многообразие в R 3 .

М е компактно свързано триангулирано 3-многообразие в R 3 .

Границата bd(M) е непресичащо се обединение на r ориентируеми повърхности S i с род g i съответно .

И нтуитивно геометрично описание на М .

Втора хомологична група Теорема 1: Хомологичните класове на повърхностите , образува т база на H 2 (M). Доказателство Ще докажем, че хомологичният клас на всеки 2-цикъл зависи линейно от [Si] Да предположим, че S съдържа S, S i1 , …, S ik в своята вътрешност равенството [S] + [S i1 ] + … + [S ik ] = 0 в хомологичните класове важи с подходяща ориентация на S ji [S] = - [S i1 ] + … + [S ik ] Извод 1: β2(М) = r-1.

Теорема 1:

Хомологичните класове на повърхностите , образува т база на H 2 (M).

Доказателство

Ще докажем, че хомологичният клас на всеки 2-цикъл зависи линейно от [Si]

Да предположим, че S съдържа S, S i1 , …, S ik в своята вътрешност

равенството [S] + [S i1 ] + … + [S ik ] = 0 в хомологичните класове важи с подходяща ориентация на S ji

[S] = - [S i1 ] + … + [S ik ]

Извод 1:

β2(М) = r-1.

Оттук нататък под повърхност винаги ще разбираме ориентирана повърхност, дори нещо повече - такава, която е потопима в R 3 по-големите разрези-елипси представляват надлъжни генератори по-малките представляват напречни генератори

Оттук нататък под повърхност винаги ще разбираме ориентирана повърхност, дори нещо повече - такава, която е потопима в R 3

по-големите разрези-елипси представляват надлъжни генератори

по-малките представляват напречни генератори

Първа хомологична група Теорема 2: Доказателство Триангулация K d на M d може да бъде получена чрез удвояване на К За Ойлеровата характеристика на K d имаме, че

Теорема 2:

Доказателство

Триангулация K d на M d може да бъде получена чрез удвояване на К

За Ойлеровата характеристика на K d имаме, че

Знаем, че рангът на нулевата хомологична група е равен на 1, когато K е свързано, както и Последното равенство идва от Извод 1 Така получаваме Тази теорема ни дава размера на базата - ранга на H 1 (M)

Знаем, че рангът на нулевата хомологична група е равен на 1, когато K е свързано, както и

Последното равенство идва от Извод 1

Така получаваме

Тази теорема ни дава размера на базата - ранга на H 1 (M)

3-кълбо с дупки Избираме 2g различни точки { p i , q i : i=1…g } върху границата S 2 на кълбото B 3 в R 3 . Избираме дъги d i , свързващи p i към q i така, че освен за своите крайни точки p i и q i , d i лежи във вътрешността на B 3 и по този начин точките d i са две по две непресичащи се двойки. Избираме две по две непресичащи се затворени цилиндрични околности N i в дъгите d i . Всяка N i е хомеоморфна на d i х B 2 . Задаваме

Избираме 2g различни точки { p i , q i : i=1…g } върху границата S 2 на кълбото B 3 в R 3 .

Избираме дъги d i , свързващи p i към q i така, че освен за своите крайни точки p i и q i , d i лежи във вътрешността на B 3 и по този начин точките d i са две по две непресичащи се двойки.

Избираме две по две непресичащи се затворени цилиндрични околности N i в дъгите d i . Всяка N i е хомеоморфна на d i х B 2 .

Задаваме

Теорема 3: Компактно 3-многообразие M в R 3 , ограничено чрез единична повърхност L от род g, е хомеоморфно на някое 3-кълбо с g дупки Q. Доказателство И ндукция по рода g на повърхността L Базата при g=1 следва от теоремата за пълтния тор Нека I е затворена поддъга на S 1 Пространството O = int(I×B2)int( ) може да се приеме като отворено кълбо или отворен цилиндър

Теорема 3:

Компактно 3-многообразие M в R 3 , ограничено чрез единична повърхност L от род g, е хомеоморфно на някое 3-кълбо с g дупки Q.

Доказателство

И ндукция по рода g на повърхността L

Базата при g=1 следва от теоремата за пълтния тор

Нека I е затворена поддъга на S 1

Пространството O = int(I×B2)int( ) може да се приеме като отворено кълбо или отворен цилиндър

Имаме: B 3 = S 3 – О защото N 1 е затворена цилиндрична околност на дъгата d 1 = cl(S 1 – I)×(0,0), където (0,0) е центърът на B 2 N 1 пресича M точно в cl(S 1 – I)×bd(B 2 ) , следователно M = cl(B 3 - N 1 ) Допускаме, че теоремата е вярна за повърхности от род най-малко g Предполагаме, че L има род g+1

Имаме: B 3 = S 3 – О

защото

N 1 е затворена цилиндрична околност на дъгата d 1 = cl(S 1 – I)×(0,0), където (0,0) е центърът на B 2

N 1 пресича M точно в cl(S 1 – I)×bd(B 2 ) , следователно M = cl(B 3 - N 1 )

Допускаме, че теоремата е вярна за повърхности от род най-малко g

Предполагаме, че L има род g+1

Н амираме основна проста затворена крива J в L, която ограничава парче по парче продълговатия кръг D Предполагаме, че D е в M , а след това че D е в и доказваме, че М е хомеоморфно на 3-кълбо с g+1 дупки Л ема 1: Ако Q е 3-кълбо с g дупки, тогава е дръжковидно тяло от род g. Доказателство Дефиниция на надлъжни и напречни генератори на повърхност S с род g

Н амираме основна проста затворена крива J в L, която ограничава парче по парче продълговатия кръг D

Предполагаме, че D е в M , а след това че D е в и доказваме, че М е хомеоморфно на 3-кълбо с g+1 дупки

Л ема 1:

Ако Q е 3-кълбо с g дупки, тогава е дръжковидно тяло от род g.

Доказателство

Дефиниция на надлъжни и напречни генератори на повърхност S с род g

Извод 2 : Ако М е компактно 3-многообразие в R 3 , ограничено чрез единична повърхност L от род g, и C i i = 1,…,g са надлъжни генератори на L, и D i , i = 1,…,g са g напречни генератори на L, тогава: C i и D i , i = 1, ... ,g заедно формират база H 1 (L). C i , i = 1, ... ,g формира база H 1 (M). D i , i = 1, ... ,g формира база H 1 ( ). Доказателство Имайки предвид, че Това, което следва е част от редицата на Майер-Виеторис ).

Извод 2 :

Ако М е компактно 3-многообразие в R 3 , ограничено чрез единична повърхност L от род g, и C i i = 1,…,g са надлъжни генератори на L, и D i , i = 1,…,g са g напречни генератори на L, тогава:

C i и D i , i = 1, ... ,g заедно формират база H 1 (L).

C i , i = 1, ... ,g формира база H 1 (M).

D i , i = 1, ... ,g формира база H 1 ( ).

Доказателство

Имайки предвид, че

Това, което следва е част от редицата на Майер-Виеторис

Теорема 4: Нека и са g i на брой надлъжни и напречни пораждащи кръгове на S i . Тогава множеството от хомологични класове от кръгове формират база на H 1 (M).

Теорема 4:

Нека и са g i на брой надлъжни и напречни пораждащи кръгове на S i . Тогава множеството от хомологични класове от кръгове

формират база на H 1 (M).

Доказателство φ е изоморфизъм φ съотнася надлъжните генератори на S 1 ,…,S r-1 и напречните генератори на S r към база на H 1 ( ) С ледва, че φ трябва да съотнася останалите генератори в L

Доказателство

φ е изоморфизъм

φ съотнася надлъжните генератори на S 1 ,…,S r-1 и напречните генератори на S r към база на H 1 ( )

С ледва, че φ трябва да съотнася останалите генератори в L

 

Алгоритми За да изчислим числата на Бети ще имаме нужда от следното: кои са тези заграждащи повърхности в нашето многообразие М , както и изчисляването на техния род или да намерим всички заграждащи повърхности и след преброяване на симплексите на К да определим Ойлеровата харектеристика

За да изчислим числата на Бети ще имаме нужда от следното:

кои са тези заграждащи повърхности

в нашето многообразие М , както и

изчисляването на техния род

или да намерим всички заграждащи

повърхности и след преброяване на

симплексите на К да определим

Ойлеровата харектеристика

Относно генераторите Д ва главни изчислителни въпроса за определянето на H 1 (K): При потапяне на К в R 3 как да разберем коя от повърхностите е затворената повърхност S r , т.е. най-външната повърхност обхващата всички други? При дадено множество от цикли (2g i за съответното S i ) как да разберем кои са напречните и надлъжните? Това е информация за разположението на S i относно останалата част от R 3 .

Д ва главни изчислителни въпроса за определянето на H 1 (K):

При потапяне на К в R 3 как да разберем коя от повърхностите е затворената повърхност S r , т.е. най-външната повърхност обхващата всички други?

При дадено множество от цикли (2g i за съответното S i ) как да разберем кои са напречните и надлъжните? Това е информация за разположението на S i относно останалата част от R 3 .

Свързващо число L(C 1 , C 2 ) C 1 и C 2 са ориетнирани многоъгълни възли в R 3 Две еквивалентни дефиниции: А ко хомологичният клас [C 1 ] = n[C’] в H 1 (R 3 – C 2 ), дефинираме L(C 1 , C 1 ) = n . С регулярна проекция π

C 1 и C 2 са ориетнирани многоъгълни възли в R 3

Две еквивалентни дефиниции:

А ко хомологичният клас [C 1 ] = n[C’] в H 1 (R 3 – C 2 ), дефинираме L(C 1 , C 1 ) = n .

С регулярна проекция π

З а всяка повърхност S i конструираме двойката генератори и съответно по дължина и по ширина за всяко k=1 ,..., g i . Ако k е едно и също, то имаме една обща пресечна точка. К онструираме и първото барицентрично подразделение К’ на К . Взимаме предвид надлъжния пораждащ кръг на вътрешна повърхност S i .

З а всяка повърхност S i конструираме двойката генератори и съответно по дължина и по ширина за всяко k=1 ,..., g i .

Ако k е едно и също, то имаме една обща пресечна точка.

К онструираме и първото барицентрично подразделение К’ на К .

Взимаме предвид надлъжния пораждащ кръг на вътрешна повърхност S i .

 

Add a comment

Related pages

/ COMPUTATIONAL TOPOLOGY : 2+0+1 - fmi.uni-sofia.bg

... методи за изчисляване, ... Симплициални комплекси ... на групи, хомологични ...
Read more