В теории графов, граф Риба некоторой функции описывает связность поверхностей уровня этой функции. Был введен Жоржем Рибом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.
Определение Рассмотрим непрерывную функцию, заданную на компактном многообразии, . Прообраз точки является поверхностью уровня функции . Две точки называются эквивалентными, , если они принадлежат одной компоненте связности поверхности уровня .
Граф Риба функции — это факторпространство многообразия по такому отношению эквивалентности, . Вершинами графа являются компоненты связности критических уровней функции. Ориентация графа определяется направлением градиента функции .
Свойства Следующие свойства графа Риба были доказаны в его основополагающей работе:
Пусть на компактном -мерном многообразии класса гладкости задана функция Морса f, все критические точки которой соответствуют разным критическим значениям функции. Множество таких функций открыто и плотно в пространстве всех функций. Обозначим граф Риба этой функции. Тогда:
Вершинам степени 1 графа в точности соответствуют критические точки функции f индекса 0 и n. Если , вершина графа, соответствующая критическому уровню функции f, который содержит критическую точку индекса 1 и n-1, может иметь степень 2 или 3. Если , вершины графа, соответствующие критическим точкам индекса 1, могут иметь степень 2, 3 или 4. Степень вершины графа, соответствующей критическому уровню функции f, который содержит критическую точку индекса, отличного от 0, 1, n-1 и n, всегда равна 2.
Эти свойства графа влекут любопытное свойство функций Морса, доказанное там же:
Обозначим через множество критических точек функции индекса k и n-k. Если , то .
Применение Графы Риба используются в математике при изучении
топологической классификации функций Морса Шарко В. В. Гладкая и топологическая эквивалентность функций на поверхностях. // Український математичний журнал. 2003. Т. 55. № 5. С. 687—700. гамильтоновых систем А. В. Болсинов, А. Т. Фоменко, Введение в топологию интегрируемых гамильтоновых систем, Наука, М., 1997.
Графы Риба и, в особенности, ациклические графы Риба, называемые контурными деревьями, находят широкое применение в компьютерных приложениях: в компьютерном дизайне и геометрическом моделировании, в геометрических моделях структуры данных и методах поиска в базах данных в системах автоматизации проектных работ.
Примечания
Категория:Графы, имеющие собственные названия Категория:Топология