Discrete Morse theory is a combinatorial adaptation of Morse theory developed by Robin Forman. The theory has various practical applications in diverse fields of applied mathematics and computer science, such as configuration spaces,^[1] homology computation,^[2][3] denoising,^[4] mesh compression,^[5] and topological data analysis.^[6]

Notation regarding CW complexes

Let ${\displaystyle X}$ be a CW complex and denote by ${\displaystyle {\mathcal {X}}}$ its set of cells. Define the incidence function ${\displaystyle \kappa \colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {Z} }$ in the following way: given two cells ${\displaystyle \sigma }$ and ${\displaystyle \tau }$ in ${\displaystyle {\mathcal {X}}}$, let ${\displaystyle \kappa (\sigma ,~\tau )}$ be the degree of the attaching map from the boundary of ${\displaystyle \sigma }$ to ${\displaystyle \tau }$. The boundary operator is the endomorphism ${\displaystyle \partial }$ of the free abelian group generated by ${\displaystyle {\mathcal {X}}}$ defined by

${\displaystyle \partial (\sigma )=\sum _{\tau \in {\mathcal {X}}}\kappa (\sigma ,\tau )\tau .}$

It is a defining property of boundary operators that ${\displaystyle \partial \circ \partial \equiv 0}$. In more axiomatic definitions^[7] one can find the requirement that ${\displaystyle \forall \sigma ,\tau ^{\prime }\in {\mathcal {X}}}$

${\displaystyle \sum _{\tau \in {\mathcal {X}}}\kappa (\sigma ,\tau )\kappa (\tau ,\tau ^{\prime })=0}$

which is a consequence of the above definition of the boundary operator and the requirement that ${\displaystyle \partial \circ \partial \equiv 0}$.

Discrete Morse functions

A real-valued function ${\displaystyle \mu \colon {\mathcal {X}}\to \mathbb {R} }$ is a discrete Morse function if it satisfies the following two properties:

1. For any cell ${\displaystyle \sigma \in {\mathcal {X}}}$, the number of cells ${\displaystyle \tau \in {\mathcal {X}}}$ in the boundary of ${\displaystyle \sigma }$ which satisfy ${\displaystyle \mu (\sigma )\leq \mu (\tau )}$ is at most one.
2. For any cell ${\displaystyle \sigma \in {\mathcal {X}}}$, the number of cells ${\displaystyle \tau \in {\mathcal {X}}}$ containing ${\displaystyle \sigma }$ in their boundary which satisfy ${\displaystyle \mu (\sigma )\geq \mu (\tau )}$ is at most one.

It can be shown^[8] that the cardinalities in the two conditions cannot both be one simultaneously for a fixed cell ${\displaystyle \sigma }$, provided that ${\displaystyle {\mathcal {X}}}$ is a regular CW complex. In this case, each cell ${\displaystyle \sigma \in {\mathcal {X}}}$ can be paired with at most one exceptional cell ${\displaystyle \tau \in {\mathcal {X}}}$: either a boundary cell with larger ${\displaystyle \mu }$ value, or a co-boundary cell with smaller ${\displaystyle \mu }$ value. The cells which have no pairs, i.e., whose function values are strictly higher than their boundary cells and strictly lower than their co-boundary cells are called critical cells. Thus, a discrete Morse function partitions the CW complex into three distinct cell collections: ${\displaystyle {\mathcal {X}}={\mathcal {A}}\sqcup {\mathcal {K}}\sqcup {\mathcal {Q}}}$, where:

1. ${\displaystyle {\mathcal {A}}}$ denotes the critical cells which are unpaired,
2. ${\displaystyle {\mathcal {K}}}$ denotes cells which are paired with boundary cells, and
3. ${\displaystyle {\mathcal {Q}}}$ denotes cells which are paired with co-boundary cells.

By construction, there is a bijection of sets between ${\displaystyle k}$-dimensional cells in ${\displaystyle {\mathcal {K}}}$ and the ${\displaystyle (k-1)}$-dimensional cells in ${\displaystyle {\mathcal {Q}}}$, which can be denoted by ${\displaystyle p^{k}\colon {\mathcal {K}}^{k}\to {\mathcal {Q}}^{k-1}}$ for each natural number ${\displaystyle k}$. It is an additional technical requirement that for each ${\displaystyle K\in {\mathcal {K}}^{k}}$, the degree of the attaching map from the boundary of ${\displaystyle K}$ to its paired cell ${\displaystyle p^{k}(K)\in {\mathcal {Q}}}$ is a unit in the underlying ring of ${\displaystyle {\mathcal {X}}}$. For instance, over the integers ${\displaystyle \mathbb {Z} }$, the only allowed values are ${\displaystyle \pm 1}$. This technical requirement is guaranteed, for instance, when one assumes that ${\displaystyle {\mathcal {X}}}$ is a regular CW complex over ${\displaystyle \mathbb {Z} }$.

The fundamental result of discrete Morse theory establishes that the CW complex ${\displaystyle {\mathcal {X}}}$ is isomorphic on the level of homology to a new complex ${\displaystyle {\mathcal {A}}}$ consisting of only the critical cells. The paired cells in ${\displaystyle {\mathcal {K}}}$ and ${\displaystyle {\mathcal {Q}}}$ describe gradient paths between adjacent critical cells which can be used to obtain the boundary operator on ${\displaystyle \mathcal{A}}$Zdroj:https://en.wikipedia.org?pojem=Discrete_Morse_theory
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.