RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., 2017, том 24, номер 2, страницы 68–86 (Mi da870)  

Асимптотическое приближение числа $n$-вершинных графов заданного диаметра

Т. И. Федоряеваab

a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

Аннотация: Доказано, что при фиксированном $k\geq3$ асимптотически равномощны следующие классы помеченных $n$-вершинных графов: графы диаметра $k$, связные графы диаметра не менее $k$ и графы (не обязательно связные), имеющие кратчайшую цепь длины не менее $k$. Получено асимптотически точное приближение числа таких $n$-вершинных графов, и найдена явная оценка погрешности при этом приближении. Тем самым улучшены оценки для асимптотического приближения числа $n$-вершинных графов фиксированного диаметра $k$, которое ранее получили Фюреди и Ким. Установлено, что почти все графы диаметра $k$ имеют единственную пару диаметральных вершин, но почти все графы диаметра 2 имеют более одной пары таких вершин. Ил. 3, библиогр. 9.

Ключевые слова: граф, помеченный граф, кратчайшая цепь, диаметр графа, число графов, типичный граф.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-01-00949
Российская академия наук - Федеральное агентство научных организаций 0314-2015-0011
Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проект 17–01–00949) и программы РАН (проект 0314–2015–0011).


DOI: https://doi.org/10.17377/daio.2017.24.534

Полный текст: PDF файл (363 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2017, 11:2, 204–214

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.1+519.175
Статья поступила: 29.03.2016
Переработанный вариант: 04.07.2016

Образец цитирования: Т. И. Федоряева, “Асимптотическое приближение числа $n$-вершинных графов заданного диаметра”, Дискретн. анализ и исслед. опер., 24:2 (2017), 68–86; J. Appl. Industr. Math., 11:2 (2017), 204–214

Цитирование в формате AMSBIB
\RBibitem{Fed17}
\by Т.~И.~Федоряева
\paper Асимптотическое приближение числа $n$-вершинных графов заданного диаметра
\jour Дискретн. анализ и исслед. опер.
\yr 2017
\vol 24
\issue 2
\pages 68--86
\mathnet{http://mi.mathnet.ru/da870}
\crossref{https://doi.org/10.17377/daio.2017.24.534}
\elib{http://elibrary.ru/item.asp?id=29275515}
\transl
\jour J. Appl. Industr. Math.
\yr 2017
\vol 11
\issue 2
\pages 204--214
\crossref{https://doi.org/10.1134/S1990478917020065}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85019662822}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da870
  • http://mi.mathnet.ru/rus/da/v24/i2/p68

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:184
    Полный текст:13
    Литература:17
    Первая стр.:14
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019