Граф Риба

Граф Риба функции высоты на торе. Критическим уровням функции соответствуют вершины графа, связной компоненте неособого уровня — точка на ребре. Ориентация графа определяется направлением роста функции.

В теории графов, граф Риба некоторой функции описывает связность поверхностей уровня этой функции. Был введен Жоржем Рибом

Определение

Рассмотрим непрерывную функцию, заданную на компактном многообразии, $f:M\to R$. Прообраз точки $y\in R$ является поверхностью уровня функции $f^{-1}(y)\subset M$. Две точки $x,x'\in M$ называются эквивалентными, $x\!\sim x'$, если они принадлежат одной компоненте связности поверхности уровня $f^{-1}(y)$.

Граф Риба функции $f$ — это факторпространство многообразия $M$ по такому отношению эквивалентности, $G=M/\!\sim$. Вершинами графа являются компоненты связности критических уровней функции. Ориентация графа $G$ определяется направлением градиента функции $f$.

Свойства

Следующие свойства графа Риба были доказаны в его основополагающей работе:

Пусть на компактном $n$-мерном многообразии класса гладкости $C^{2}$ задана функция Морса f, все критические точки которой соответствуют разным критическим значениям функции. Множество таких функций открыто и плотно в пространстве всех функций. Обозначим $\Gamma$ граф Риба этой функции. Тогда:

• Вершинам степени 1 графа $\Gamma$ в точности соответствуют критические точки функции f индекса 0 и n.
• Если $n\geq 3$, вершина графа, соответствующая критическому уровню функции f, который содержит критическую точку индекса 1 и n-1, может иметь степень 2 или 3.
• Если $n\,=2$, вершины графа, соответствующие критическим точкам индекса 1, могут иметь степень 2, 3 или 4.
• Степень вершины графа, соответствующей критическому уровню функции f, который содержит критическую точку индекса, отличного от 0, 1, n-1 и n, всегда равна 2.

Эти свойства графа влекут любопытное свойство функций Морса, доказанное там же:

• Обозначим через $\Omega _{k}$ множество критических точек функции индекса k и n-k. Если $n\geq 3$, то $|\Omega _{0}|\leq |\Omega _{1}|+2$.

Применение

Графы Риба используются в математике при изучении

• топологической классификации функций Морса
• гамильтоновых систем

Графы Риба и, в особенности, ациклические графы Риба, называемые контурными деревьями, находят широкое применение в компьютерных приложениях:

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