Оценки экстремальных значений основных метрических характеристик псевдосимметрических графов

• Автор: Князев, Александр Викторович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 203 с. : ил

ОГЛАВЛЕНИЕ:

ВВЕДЕНИЕ

ЧАСТЬ I. ОБЗОР ЛИТЕРАТУРЫ И ОСНОВНЫЕ РЕЗУЛЬТАТЫ

РАБОТЫ

ЧАСТЬ И. ДИАМЕТРЫ ПСЕВДОСИММЕТРИЧЕСКИХ ГРАФОВ

§2.1. Основные леммы

§ 2.2. Верхние оценки диаметров псевдосимметрических

графов
§ 2.3. Верхние оценки диаметров дихотомических графов 72 ЧАСТЬ III. ЭКСПОНЕНТЫ ПСЕВДОСИММЕТРИЧЕСКИХ
ГРАФОВ
§ 3.1. Известный метод построения верхних оценок примитивных графов
§ 3.2. Дихотомические графы с максимальным обхватом 1
§ 3.3. Дихотомические графы собхватом на единицу
меньше максимального
§ 3.4. Верхние оценки экспонентов дихотомических
графов
§ 3.5. Верхние оценки экспонентов псевдосимметрических графов
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ.
Представленная диссертационная работа посвящена изучению верхних оценок диаметров и экспонентов псевдосимметрических (полустепени исхода и захода каждой вершины совпадают) ориентированных сильно связных графов без параллельных дуг.
Псевдосимметрические графы являются “переходным'’ множеством между множеством всех неориентированных (симметрических) графов и множеством всех ориентированных графов, моделируют многие реальные процессы и объекты и активно используются в теории управления (в частности, при моделировании процессов переработки информации), в теоретической криптографии (при моделировании узлов и блоков устройств шифрования), в теории конечных автоматов (любой регулярный автомат моделируется псевдосимметрическим регулярным графом) - см., например, /12, 13, 15, 16, 18, 20, 21/, и др.
Важнейшими метрическими характеристиками графов являются диаметр (максимальный из всех минимальных путей между всеми различными парами вершин графа) и экспонент (минимальная степень, в которой матрица смежности графа
либо,

?4() + 1) + ^а+2) < Х(
?4(]> < ^(]+4)
я.о+1> < ^о+2) + х. о+з)

Пусть, например, выполнена первая система неравенств (для второй все доказывается аналогично). Сложив второе и третье неравенства, получаем
Х{ ш + Х{ а+1) > Х{ и+2) + Х[ ('+3) + Х{ (1+4).
Так как для Г справедлива лемма 2.2., из последнего неравенства непосредственно получаем справедливость (2.3).
2. Хотя бы одна из четверок чисел (пусть это, например,
Х{{]), Х(('+1) + ^(]+2), ^('+3 ^°+4))
такова, что (2.4) для нее не выполняется. То есть
Ху Ш • (Х{ 0+1) + Х{ а+2)) + Х{ а+3) (]+4) <