Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Князев, Александр Викторович
01.01.09
Докторская
2002
Москва
203 с. : ил
Стоимость:
499 руб.
ОГЛАВЛЕНИЕ:
ВВЕДЕНИЕ
ЧАСТЬ 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) <
Название работы | Автор | Дата защиты |
---|---|---|
О покрытиях множеств в евклидовых пространствах | Филимонов, Владислав Павлович | 2013 |
О конечной порожденности предполных классов монотонных функций многозначной логики | Дудакова, Ольга Сергеевна | 2007 |
О несуществовании двоичных кодов при различных условиях равномерной распределенности | Ярыкина, Мария Сергеевна | 2008 |