О разнообразии шаров графа заданного диаметра

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Прикладная теория кодирования, автоматов и графов
127
ЛИТЕРАТУРА
1. Sperner E. Ein Satz uber Untermengen einer endlichen Menge // Math. Zeitschrift. 1928. B. 27. No. 1. S. 544−548.
2. Богомолов А. Д., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
3. Салий В. Н. Шпернерово свойство для многоугольных графов // Прикладная дискретная математика. Приложение. 2014. № 7. С. 135−137.
4. Новокшонова Е. Н. Шпернерово свойство для линейных графов // Компьютерные науки и информационные технологии: Материалы Междунар. науч. конф. Саратов: Издат. Центр «Наука», 2014. С. 230−231.
5. Atkinson M. D. and Ng D. T. N. On the width of an orientation of a tree // Order. 1988. V. 5. No. 1. P. 33−43.
6. Харари Ф. Теория графов. М.: Мир, 1973.
УДК 519. 1+519. 173 DOI 10. 17 223/2226308X/8/48
О РАЗНООБРАЗИИ ШАРОВ ГРАФА ЗАДАННОГО ДИАМЕТРА1
Т. И. Федоряева
Изучаются векторы разнообразия шаров (i-я компонента вектора равна числу различных шаров радиуса i) для обыкновенных связных графов в асимптотике. Исследовано асимптотическое поведение числа графов с разнообразием шаров специального вида, в частности с локальным (полным) разнообразием шаров. Для типичного графа заданного диаметра получено описание строения разнообразия шаров больших радиусов.
Ключевые слова: граф, шар, радиус шара, вектор разнообразия шаров.
В работе изучается разнообразие шаров обыкновенного связного графа в асимптотике. Пусть Ti (G) — число всех различных шаров радиуса i в метрическом пространстве графа G с обычным расстоянием между вершинами, т. е. длиной кратчайшей цепи, соединяющей эти вершины.
Определение 1 [1]. Вектор т (G) = (t0(G), ti (G),…, Td (G)), где d = d (G) — диаметр графа G, называется вектором разнообразия шаров графа G.
Например, вектор разнообразия шаров простой цепи длины d, как показано в [1], равен А^ = (ДО, А?,…, А?), где
(d + 1, если 0 ^ i ^ |_d/2j ,
А? = & lt-j 2(d — i) + 1, если [d/2j & lt- i & lt- d, У 1, если i ^ d.
Определение 2 [2]. Граф G обладает локальным t-разнообразием шаров, если |V (G)| = t0(G) = Ti (G) = … = Tt (G), 0 ^ t & lt- d (G). Граф G с локальным t-разнообра-зием шаров при t = d (G) — 1 называется графом полного разнообразия шаров.
Таким образом, вектор разнообразия шаров графа G с полным разнообразием шаров имеет вид (|V (G)|,…, |V (G)|, 1). В [1] показано, что класс деревьев с полным разнообразием шаров является бедным, так как состоит лишь из звезды K1/n, и получена
1 Работа поддержана грантом РФФИ, проект № 14−01−507.
128
Прикладная дискретная математика. Приложение
характеризация деревьев с локальным разнообразием шаров. Наименьший порядок графов диаметра d с локальным ?-разнообразием шаров (полным разнообразием шаров) найден в [3], а в [4] все такие графы наименьшего порядка явно описаны с точностью до изоморфизма и вычислены их векторы разнообразия шаров. В [3] установлены все возможные значения параметров n, d и t, при которых существует n-вершинный граф диаметра d с полным разнообразием шаров (локальным ?-разнообразием шаров). В [5] изучен вопрос единственности n-вершинного графа диаметра d с полным разнообразием шаров. Только при n = 2d & gt- 6 или d ^ 1 существует единственный такой граф — 2d-вершинный цикл при d & gt- 3 и полный граф Kn при d ^ 1.
В настоящей работе исследуется асимптотическое поведение числа графов с локальным (полным) разнообразием шаров и строение вектора разнообразия шаров графа заданного диаметра. Хорошо известен следующий результат.
Теорема 1 [6]. Почти все графы являются графами диаметра 2.
Более того, справедлива следующая
Теорема 2 [2]. Почти все графы являются графами диаметра 2 с полным разнообразием шаров.
Непосредственно из теорем 1 и 2 вытекает
Теорема 3. Граф диаметра 2 является графом полного разнообразия шаров. Основным результатом работы является следующая
Теорема 4. Пусть d ^ 3. Тогда в графе диаметра d число различных шаров радиуса i равно Ad для всех i ^ d/2.
Следствие 1. Пусть d ^ 3 и t ^ d/2. Тогда граф диаметра d не обладает локальным ?-разнообразием шаров и, в частности, не является графом полного разнообразия шаров.
ЛИТЕРАТУРА
1. Федоряева Т. И. Разнообразие шаров в метрических пространствах деревьев // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12. № 3. С. 74−84.
2. Евдокимов А. А. Локально изометрические вложения графов и свойство продолжения метрики // Сиб. журн. исслед. операций. 1994. Т. 1. № 1. С. 5−12.
3. Федоряева Т. И. Векторы разнообразия шаров для графов и оценки их компонент // Дискрет. анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 2. С. 47−67.
4. Федоряева Т. И. О графах с заданными диаметром, числом вершин и локальным разнообразием шаров // Дискрет. анализ и исслед. операций. 2010. Т. 17. № 1. С. 65−74.
5. Федоряева Т. И. Мажоранты и миноранты класса графов с фиксированными диаметром и числом вершин // Дискрет. анализ и исслед. операций. 2013. Т. 20. № 1. С. 58−76.
6. Bollabas B. Graph Theory. Springer Verlag, 1979.

ПоказатьСвернуть
Заполнить форму текущей работой