SIMPLICIALNI KOMPLEKSI IN DISKRETNA
MORSOVA TEORIJA
ALEKSANDRA FRANC
Fakulteta za računalnǐstvo in informatiko
Univerza v Ljubljani
Math. Subj. Class. (2010): 55U10, 57R70
V članku predstavimo enostavne, a nadvse uporabne simplicialne komplekse in osnove
diskretne Morsove teorije.
SIMPLICIAL COMPLEXES AND DISCRETE MORSE THEORY
This paper introduces the simple and useful concept of a simplicial complex and the
basics of discrete Morse theory.
Uvod
Amerǐski matematik Marston Morse [4, 5] je opazil, da so določene gladke
funkcije na gladkih mnogoterostih tesno povezane s topologijo teh mnogote-
rosti, in tako je nastala Morsova teorija. Ta teorija zgradi sklenjene gladke
mnogoterosti iz informacije o (končno mnogo) kritičnih točkah Morsovih
funkcij oziroma iz (končnega števila) geometrijsko preprostih gradnikov. En
primer take funkcije in pripadajoče dekompozicije je na sliki 1. Na žalost
pa je pri takih dekompozicijah mnogoterosti na končno število lepih kosov
še vedno treba vedeti, kako se ti kosi med sabo zlepijo, načinov za to pa je,
na žalost (ali pa morda veselje algebraičnih topologov), v večini dimenzij
ogromno.
V veliko veselje številnih bolj ali manj uporabnih matematikov in ra-
čunalnikarjev pa je prav tako amerǐski matematik, Robin Forman, v letih
1998 [1] in 2002 [2] svetu predstavil diskretno verzijo Morsove teorije, ki je
definirana za prostore s kombinatorično strukturo (za simplicialne komple-
kse, za celične komplekse ipd.), in pri kateri so tako Morsove funkcije kot
pripadajoča vektorska polja diskretni objekti.
Tako sta področji uporabne matematike in računalnǐstva dobili teorijo,
ki ima aplikacije v topološki analizi podatkov, računski homologiji, konfigu-
racijskih prostorih, topološkem poenostavljanju objektov in odstranjevanju
šuma, pa še kje.
Obzornik mat. fiz. 65 (2018) 6 201
Aleksandra Franc
f
R
b bx f(x)
b
b
b
b
Slika 1. Primer gladke Morsove funkcije na gladki mnogoterosti (torusu) s štirimi kritič-
nimi točkami in pripadajočo dekompozicijo.
V tem članku bomo najprej vpeljali pojem simplicialnih kompleksov
ter si ogledali nekaj njihovih lastnosti. Nato se bomo sprehodili čez osnove
diskretne Morsove teorije (teh je presenetljivo malo in so presenetljivo lahko
dostopne).
Simplicialni kompleksi
Začnimo s točko v dimenziji 0. V dimenziji 1 ni velikih presenečenj, iz točke
nastane daljica z dvema krajǐsčema. V dimenziji 2 hitro najdemo vsaj dve
možnosti za smiselno enostaven geometrijski gradnik: trikotnik ali kvadrat.
Izberimo trikotnik. V dimenziji 3 bo na vrsti tetraeder (skupaj z notra-
njostjo). Tako nadaljujemo. Opisali smo osnovne gradnike simplicialnih
kompleksov, simplekse (slika 2). Omenimo še, da bi z izbiro kvadrata v
dimenziji 2 in z ustreznimi posplošitvami v vǐsjih dimenzijah lahko prǐsli do
npr. kubičnih kompleksov ali pa do prodsimplicialnih kompleksov, ampak o
tem morda več kdaj drugič.
Da ne bo dilem, kako so videti simpleksi vǐsjih dimenzij, povejmo vse še
malo bolj natančno. Za začetek vpeljimo pojem standardnega n-simpleksa
202 Obzornik mat. fiz. 65 (2018) 6
Simplicialni kompleksi in diskretna Morsova teorija
b b b b b
b
b b
b
b
Slika 2. 0-simpleks, 1-simpleks, 2-simpleks in 3-simpleks.
(slika 3), ki je podan kot konveksna ogrinjača n+ 1 točk s koordinatami
(1, 0, . . . , 0), (0, 1, 0, . . . , 0), . . . , (0, . . . , 0, 1) ∈ Rn+1.
Definicija 1. Standardni n-simpleks je podmnožica
∆n = {λ1e1+ · · ·+λnen+1 | λ1+ · · ·+λn+1 = 1 in λi ≥ 0 za vse i} ⊂ R
n+1,
pri čemer smo z ei ∈ R
n+1 označili vektor, ki ima na i-tem mestu 1, na vseh
preostalih pa 0.
b b
b
b
b
b
1 (1, 0)
(0, 1)
(1, 0, 0)
(0, 0, 1)
(0, 1, 0)
Slika 3. Standardni 0-simpleks, 1-simpleks in 2-simpleks.
Splošen n-simpleks je posplošitev standardnega n-simpleksa, torej objekt,
ki ima n + 1 oglǐsč, ki so povezana z
(
n+1
2
)
daljicami, na katere je napetih(
n+1
3
)
trikotnikov, medtem ko vsaka štiri različna oglǐsča določajo enega od(
n+1
4
)
tetraedrov in tako dalje. Z drugimi besedami, splošen n-simpleks je
podan z množico n + 1 oglǐsč, vsako njeno podmnožico pa imenujemo lice
danega simpleksa in je sama po sebi spet simpleks. Če je simpleks τ lice
simpleksa σ, pǐsemo τ ≤ σ. Vsak simpleks je sam svoje lice, lica nižjih di-
menzij pa imenujemo prava lica. Če pri tem ne pozabimo na prazno lice, ki
ustreza prazni podmnožici oglǐsč, smo morda koga spomnili na dobro znano
201–217 203
Aleksandra Franc
formulo: (
n
0
)
+
(
n
1
)
+ · · ·+
(
n
n− 1
)
+
(
n
n
)
= 2n.
In res, n-simpleks ima 2n+1 lic. To je v resnici problem, ki lahko zelo hitro
pokvari učinkovitost algoritmov, ki delajo s simplicialnimi kompleksi. Če bo
naš algoritem nekaj naredil ali preveril za vsako lice simpleksa, bo takoj vsaj
eksponentno zahteven glede na dimenzijo simpleksa. Računska zahtevnost
je sicer še ena zanimiva zgodba, ki jo bomo tokrat izpustili. Omenimo le, da
lahko težavo precej omilimo, če se mora npr. naš algoritem ukvarjati le z lici
kodimenzije 1, tj. s takimi, katerih dimenzija je za 1 manǰsa od dimenzije
simpleksa. Takih je namreč le
(
n+1
n
)
= n+ 1.
Če želimo za neki simpleks σ poudariti njegovo dimenzijo, jo običajno
zapǐsemo v eksponent, npr. σn označuje n-dimenzionalni simpleks z imenom
σ.
Zdaj pa je prǐsel čas, da naše osnovne gradnike simplekse na smiseln
način združimo v večjo celoto. Na sliki 4 je prikazanih nekaj načinov zdru-
ževanja, ki niso sprejemljivi, na sliki 5 pa nekaj takih, ki so.
b b
b
b
b
b
b
b
b b
b
Slika 4. To niso simplicialni kompleksi. V prvem primeru eden od diagonalnih 1-
simpleksov drugega seka v notranjosti in ne v skupnem licu (oglǐsču), v drugem primeru
niso vključena vsa lica 2-simpleksa, v tretjem primeru pa se pojavita oba problema hkrati.
b b
b b
b
b
b b
b
b
b
Slika 5. To pa so simplicialni kompleksi.
204 Obzornik mat. fiz. 65 (2018) 6
Simplicialni kompleksi in diskretna Morsova teorija
Definicija 2. Simplicialni kompleks K je množica simpleksov, ki zadošča
naslednjim pogojem:
1. vsako lice simpleksa iz K je vsebovano v K in
2. presek poljubnih dveh simpleksov σ1 in σ2 je lice tako v σ1 kot v σ2.
Torej, skupaj z vsakim simpleksom σ so v simplicialnem kompleksu K
vsebovana vsa njegova lica in simpleksi so lahko zlepljeni samo vzdolž sku-
pnih lic.
Vsak simpleks σ ∈ K, ki ni pravo lice nobenega drugega simpleksa iz K,
imenujemo maksimalni simpleks. Simplicialni kompleks je torej natančno
določen s seznamom svojih maksimalnih simpleksov.
Unija vseh pravih lic simpleksa σ sestavlja njegov rob ∂σ, preostale točke
iz simpleksa σ pa spadajo v njegovo notranjost
◦
σ (slika 6). Z izjemo 0-
simpleksov torej vsaka točka v simplicialnem kompleksu pripada notranjo-
sti natanko enega od simpleksov (v vseh preostalih simpleksih, ki to točko
vsebujejo, leži na robu).
b b
b
b b
b
σ ◦σ ∂σ
Slika 6. Notranjost in rob 2-simpleksa σ.
Oglejmo si še tri zanimive tipe simplicialnih kompleksov, ki jih lahko
konstruiramo kot podmnožice večjih simplicialnih kompleksov.
Definicija 3. Simplicialno zaprtje cl(σ) simpleksa σ ∈ K je podkompleks,
sestavljen iz vseh simpleksov, ki so lica σ. Simplicialno zaprtje cl(S) pod-
množice simpleksov S v simplicialnem kompleksu K je podkompleks, sesta-
vljen iz vseh simpleksov, ki so lica kakšnega simpleksa iz S.
Definicija 4. Zvezda st(σ) simpleksa σ iz K je sestavljena iz vseh simple-
ksov v K, ki imajo σ za lice. Zvezda st(S) podmnožice simpleksov S iz K je
unija zvezd st(σ) po vseh simpleksih σ iz S.
201–217 205
Aleksandra Franc
Definicija 5. Okvir lk(S) podmnožice S iz K je razlika množic
cl(st(S)) \ st(cl(S)),
tj. iz simplicialnega zaprtja zvezde odstranimo vse elemente, ki so v zvezdi
simplicialnega zaprtja.
Primer 6. Na sliki 7 je primer simplicialnega kompleksa, sestavljenega iz
osmih maksimalnih 2-simpleksov (in seveda vseh pripadajočih lic). Oglejmo
si, kako so videti zgornje tri konstrukcije za 0-simpleks v. Vidimo, da simpli-
cialno zaprtje cl(v) vsebuje samo 0-simpleks v. Zvezda st(v) vsebuje poleg
0-simpleksa v še vse 1- in 2-simplekse, ki imajo 0-simpleks v v robu (ki so
torej en korak od v). Okvir
lk(v) = cl(st(v)) \ st(cl(v)) = cl(st(v)) \ st(v)
pa vsebuje simplekse, ki so v simplicialnem zaprtju zvezde st(v), v zvezdi
pa ne (torej take, ki so dva koraka od v po najkraǰsi poti).
b b b
b b
b b b
b b b
b b b
b b b
b b b
b b b
b b b
b b
b b
b
bb
b
v v v
cl(v) st(v) lk(v)
Slika 7. Simplicialno zaprtje, zvezda in okvir 0-simpleksa v (primer 6). Simplicialno zapr-
tje vsebuje samo oglǐsče v, zvezda poleg tega še po šest v-ju sosednjih robov in trikotnikov,
okvir pa le po šest oglǐsč in robov, ki so sosedi sosedov v.
Naloga 1. Za simplicialni kompleks s slike 8 določi naslednje podkomple-
kse:
cl(B), cl(BD), cl(BDF ), st(B), st(BD), st(BDF ), lk(B), lk(BD), lk(BDF ).
V nadaljevanju si oglejmo zanimivo konstrukcijo, s pomočjo katere iz
danega simplicialnega kompleksa dobimo nov, bolj razdrobljen simplicialni
kompleks. Začnimo z definicijo za simplicialne komplekse in si prihranimo
težave za konec.
206 Obzornik mat. fiz. 65 (2018) 6
Simplicialni kompleksi in diskretna Morsova teorija
A C
E
B
DF
b b
b b
b
b
Slika 8. Simplicialni kompleks (naloga 1).
Definicija 7. Baricentrična subdivizija simplicialnega kompleksa K je sim-
plicialni kompleks K̂, ki je unija baricentričnih subdivizij vseh simpleksov
iz K.
Zdaj pa potrebujemo še definicijo baricentrične subdivizije za posamezni
simpleks. Formalna definicija je malce bolj zapletena, zato si najprej oglejmo
primer. Baricentrične subdivizije za 0, 1 in 2-simpleks so prikazane na sliki
9.
b b
b
b
b
b b
b b
b
b
b
b
b
b
b
b
Slika 9. Baricentrična subdivizija za 0, 1 in 2-simpleks.
To idejo bi želeli posplošiti na simplekse poljubne dimenzije. S pomočjo
permutacij lahko na kratko povemo, katere simplekse dodamo, vendar je
taka definicija precej abstraktna, zato jo bomo poskusili razumeti tako, da
bomo baricentrično subdivizijo zgradili postopoma z dodajanjem simpleksov
po dimenzijah. Vseeno najprej zapǐsimo formalno definicijo:
201–217 207
Aleksandra Franc
Definicija 8. Baricentrična subdivizija n-dimenzionalnega simpleksa σ z
oglǐsči v1, . . . , vn+1 je unija (n+ 1)! simpleksov dimenzije n. Vsak tak sim-
pleks z oglǐsči p1, . . . , pn+1 ustreza neki permutaciji vπ(1), . . . , vπ(n+1), in
sicer tisti, za katero je pi težǐsče točk vπ(1), . . . , vπ(i+1).
Vsak simpleks simplicialnega kompleksa K bo ustrezal natanko enemu
0-simpleksu baricentrične subdivizije K̂. Baricentrično subdivizijo K̂ torej
začnemo graditi tako, da v težǐsče vsakega simpleksa σ ∈ K postavimo
en 0-simpleks, vσ, in vsakega od teh povežemo z vsemi vα, za katere je
α ≤ σ. Dobili smo 1-dimenzionalni simplicialni kompleks, ki bo 1-skelet
baricentrične subdivizije K̂. Če je bila dimK = 1, smo končali, sicer pa za
vsak 2-simpleks σ2 ∈ K za vsako verigo simpleksov α0 ≤ β1 ≤ σ dodamo
v K̂ 2-simplekse, napete na vα, vβ in vσ. Dobili smo 2-skelet baricentrične
subdivizije. Če je bila dimK = 2, smo končali, sicer ponovimo postopek in
za vse σ3 ∈ K za vsako verigo simpleksov α0 ≤ β1 ≤ γ2 ≤ σ dodamo v K̂
3-simplekse, napete na vα, vβ, vγ in vσ, in tako naprej.
Iz formalne definicije je jasno, da število simpleksov v baricentrični sub-
diviziji z dimenzijo izjemno hitro narašča. Če je dimK = n, ima K̂ vsaj
(n+1)! simpleksov. Teoretično je baricentrična divizija torej uporabna, ka-
dar želimo npr. omejiti velikost največjega simpleksa, ker se ta s subdivizijo
strogo zmanǰsa. Seveda pa hkrati zelo povečamo število simpleksov (funk-
cija n! narašča še veliko hitreje kot funkcija 2n, ki smo jo srečali zgoraj),
zato se v aplikacijah običajno ne obnese, sploh če bi morali za zmanǰsanje
maksimalnega premera simpleksov baricentrično divizijo uporabiti večkrat
zapored. Ta postopek pa lahko posplošimo na konveksne politope in takrat
je baricentrična subdivizija zelo uporabna, saj poliedre spremeni v simplici-
alne komplekse, ki so zaradi bolj homogene strukture s stalǐsča računalnǐskih
aplikacij bolj priročni.
Naloga 2. Naj bo K triangulacija ravninskega poligona, tj. povezan 2-
dimenzionalni simplicialni kompleks, v katerem so vsi maksimalni simpleksi
trikotniki, ki ležijo v isti ravnini in se sekajo vzdolž stranic.
(a) Dokaži, da lahko oglǐsča njegove baricentrične subdivizije pobarvamo s
tremi barvami tako, da nobeni dve oglǐsči iste barve ne bosta sosednji
(tj. povezani z 1-simpleksom).
208 Obzornik mat. fiz. 65 (2018) 6
Simplicialni kompleksi in diskretna Morsova teorija
(b) Dokaži, da lahko 2-simplekse v baricentrični subdiviziji K pobarvamo z
dvema barvama tako, da bosta vsaka dva 2-simpleksa, ki imata skupno
daljico, različne barve.
Oglejmo si še, kako lahko zgradimo simplicialne komplekse, ki pripadajo
določenim družinam grafov.
Naj boKn poln graf z n vozlǐsči (graf, v katerem sta poljubni dve vozlǐsči
sosednji). Oglejmo si družino Vn njegovih vpetih podgrafov (vpet podgraf
grafa G je podgraf, ki vsebuje vsa vozlǐsča iz G in nekatere od povezav). Če
za vsak graf z lastnostjo L velja, da imajo to lastnost tudi vsi njegovi vpeti
podgrafi, pravimo, da je lastnost L monotono padajoča. Primeri monotono
padajočih lastnosti so:
• graf nima več kot k povezav,
• vsa vozlǐsča grafa imajo stopnjo ≤ δ (tj. vsako vozlǐsče ima največ δ
sosedov),
• graf ni povezan (tj. množica vozlǐsč razpade na več podmnožic, tako da
med vozlǐsči iz različnih podmnožic ni povezav),
• graf nima Hamiltonovega cikla (tj. ne obstaja sklenjena pot po grafu,
ki bi vsako vozlǐsče obiskala natanko enkrat),
• graf je dvodelen (tj. vozlǐsča lahko razdelimo na dve podmnožici tako,
da vozlǐsča, ki pripadajo isti podmnožici, niso povezana),
• vozlǐsča grafa lahko pobarvamo z b barvami tako, da nobeni sosednji
vozlǐsči nista iste barve.
Množici grafov, ki imajo dano monotono padajočo lastnost L, lahko pri-
redimo simplicialni kompleks. Na primer, označimo z Nn ⊂ Vn množico
vseh nepovezanih vpetih podgrafov polnega grafa Kn. V pripadajočem sim-
plicialnem kompleksu Cn ustrezajo k-simpleksi tistim nepovezanim vpetim
podgrafom, ki imajo natanko k+1 povezav. Ker je nepovezanost monotono
padajoča lastnost, so v Cn skupaj z vsakim simpleksom tudi vsa njegova lica
in res dobimo simplicialni kompleks.
201–217 209
Aleksandra Franc
Primer 9. Za n = 4 dobimo simplicialni kompleks s šestimi 0-simpleksi,
petnajstimi 1-simpleksi in štirimi 2-simpleksi. Podgrafi, ki ustrezajo posa-
mezim simpleksom, so prikazani na sliki 11. Poimenovali smo jih tako, da
smo povezave grafa K4 poimenovali s črkami od A do F , nato pa vsakemu
podgrafu priredili niz, ki ustreza njegovim povezavam. Z nekaj truda lahko
C4 tudi narǐsemo tako, da se 2-simpleksi ne prekrivajo (slika 10). Nekaj več o
strukturi simplicialnih kompleksov Cn bomo povedali na koncu naslednjega
razdelka.
A
B
C
D E
F
bb
b
bb
b
Slika 10. Simplicialni kompleks C4, ki pripada nepovezanim vpetim podgrafom polnega
grafa K4. Narǐsemo ga lahko tako, da le 1-simpleksi AE, BF in CD ne ležijo v ravnini.
Diskretna Morsova teorija
Zdaj ko smo se seznanili s simplicialnimi kompleksi, se lahko lotimo diskretne
Morsove teorije. Začnimo pri funkcijah.
Funkcija f : K → R vsakemu simpleksu iz K priredi neko realno število.
Diskretna Morsova funkcija to naredi tako, da vrednost funkcije načeloma
narašča z dimenzijo z največ eno izjemo pri vsakem simpleksu. Formalno
definicijo običajno zapǐsemo takole:
210 Obzornik mat. fiz. 65 (2018) 6
Simplicialni kompleksi in diskretna Morsova teorija
b
b
b
b
A
b
b
b
b
B
b
b
b
b
C
b
b
b
b
D
b
b
b
b
E
b
b
b
b
F
b
b
b
b
AB
b
b
b
b
AC
b
b
b
b
AD
b
b
b
b
AE
b
b
b
b
AF
b
b
b
b
BC
b
b
b
b
BD
b
b
b
b
BE
b
b
b
b
BF
b
b
b
b
CD
b
b
b
b
CE
b
b
b
b
CF
b
b
b
b
DE
b
b
b
b
DF
b
b
b
b
EF
b
b
b
b
ABD
b
b
b
b
ACF
b
b
b
b
BCE
b
b
b
b
DEF
Slika 11. Nepovezani vpeti podgrafi polnega grafa K4.
Definicija 10. Funkcija f : K → R je diskretna Morsova funkcija, če za
vsak p-dimenzionalni simpleks σp iz K velja:
1. množica (p+ 1)-dimenzionalnih simpleksov
{αp+1 ∈ K | σ ≤ α in f(α) ≤ f(σ)}
vsebuje največ en element in
2. množica (p− 1)-dimenzionalnih simpleksov
{βp−1 ∈ K | β ≤ σ in f(β) ≥ f(σ)}
vsebuje največ en element.
201–217 211
Aleksandra Franc
Če sta za kak simpleks σ obe množici iz definicije prazni, pravimo, da je σ
kritični simpleks.
Primer 11. Naj boK poljuben simplicialni kompleks in f : K → R podana
s predpisom f(σ) = dim(σ) za vse σ ∈ K. Potem je f Morsova funkcija
na K in vsi simpleksi v K so kritični. Ta primer pokaže, da je za poljuben
simplicialni kompleks K množica diskretnih Morsovih funkcij na K nepra-
zna. Seveda pa nas običajno zanimajo takšne diskretne Morsove funkcije,
ki imajo čim manj kritičnih celic.
Čeprav je morda videti, da bi lahko imeli po definiciji pri vsakem sim-
pleksu dve izjemi, eno v dimenziji več in eno v dimenziji manj, pa se to ne
more zgoditi. Dokaz je izjemno preprost, zato si ga oglejmo.
Trditev 12. Naj bo f : K → R diskretna Morsova funkcija na simplicial-
nem kompleksu K in naj bo σ ∈ K simpleks, ki ni kritičen. Potem velja
natanko ena od naslednjih trditev:
1. Obstaja (p + 1)-dimenzionalni simpleks α, za katerega je σ ≤ α in je
f(α) ≤ f(σ).
2. Obstaja (p−1)-dimenzionalni simpleks β, za katerega je β ≤ σ in f(β) ≥
f(σ).
Dokaz. Ker simpleks σ ni kritičen, obstaja gotovo vsaj en od simpleksov α
in β. Denimo, da obstajata oba. Potem je p ≥ 1 zaradi drugega pogoja in je
dim(α) ≥ 2. Za vsa preostala p-dimenzionalna lica (p-lica) γ 6= σ simpleksa
α potem velja f(γ) < f(α), saj je f Morsova funkcija in α že ima eno izjemo
v dimenziji p. Ampak β je (p − 1)-lice σ, ki je p-lice (p + 1)-simpleksa α,
zato je β tudi (p − 1)-lice α (slika 12). To pa pomeni, da obstaja še eno
p-lice γ 6= σ simpleksa α, tako da je β ≤ γ. Vendar β že ima izjemo pri σ,
zato je f(β) < f(γ). Če vse neenakosti zberemo skupaj, vidimo, da je
f(β) ≥ f(σ) ≥ f(α) > f(γ) > f(β).
To protislovje nam pove, da ne moreta biti hkrati izpolnjena oba pogoja.
Obstaja torej natanko eden od simpleksov α in β.
212 Obzornik mat. fiz. 65 (2018) 6
Simplicialni kompleksi in diskretna Morsova teorija
b b
b
β σ
γ
α
b b
b
b
A B
C
D
σ = ABC
α = ABCD
β = AB
γ = ABD
Slika 12. Situacija za primera p = 1 in p = 2 (trditev 12).
Trditev 12 nam omogoča, da povežemo diskretne Morsove funkcije z
določenimi diskretnimi vektorskimi polji.
Definicija 13. Diskretno vektorsko polje V na simplicialnem kompleksu K
je družina parov (τp, σp+1) simpleksov τ, σ ∈ K sosednjih dimenzij s τ ≤ σ,
za katero velja, da se noben simpleks iz K ne pojavi v več kot enem paru.
Polje lahko grafično predstavimo tako, da za vsak par (τp, σp+1) ∈ V
narǐsemo puščico od sredǐsča τ do sredǐsča σ. Če simpleks ne pripada no-
benemu paru, pravimo, da je kritičen. Povezavo z diskretnimi Morsovimi
funkcijami nam da naslednja definicija.
Definicija 14. Naj bo K simplicialni kompleks in f diskretna Morsova
funkcija na K. Gradientno vektorsko polje funkcije f , označimo ga z −∇f ,
ima za kritične simplekse vse kritične simplekse funkcije f . Če neki σp ni
kritični simpleks za f , potem obstaja natanko en simpleks αp+1 ali βp−1,
kjer ima funkcija f nižjo oziroma vǐsjo vrednost. V prvem primeru je v
polju −∇f par (σ, α), v drugem primeru pa par (β, σ).
Oznako −∇f uporabljamo zato, ker puščice gradientnega polja prikazu-
jejo smer (strogega) padanja funkcije f .
V vsakem diskretnem vektorskem polju so poti zaporedja puščic, pri
katerih je začetek vsake naslednje puščice lice kodimenzije 1 simpleksa, ki
je bil konec preǰsnje puščice. Zaporedje parov (τp−11 , σ
p
1) . . . (τ
p−1
n , σ
p
n), kjer
je τi ≤ σi za i = 1, . . . n in τi+1 ≤ σi za i = 1, . . . n− 1, je p-pot doľzine n.
Primer 15. Denimo, da je diskretna Morsova funkcija na simplicialnem
201–217 213
Aleksandra Franc
kompleksu s slike 13 podana z naslednjimi vrednostmi:
A B C D E F G AB AC BC BD BE
7 5 5 2 0 2 2 6 9 6 3 6
CD DE DF EF EG FG ABC BCD EFG
3 1 3 1 1 4 8 4 3
V pripadajočem vektorskem polju so maksimalne 1-poti
• (F,EF ) dolžine 1,
• (G,EG) dolžine 1,
• (C,CD)(D,DE) dolžine 2 ter
• (A,AB)(B,BD)(D,DE) dolžine 3
in maksimalne 2-poti
• (FG,EFG) dolžine 1 ter
• (AC,ABC)(BC,BCD) dolžine 2,
medtem ko so 1-simpleksa BE in DF ter 0-simpleks E kritični.
b b
b
b
b
b
b
A B
C
E
D
G
F
Slika 13. Diskretno vektorsko polje (primer 15).
Iz povedanega sledi, da gradientna polja diskretnih Morsovih funkcij
nimajo zank, tj. poti iz puščic, ki bi se po nekaj korakih vrnile na začetek, saj
vrednosti vzdolž poti strogo padajo in torej začetek poti nikoli ne sovpada
s koncem. Da se tudi pokazati (glej izrek 6.19 v [3]), da je vsako vektorsko
polje, ki nima zank, gradientno polje kakšne diskretne Morsove funkcije (a
očitno ne ene same, saj lahko vrednosti transliramo ali pa jim dodamo šum).
214 Obzornik mat. fiz. 65 (2018) 6
Simplicialni kompleksi in diskretna Morsova teorija
Gradientna polja diskretnih Morsovih funkcij na simplicialnih komple-
ksih se obnašajo podobno kot gradientna polja gladkih Morsovih funkcij na
gladkih mnogoterostih. V obeh primerih govorimo o gradientnih poteh, pa-
dajočih diskih ter kraǰsanjih kritičnih simpleksov in v obeh primerih lahko
iz kritičnih simpleksov izluščimo informacijo o homologiji prostora. Robin
Forman je bil torej pri iskanju diskretne verzije znane zvezne teorije nadvse
uspešen.
Več informacij o Morsovi teoriji lahko bralec najde v knjigi Kevina Knud-
sona [3], ki bralca v prvi polovici seznani z gladko Morsovo teorijo, v drugi
pa vsebuje poleg diskretne teorije tudi poglavji o algoritmih in aplikacijah.
Kot smo že omenili, lahko z uporabo diskretne Morsove teorije določimo
homotopski tip kompleksov Cn iz primera 9. Z relativno preprostim premi-
slekom lahko vidimo, da je prostor Cn homotopsko ekvivalenten šopu (n−1)!
kopij sfere Sn−3. Prostor C4 s slike 10 je torej homotopsko ekvivalenten pro-
storu, ki ga dobimo, če 6 krožnic S1 zlepimo v eni točki. Podrobnosti lahko
zainteresirani bralec najde v Formanovem članku [2], še posebej lepo pa so
razložene v že omenjenem poglavju o aplikacijah v Knudsonovi knjigi [3].
Mi pa končajmo z nalogama za preverjanje razumevanja.
Naloga 3. Katere od funkcij s slike 14 so Morsove? Za tiste, ki so, narǐsi
pripadajoče diskretno vektorsko polje.
b b
b
b
4 4
2
0
1
3 3
5
6
b b
b
7 8
5
6
4 7
b
b
b
b
b
6 3
7 3
1
8
6
5
54
2
2
Slika 14. Katere od zgornjih funkcij so Morsove (naloga 3)?
Naloga 4. Poǐsči še kakšno diskretno Morsovo funkcijo, ki je Morsova funk-
cija diskretnega vektorskega polja s slike 13. Poskusi najti kakšno, ki je ne
dobǐs iz dane s prǐstevanjem konstante.
201–217 215
Aleksandra Franc
Rešitve nalog
Rešitev naloge 1. Za vsak podkompleks bomo našteli vse simplekse, ki
jih vsebuje:
cl(B) = {B},
cl(BD) = {B,D,BD},
cl(BDF ) = {B,D, F,BD,BF,DF,BDF},
st(B) = {B,AB,BC,BD,BF,ABF,BCD,BDF},
st(BD) = {BD,BCD,BDF},
st(BDF ) = {BDF},
lk(B) = {A,C,D, F,AF,CD,DF},
lk(BD) = {C,F},
lk(BDF ) = {}.
Rešitev naloge 2. Baricentrična subdivizija ravninske triangulacije ima
tri vrste oglǐsč. Prva so bila vsebovana že v originalnem simplicialnem kom-
pleksu. Druga so sredǐsča daljic iz originalnega simplicialnega kompleksa in
tretja so sredǐsča trikotnikov iz originalnega simplicialnega kompleksa. Če
vsako od teh treh skupin pobarvamo z drugo barvo, dobimo iskano barvanje,
v katerem ni sosedov istih barv.
Za drugi del opazimo, da vsak trikotnik razpade na 6 manǰsih trikotni-
kov, ki jih očitno lahko pobarvamo izmenično z dvema barvama, belo in
črno. Potrebno se je le še prepričati, da lahko za vsak trikotnik izberemo
eno od obeh možnih izmeničnih barvanj malih trikotnikov tako, da je uskla-
jeno s sosednjimi trikotniki. To najlažje naredimo tako, da vse trikotnike v
prvotnem simplicialnem kompleksu orientiramo v pozitivni smeri (naspro-
tni vrtenju urnega kazalca). Orientacija na notranjosti trikotnika določi
tudi orientacijo na njegovem robu, pri čemer je vsak rob, ki pripada dvema
trikotnikoma, v enem trikotniku orientiran v eno smer, v drugem pa ravno
obratno. Po subdiviziji vsak tak rob razpade na dve polovici in v vsakem od
trikotnikov, ki se v tem robu stikata, mu pripadata dva mala trikotnika. Če
pobarvamo te male trikotnike tako, da je glede na podedovano orientacijo
216 Obzornik mat. fiz. 65 (2018) 6
Simplicialni kompleksi in diskretna Morsova teorija
prvi mali trikotnik pobarvan belo in drugi črno, potem bo vsak mali triko-
tnik iz sosednjega trikotnika pobarvan ravno obratno (črni bo imel belega
soseda, beli pa črnega). Tako barvanje bo zadoščalo pogojem naloge.
Rešitev naloge 3. Prva in tretja funkcija sta Morsovi, druga pa ni, ker
ima npr. 0-simpleks z vrednostjo 8 vǐsjo vrednost kot 1-simpleksa, ki jima
pripada (torej imamo dve izjemi namesto največ ene).
Rešitev naloge 4. En možen nabor vrednosti funkcije f je podan v spo-
dnji tabeli.
A B C D E F G AB AC BC BD BE
8 6 8 4 1 5 3 7 9 7 5 7
CD DE DF EF EG FG ABC BCD EFG
7 3 6 4 2 7 8 6 6
LITERATURA
[1] R. Forman, Morse theory for cell complexes, Advances in Mathematics 184 (1998),
90–145.
[2] R. Forman, A User’s Guide to Discrete Morse Theory, Sém. Lothar. Combin. 48
(2002), Art. B48c, 1–35 (electronic) MR 1939695.
[3] K. P. Knudson, Morse Theory: smooth and discrete, World Scientific Publishing Co.
Pte. Ltd., Singapore, 2015.
[4] M. Morse, The foundations of a theory in the calculus of variations in the large,
Trans. Amer. Math. Soc. 30 (1928), 213–274.
[5] M. Morse, The Calculus of Variations in the Large, American Mathematical Society
Colloquium Publication 18, New York, 1934.
http://www.dmfa-zaloznistvo.si/
201–217 217