При изучении заданного класса графов, допускающих понятие размерности, т. е. меры их количества (часто под размерностью графа понимается число его вершин, разумеется, есть и другие подходы), естественно возникают вопросы асимптотического характера. При асимптотическом исследовании класса Ω_n графов размерности n особое внимание привлекает тематика вокруг следующих трех вопросов. Первый - вычисление асимптотически точного значения числа таких графов (или получение его хороших оценок). Это позволяет с установленной точностью достаточно просто подсчитать, как правило, трудно вычислимое число Ω_n. Второй вопрос - выделение или построение подкласса типичных графов Ω_n^* ⊆ Ω_n для заданного класса Ω_n. И третий - изучение общих, типичных свойств (справедливых для почти всех) рассматриваемых графов. Такой подход существенно помогает понять строение графов всего класса, особенно при большом числе вершин. В докладе обсуждается обозначенная тематика для класса n-вершинных графов заданного диаметра. Изучаются типичные метрические свойства этих графов, связанные с разнообразием метрических шаров, радиусом графа, диаметральными и центральными вершинами, центром графа и его спектром (множеством мощностей центров графов) и т.п., а также классы возникающих здесь типичных графов.

теория графов

Федоряева Татьяна Ивановна,  orcid.org/0000-0002-5246-0522,  Институт математики им. С. Л. Соболева Сибирского отделения РАН