Граф Риба (Ijgs JnQg)

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

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

Определение

[править | править код]

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

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

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

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

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

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

  • Обозначим через множество критических точек функции индекса k и n-k. Если , то .

Применение

[править | править код]

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

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

Примечания

[править | править код]
  1. 1 2 3 G. Reeb, Sur les points singuliers d’une forme de Pfaff complétement intégrable ou d’une fonction numérique. — C.R.A.S. Paris 222, 1946, pp. 847—849.[1] Архивная копия от 9 марта 2016 на Wayback Machine
  2. Шарко В. В. Гладкая и топологическая эквивалентность функций на поверхностях. // Український математичний журнал. 2003. Т. 55. № 5. С. 687—700.
  3. А. В. Болсинов, А. Т. Фоменко, Введение в топологию интегрируемых гамильтоновых систем, Наука, М., 1997.