Оценки экстремальных значений основных метрических характеристик псевдосимметрических графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

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

РАБОТЫ

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

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

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

§ 2.3. Верхние оценки диаметров дихотомических графов 72 ЧАСТЬ III. ЭКСПОНЕНТЫ ПСЕВДОСИММЕТРИЧЕСКИХ

ГРАФОВ.

§ 3.1. Известный метод построения верхних оценок примитивных графов.

§ 3.2. Дихотомические графы с максимальным обхватом

§ 3.3. Дихотомические графы собхватом на единицу меньше максимального.

§ 3.4. Верхние оценки экспонентов дихотомических графов.

§ 3.5. Верхние оценки экспонентов псевдосимметрических графов.

Представленная диссертационная работа посвящена изучению верхних оценок диаметров и экспонентов псевдосимметрических (полустепени исхода и захода каждой вершины совпадают) ориентированных сильно связных графов без параллельных дуг.

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

Важнейшими метрическими характеристиками графов являются диаметр (максимальный из всех минимальных путей между всеми различными парами вершин графа) и экспонент (минимальная степень, в которой матрица смежности графа становится строго положительной). Верхняя и нижняя оценки диаметра и экспонента в изучаемом множестве графов могут при этом интерпретироваться в соответствующей прикладной задаче как "наилучший" и "наихудший" случаи.

Получение нижних оценок диаметров и экспонентов на множестве псевдосимметрических графов является несложной задачей. Нетрудно видеть, что диаметр и экспонент псевдосимметрического графа с п вершинами и минимальной полустепенью исхода и захода не меньше к оцениваются снизу величиной log к п. Более того, из работы А.Д.Коршунова /14/ следует, что диаметры D почти всех регулярных псевдосимметрических графов (полустепени исхода и захода каждой из п вершин совпадают и равны к) удовлетворяют соотношению log к n < D < 10 log к п.

В то же время задачи получения верхних оценок диаметров и экспонентов являются весьма нетривиальными и имеют длительную историю.

Ранее содержательные верхние оценки диаметров удалось построить с одной стороны для множества неориентированных (симметрических) графов - в зависимости от числа и минимальной валентности вершин - Дж. Мун в /53/, 1965 г., а с другой стороны для различных графов Кэли - в основном, для определенных групп подстановок и систем образующих - в первую очередь отметим работы М.М. Глухова, А.Ю. Зубова и Б.А. Погорелова /20, 21/. В диссертации эта задача решается на множестве всех псевдосимметрических графов с получением оценок, определяемых числом вершин, наименьшим значением полустепеней исхода и захода вершин и длиной наименьшего контура - обхвата графа. Наиболее точные оценки при произвольном значении обхвата получены на множестве дихотомических графов (в каждую вершину графа входит и из каждой вершины выходит в точности по две дуги) - этот класс графов в точности соответствует классу бинарных автономных регулярных автоматов.

Исследование верхних оценок экспонентов неотрицательных матриц (ориентированных графов) было начато в 1912 г. Г.Фробениусом /37/. В последовавших работах Г.Виландта /66/, А.Далмейджа и Н.Мендельсона /35/, Джиа-Ю Шао /57, 58/ и др. задача описания всех п-вершинных ориентированных графов с максимально возможными (в зависимости от величины обхвата) экспонентами была полностью решена. В частности, было доказано, что максимальным экспонентом п - 2п +2 обладает граф с максимальным обхватом п-1. В диссертации исследуются верхние оценки экспонентов на множестве дихотомических графов и на множестве псевдосимметрических графов с малыми обхватами. В частности, в диссертации описаны (с точностью до подстановочного подобия) все n-вершинные дихотомические графы с максимальным обхватом ]п/2[ и доказано что их экспоненты не превосходят п-1. Также удалось доказать, что на множестве всех п-вершинных дихотомических графов максимальное значение экспонента достигается не на множестве графов с максимальным обхватом.

Работа состоит из введения, трех частей, заключения и списка литературы.

В I части сформулированы основные определения, сделан краткий обзор литературы по тематике диссертации и изложены основные результаты работы.

Во II части получены верхние оценки диаметров псевдосимметрических графов с малыми обхватами и дихотомических графов с произвольным обхватом, близкие к достижимым.

В III части с использованием результатов II части получены верхние оценки экспонентов псевдосимметрических графов с малыми обхватами и дихотомических графов с произвольным обхватом.

На защиту выносятся следующие основные результаты.

1. Верхние оценки диаметров псевдосимметрических графов с малыми обхватами, близкие к достижимым.

2. Верхние оценки диаметров дихотомических графов с произвольным обхватом, близкие к достижимым.

3. Классификация всех дихотомических графов с максимальным обхватом (с точностью до подстановочного подобия).

4. Описание структурных особенностей дихотомических графов с нечетным числом вершин с обхватом на единицу меньше максимального.

5. Верхние оценки экспонентов дихотомических графов с произвольным обхватом.

6. Верхние оценки экспонентов псевдосимметрических графов с малыми обхватами.

По теме диссертации опубликованы девять работ /5 - 13/.

Диссертация прошла апробацию в МИ им. В. А. Стеклова РАН, в

ВЦ им. А. А. Дородницына РАН, в ИППИ РАН и в МГУ им. М. В.

Ломоносова. Результаты работы докладывались на ИГ

Всероссийском симпозиуме по прикладной и промышленной математике (г. Ростов-на-Дону, 2002 г., пленарный доклад).

Автор выражает признательность за внимание к работе

А. А. Грушо, А. М. Зубкову, А. С. Кузьмину, В. П. Полесскому,

Ю. В. Прохорову, А. Ф. Ронжину, В. Н. Сачкову и В. Е. Тараканову. 9

Автор пользуется возможностью поблагодарить Ольгу Ломовскую за неоценимую помощь в оформлении работы.

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

Следуя /1/, напомним некоторые определения. В дальнейшем везде, помимо специально оговоренных случаев, под графом Г будем понимать ориентированный граф без параллельных дуг, с множеством вершин

У={1,., п} и множеством Е ориентированных дуг вида (Ч, ]), где [,) е {1,.,п}.

Полустепенью исхода <30С) (захода с1, У)) вершины ] е { 1,.,п} называется число исходящих из неё (входящих в неё) дуг, то есть а0а)=1{У}еЕ}|,

С) =1 {У)еЕ} | .

Определение 1.1. Граф Г называется псевдосимметрическим, если ёоО) = (]) для любой его вершины ]еУ. В случае, когда ёоО) = С)=2 для всех ]еУ, граф Г называется дихотомическим.

Определение 1.2. Граф Г называется сильно связным, если для любой пары его вершин I и ] в Г существует ориентированный путь из 1 в ].

Определение 1.3. Обхватом графа Г называется длина его кратчайшего контура (если таковые существуют).

Любой граф Г однозначно определяется своей матрицей смежности

А (Г)= I I ау || пхп, где ау = 1 тогда и только тогда, когда (¡,]) е Е. Поэтому все определения и результаты могут быть переформулированы на матричном языке. Так, в частности, обхват графа Г есть такое наименьшее натуральное число р, что матрица (А(Г))Р имеет ненулевые элементы на главной диагонали.

Прежде всего, отметим, что верхняя граница изменения параметра р (обхвата графа) на множестве всех п-вершинных псевдосимметрических графов с полустепенями исхода и захода не меньше к исследовалась в работах /24/, /30/, /32/, /56/. В работе /30/ Качетта и Хэгквист сделали предположение, что

12 П

Однако, для к>2 наилучшей в настоящее время является оценка, полученная Нишимурой в работе /56/ р < 304.

Нишимура улучшил оценку Хватала и Шемереди (/32/), существенно использовав технику из их же работы.

Для к=2 (т.е. для множества дихотомических графов) гипотеза, сформулированная в работе /28/ получила свое подтверждение, и Бехзадом в /24/ доказана достижимая верхняя оценка п

Р < где ]а[ - наименьшее целое число, не меньшее а.

Помимо этого, отметим работы /25, 26, 31, 38, 39, 67/ и обзор /27/, в котором приведено значительное количество результатов по изучению длин контуров псевдосимметрических (дирегулярных) графов при больших к (близких к п).

Обозначим через Я(а) множество всех различных подмножеств множества V вершин графа Г мощности а, где

1 < a < n -1. Пусть Q e Rw. Расстоянием p [i, Q] от вершины i до Q называется величина p [i, Q]=min { p (i, jt) I jte Q, t= 1, a, }. где p (i, jt) - длина кратчайшего непустого пути из i в jt в графе Г.

Определение 1.4. a-диаметром сильно связного графа Г называется величина

Da (Г)=шах { р [i,Q] |ieV, QeR(a\ ijeQ}. 1-диаметр называется диаметром и обозначается D(r). Ясно, что

D(H= шах{ p(i,j) I i, j е V,

Определение 1.5. Циклическим диаметром Dc (Г) графа Г называется величина

Dc(r)=max{ p(i,j) | iJeV}

Легко видеть, что имеют место неравенства

D(Г) < D° (Г)< Dc (Г)+1

1.1)

Обозначим через Н (п, к, р) ((О (п, к, р)) класс сильно связных псевдосимметрических графов с п вершинами, каждая из которых имеет не менее к (в точности к) входящих и исходящих дуг, с обхватом не меньше р (в точности р). Ясно, что в (п, к,р)сН(п, к, р).

В §1 второй части доказаны основные леммы, позволяющие в §2 получить верхние оценки диаметров графов из классов Н (п, к, р) при р = 1,2, 3. Идея метода доказательства лемм заключается в разбиении множеств вершин графов на непересекающиеся подмножества и оценивании числа дуг, связывающих между собой вершины этих подмножеств через мощности этих подмножеств.

В §2 второй части получены верхние оценки диаметров графов из Н (п, к, р) при р=1, 2, 3 и исследована их достижимость. В частности, доказано, что для любого графа Г е Н (п, к, р), где п-к >2, к >3, справедливы неравенства п- а - 1-х

3 ^ - (1 - 2х), если п - а - 1 = х (тос1 к) при х = 0,1;

Е>а(Г)< / Гп - а - 2 -|

3 Г J + 1, в противном случае.

П — X

3 —г— - (3 -х), если п - а - 1 = х (тос1 к) при х = 0,1;

Ос(Г)< {

Гп~2-1

3 [ к ] - 1? в противном случае.

1.2)

Здесь [а] - целая часть числа а.

Достижимость этих оценок характеризует следующий результат. Пусть целые неотрицательные числа п, к, I иг таковы, что п - 1к + г, г < к, 1>3, к>3. Тогда существует граф Ге Н (п, к, 1) такой, что

О (Г) = <

3^-3, если г = 0; п - г

3 ~;— - 2, если г > 0. гп - г - а 1

П * 3 I—й—] л

Ясно, что все верхние оценки, полученные в §2, справедливы и для графов из в (п, к, р) при р=1, 2, 3.

Из известных результатов о верхних оценках диаметров графов отметим прежде всего результат работы /53/: пусть п и г -натуральные числа, п -1 > г > 2; б = g (п, г) - наименьшее натуральное число, такое, что если в произвольном п-вершинном неориентированном графе без петель и параллельных ребер степень любой вершины не меньше б, то диаметр не больше г. Тогда при любом г > 3 имеет место э = [пЛ], [(п-1)А], [(п-2)Л] при г = 31 - 4, г = 31 - 3 или г = 31 - 2, соответственно. Также можно отметить тривиальную верхнюю оценку диаметра произвольного п-вершинного графа, равную (п - 1) и достижимую в классе в (п, 1, п) (см./1 /) и работы /14/, /22/, /33/, /38/, /46/, /63/.

Помимо этого, имеется значительное количество работ, посвященных изучению верхних оценок диаметров графов Кэли (длин покрытия групп и полугрупп), см. например, /3/, /4/, /17/, /19/, /20/, /21/, /34/, /36/, /42/, /52/, /65/, (всплеск интереса к диаметрам графов Кэли групп подстановок в 80-ых годах прошлого века связан, по-видимому, с появлением кубика Рубика). Интересно, что, несмотря на специфику графов Кэли, оценка (1.2) является лучшей из известных автору оценкой длины покрытия произвольной группы порядка пек образующими. Эта оценка примерно в три раза хуже наибольшей из известных в настоящее время длины покрытия циклической группы порядка п, заданной к образующими и равной ]п/к[.

В §3 второй части получены верхние оценки диаметров дихотомических графов. С учетом

17 р£ Ж.

1.3) см. /24/) в §3 доказано, что для любого графа Гев (п, 2, р), где 2<р< ]п/2[, справедливо неравенство

Ва(Г)<П2р"а(р+1) (1.4)

Достижимость последней оценки характеризуется следующим утверждением. Пусть целые неотрицательные числа п, р, к и г таковы, что п - 5 = (2р - 1) г + г, где р > 3, I >3, 0 < г < 2р -1. Тогда существует граф Гев (п, 2, р), такой, что г + 1 р + 1)1+ 2 5 если г - нечетное; г + 2

Г) = В (Г) = < (р + 1) г + —2— » если г ~ четное и г Ф 2р - 2; р + \) X + ^ , если г = 2р - 2;

Гп-5-г-а ч г1 О« (Г)> [-2^1- (Р+ 1) + 2-1'

Напомним еще ряд определений.

Определение 1.6. Граф Г называется примитивным, если для любой пары его вершин 1, '} е V существует путь из 1 в } длины у. Наименьшее у с таким свойством называется экспонентом графа Г и обозначается у (Г).

Определение 1.7. матрица А размера пхп с неотрицательными элементами называется примитивной, если существует такое число V у, что А'>0. Наименьшее у с таким свойством называется экспонентом матрицы А и обозначается у (А).

Легко видеть, что матрица смежности А (Г) примитивного графа Г примитивна, и у (Г) = у(А).

Известно, что граф Г примитивен тогда и только тогда, когда он сильно связен и длины его контуров взаимно просты (см. /18/).

Приведем основные результаты, касающиеся оценок экспонентов графов и неотрицательных матриц. По-видимому впервые оценка экспонента произвольной примитивной матрицы А размера пхп была получена Фробениусом (см. /37/): у (А) < 2п2 - 2п.

Эта оценка была улучшена Виландтом, который привел без доказательства следующий результат (см /66/): у (А) < п2 - 2п +2

Эта оценка достижима в классе всех неотрицательных матриц и достигается для матрицы

О 1 О О 0 1 о4 о

А =

000

1 1 о о

Там же Виландт показал, что у(А)<п-1, (1.5) если А=|| а^ || такова, что а^ = 1, для некоторого [ е {1, ., п}.

В этом случае соответствующий (0,1) - матрице А граф имеет петлю.

Далмейдж и Мендельсон (см./35/) доказали, что оценка у (Г) < п +р (п-2) (1.6) справедлива для произвольного п-вершинного примитивного графа Г с обхватом р.

Витек и Левин (см. /50, 64/) продолжали исследования примитивных графов и, в частности, Витеку в /64/ удалось серьезно продвинуться в построении оценок индекса Фробениуса -Шура /29/ (для множества различных натуральных чисел {аь . , ат} - такого, что НОД (аь . , ат) = 1 определим индекс Фробениуса - Шура ф (а^ . , ат), как наименьшее натуральное б такое, что любое натуральное д > б может быть представлено в виде линейной комбинации ц = с^ + с2 а2 + . + ст ат , где с1? [ = 1, т - целые, неотрицательные числа) при числе переменных т больше двух.

Бруалди (см., например /29/) поставил задачу описания примитивных графов с максимальным экспонентом, и Джиа-Ю Шао (см. /57/) описал (с точностью до изоморфизма) все п-вершинные графы с обхватом р > 2, для которых оценка (1.6.) достижима. В частности, в /57/ доказано, что необходимым условием достижимости (1.6) является выполнение НОД (р, п) = 1.

Таким образом, при простом п оценка (1.6) достижима при любом значении р > 2 и линейно растет по этому параметру. С другой стороны, отсюда же следует, что в классе всех п-вершинных примитивных графов максимальным значением экспонента п2-2п+2 обладает граф с максимальным обхватом п-1.

В работе /58/ Джиа-Ю Шао, Вей-Кван Донг и Чун-Фей Донг описали (с точностью до изоморфизма) все примитивные графы с п вершинами, с обхватом рис максимальным экспонентом при НОД (р, п)>1. В частности доказано, что в этом случае максимальное значение экспонента равно п + р (1-2) + 1, если п = кр и р-2 не делится на к-1; и равно п + р (1-2) , если п не делится на р, либо п = кр и р-2 делится на к-1 (во всех случаях I = шах {г - натуральное | р < г < п, НОД (р, г) = 1 }.

Исследованием множества п-вершинных примитивных графов занимались также Варга /40/, Кёркланд /23, 43 - 45/, Шен Джиан /60, 61/, Ньюфелд /54, 55/, Хуанг /41/ и Лю Бо Лиан /51/.

Отметим также цикл работ Марии Квашник (/47-49/), посвященных исследованию экспонентов (индексов примитивности) дизъюнкции и композиции двух ориентированных графов, и работы /28/, /59/, посвященные обобщению понятия экспонента для непримитивных графов.

Обозначим через Р(п, к, р) класс примитивных графов из 0(п, к, р) с обхватом в точности р. Ясно, что справедлива цепочка включений

Р(п, к, р) с 0(п, к, р) с Н(п, к, р).

В третьей части получены верхние оценки экспонентов для графов из классов Р (п, 2, р) при 3 < р < ]п/2[ и Р (п, к, р) при р = 1, 2.

В §1 третьей части изложена основная идея (/35/, /57/, /58/) метода построения верхних оценок экспонентов примитивных графов в классе всех п-вершинных примитивных графов. Приведены формулировки основных теорем из /57/, /58/ и работы Витека /64/, результаты которой существенно использовались Джиа-Ю Шао.

В §2 третьей части описаны (с точностью до подстановочного подобия) матрицы смежности всех дихотомических графов с максимальным обхватом из классов в(п, 2]п/2[) и Р(п, 2, ]п/2[). В частности, доказано, что

У (Г)=п-1

1.7) для любого графа Г е Р(п, 2, ]п/2[), п Ф 6.

В §3 третьей части описаны структурные свойства графов из множества С(п, 2, при нечетном п > 13; доказано, что в этом случае в(п, 2, уЦ = Р(п, 2, у~), п-1 и для любого Г еР (п, 2, у-)

1 / построен граф из Р(п, 2, у) с экспонентом -—— + 1.

Отметим, что из результатов последних двух параграфов следует, что свойство линейного роста достижимой верхней оценки экспонента по величине обхвата, справедливое в классе примитивныхх графов с простым числом вершин п, не имеет места в класее п-вершинных дихотомических примитивныхх графов.

Ясно также, что в классе п-вершинных дихотомических примитивныхх графов максимальным экспонентом обладает граф с немаксимальным обхватом.

В §4 третьей части получены верхние оценки экспонентов дихотомических графов из классов Р(п, 2, р) при 3<р<]п/2[. Доказано, что г)<(р + 1)£ 4 ; 2р -1

1.8) для любого графа Г е Р(п, 2, р), 3 < р < ]п/2[. При р = 1,2 более точными остаются оценки (1.5) и (1.6), соответственно. При получении последнего результата существенно использовались метод, изложенный в первом параграфе и оценка (1-4), полученная во второй части.

В §5 третьей части получены верхние оценки экспонентов графов из классов Р(п, к, р) при р = 1, 2. В частности, доказано, что для любого Г е Р(п, к, 2), где к > 3, справедливо неравенство

У (П

1 2 п - 1

9кТТ-5 если к > 6 п п +

1; п + 2

11 п — 6 к + 1 если к < 6 п - 1 п + 1

- 1

1.9)

Часть II. ДИАМЕТРЫ ПСЕВДОСИММЕТРИЧЕСКИХ ГРАФОВ.

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

В настоящем параграфе доказаны основные леммы, результаты которых позволяют получить верхние оценки диаметров графов из классов Н (п, к, р) при р=1, 2, 3.

Каждому сильно связному графу Г поставим в соответствие разбиения (Г), 1 е {1,., п}, множества его вершин V на непустые непересекающиеся подмножества, которые будем называть ярусами:

0-ой ярус разбиения 11^ (Г) образует вершина

1-ый ярус образуют все вершины, в которые входят дуги, исходящие из вершину 0-го яруса и не совпадающие с [; ярус образуют все вершины, в которые входят дуги, исходящие из вершин ^-1 )-го яруса, не совпадающие с вершинами 0-го, 1-го, ., (]-1)-го ярусов,] > 1.

Так как Г сильно связен, любая его вершина окажется включенной в какой-либо ярус разбиения (Г). Будем обозначать через Ь[ (Г) номер старшего яруса в (Г), а через А,^ (Г) - число вершин ]-го яруса (Г), ] = (там, где это не будет вызывать путаницы, будем писать Ц, и Я^).

Утверждение 2.1. Пусть Г - произвольный п-вершинный псевдосимметрический граф, С) и Ь - непересекающиеся непустые подмножества вершин Г, такие, что

I (2 I + | Ь | = п.

Тогда число дуг, исходящих из вершин и входящих в вершины Ь, совпадает с числом дуг, исходящих из вершин Ь и входящих в вершины С*.

Доказательство. Индукция по | | . Пусть |с>|=1. В этом случае справедливость утверждения следует из определения 1.1. псевдосимметрического графа. Пусть | С* | =ш и утверждение справедливо.

Пусть |С)|=т+1. Выделим произвольную вершину ¡еС) (см. рис. 2.1.).

Обозначим через и и 8 число дуг, исходящих из вершин С>\{1} и входящих в вершины Ь и ¡, соответственно; через v и г - число дуг, исходящих из вершин Ь и входящих в вершины и соответственно; через р и q - число дуг, исходящих из \ и входящих в вершины С>\{1} и Ь соответственно.

Тогда из предположения индукции следует, что и+з=у+р. Из псевдосимметричности Г следует, что p+q=s+r. Сложив эти два равенства, получим д+и=у+г, что и требовалось. ■

Рис. 2.1 Разбиение вершин графа Г на подмножества. Лемма 2.2. Если Ге Н (п, к, 2), то для любого разбиения

Г) [е V и ] = О, Ь[-2 справедливо неравенство

Я.1и) + Х1а+1) +А,1и+2)>к+1.

Доказательство. Рассмотрим разбиение вершин графа Г на три подмножетсва А|+1, С,+1: образуют все вершины 0-го, 1-го, ., ]-го ярусов разбиения Я ¡; образуют все вершины 0 + 1)-го яруса; С(+1 - остальные вершины.

Обозначим через а ¡+1 число дуг, исходящих из вершин и входящих в вершины В^ь а,+ ] - число дуг, исходящих из вершин В^ч и входящих в вершины А]+ь

Ь|+] - число дуг, соединяющих между собой вершины В|+,; Cj.fi- число дуг, исходящих из вершин С,+1 и входящих в вершины с+1- число дуг, исходящих из вершин и входящих в вершины

С|+1

Тогда выполнено неравенство с) + 1 + к-а] + 1 . (2.1)

Оце ним а,+[, Ь]+1, С|+],. Прежде всего отметим, что с учетом утверждения 2.1., имеет место равенство а ]+1 — а .¡+1 + с ¡-1, и, следовательно, а ,+1 < а ]+]

Так как в Г нет параллельных дуг, то

Так как в Г нет петель, имеем

Ь] + 1<^[0+1)(^1а+1)- О- (2-2)

Воспользовавшись последними тремя неравенствами, из (2.1) получаем а.и+п ^.и+2) > ^.о + п к а.и+п. ^(М) . 1}.

Разделив на * 0 правую и левую части, получаем требуемое неравенство. ►

Лемма 2.3. Если Ге Н (п, к, 1), то для любого разбиения (Г), 1 е V и ] = О, Ъ[-2 справедливо неравенство

Х^ + + > к.

Доказательство аналогично приведенному выше, вплоть до неравенства (2.2), вместо которого имеем: за счет возможности существования петель. ►

Лемма 2.4. Если Ге Н (п, к, 3), то для любого разбиения (Г) I е V и ] = О, Ь[-4 справедливо неравенство

2.3) + > 2к + 2.

Доказательство. Имеет место следующий очевидный факт. Пусть а, Ь, с, 6- действительные числа. Неравенство аЬ + сё > + (1) (Ь + с) (2.4) справедливо тогда и только тогда, когда а > (1, Ь > с, либо а < с1, Ь < с.

Рассмотрим разбиение множества вершин Г на три подмножества: такое же, как и в лемме 2.2, В,+ 1 - множество вершин 0+1) -го? С+2)-го, 0+3)-го ярусов разбиения а С)+) - множество всех остальных вершин. Величины а,+!, ь С|+ь определим так же, как и в лемме 2.2.

Тогда справедливо неравенство: сз+1 >(Я,1а+1) + Я,1а+2)+ ^(-,+3))к

2.5)

- - Ь ¡+1.

Помимо этого имеем а]+1< V"0

Так как в Г нет петель и контуров длины 2, то bj.fi < +

2.6)

Воспользовавшись последними тремя неравенствами, из (2.5) получаем и+3) ^.а+4) > (31.о+1) +

Следовательно,

-(Х-^ + Х^+Х^) (2к + 1

- (^0+1) + ^а+2)+ А,10+3))) - (2.7)

Имеют место очевидные неравенства

Х-® Х^+1) + Х^ <

2.8) Х^ + (Х^+2) + Х-^) ^а+4)

Возможны следующие два случая. 1. Четверки чисел и

2.9) таковы, что подставив их вместо а, Ь, с и с1, соответственно в (2.4), мы получим верные неравенства. Тогда выполнены системы неравенств:

5Ц а+1) + > Л^1

Х{ > Х1 {]+л) либо,

Зц а+1) + ^. а+2) а+2) < а+з) зца) < ^а+4)

Пусть, например, выполнена первая система неравенств (для второй все доказывается аналогично). Сложив второе и третье неравенства, получаем

Так как для Г справедлива лемма 2.2., из последнего неравенства непосредственно получаем справедливость (2.3). 2. Хотя бы одна из четверок чисел (пусть это, например,

Х-®, X+ такова, что (2.4) для нее не выполняется. То есть а) +(ка+1) + я[а+2) + х[а+3))

Следовательно, с учетом (2.8),

Подставляя правую часть последнего неравенства вместо последнего члена в скобках в левой части неравенства (2.7), получаем

Ача+1) + ^0+3))(2к+ 1

- + зча+2)+ к(]+3)))

- + (Я,1а+1) +ЗЦа+2)+ ^а+3))] < о, откуда и следует справедливость (2.3) и в этом случае. ►

Замечание 2.5. Рассмотрим разбиение вершин графа Ге Н(п, к, 3) на три подмножества аналогично тому, как это было сделано в лемме 2.2. (то есть В)+1 содержит вершины 0 + 1)-го яруса разбиения В этом случае, для Ь ¡+1 будет справедлива оценка, аналогичная (2.6)

Повторяя рассуждения леммы 2.2., получим, что если Ге Н (п, к, 3) то для любого разбиения (Г), \ е V и ] = 0, \-2 справедливо неравенство

2 + +2 Х[(]+2) > 2к + 1. (2.10)

Ясно, что (2.3) более точно отражает распределение вершин графа по ярусам его разбиений, чем последнее неравенство (2.10).

Для графов из Н (п, к, 3) при к = 2, 3 удается уточнить результат.

Лемма 2.6. Пусть Ге Н (п, к, 3) и 1 е V. Если ] е {0, . , Ь ^ - 3}, таково, что + + + ^ °+3) = 2к + 1 - у,

2.11) у > 0. тогда

Х-^+2) - Х-^) {Х^+3) - Х-^) >

2.12) у (Х{ а+1) + Х^+3))

Доказательство. Так же, как и в леммах 2.2.-2.4., разобьем множество вершин Г на три подмножества А ¡+], В ¡+] и С где В ¡+1 - множество вершин (] + 1)-го и ^+2)-го ярусов разбиения а А ¡+1 и С ¡+1 определяются так же, как и в лемме 2.4. Оценивая количество дуг, связывающих между собой вершины этих множеств, по аналогии с леммой 2.4., приходим к неравенству 1 2 гк + 1 - + л1с+2))](а[ (]+1)+ х^+2)) «> Х{ (]+1)+ а+2) Х{ (]+3)) < о

Пусть] таково, что выполнено равенство (2.11). Тогда

2к +1) - (Х{ а+1) + Х1 а+2)) = X; ш + ^ а+3) + у.

Подставив правую часть последнего равенства вместо левой в последнее неравенство, получим х-® + >ча+3) + у) + >ча+2))

- (Х{(]) Х{{]+1) + Х-^+2) Х^+3)) < о, откуда легко получается требуемое неравенство (2.12). ►

Следствие 2.7. Если Ге Н (п, к, 3), к е {2, 3}, то для любого разбиения \ е V и ] = 0, ЬрЗ , справедливо неравенство ^а+2) +^а+3)> 2к+ 1 (2.13)

Доказательство. Пусть к = 2. Возможны два случая.

1. > к, либо ^а+3) ^ к-Тогда, с учетом леммы 2.2 получаем требуемое неравенство.

2. ^С) = Х.а+3)=

40

Пусть выполнено (2.11). Тогда в левой части (2.12) стоит нуль - противоречие с предположением. Следовательно, выполнено (2.13).

Пусть к = 3. Также как и при к = 2 легко показать, что для случаев ш > к, либо ^ а+3) > к, либо а) = ^ а+3) неравенство (2.13) выполняется. Остается один возможный случай:

0+3> - х^) |= 1, к, Я.1а+3)< к.

Пусть выполнено (2.11). Тогда модуль левой части (2.12) должен быть больше модуля правой части - очевидно, невыполнимое неравенство. Противоречие с предположением. Следовательно, справедливо (2.13). Следствие доказано.«

Выводы: В третьей части диссертации для псевдосимметрических и дихотомических графов с заданным числом вершин получены верхние оценки экспонентов в зависимости от минимальной полустепени исхода и захода и длины наименьшего контура. Полученные оценки существенно точнее ранее известных. При этом использован модифицированный метод из /57/ и оценки диаметров графов из части II.

ЗАКЛЮЧЕНИЕ.

В диссертационной работе исследованы верхние оценки диаметров и экспонентов псевдосимметрических и дихотомических графов.

1. Предложен метод получения верхних оценок диаметров псевдосимметрических графов, основанный на точном оценивании количества вершин в некотором числе (зависящем от обхвата графа) подряд идущих ярусов разбиения множества вершин графа (по расстоянию от произвольной вершины).

2. Получены верхние оценки диаметров псевдосимметрических графов с обхватом не меньше 1, 2 и 3, близкие к достижимым. Достижимость оценивалась путем построения графов с соответствующими диаметрами.

3. Получены верхние оценки диаметров дихотомических графов с произвольным обхватом, близкие к достижимым.

4. Классифицированы (с точностью до подстановочного подобия) все дихотомические графы с максимальным обхватом. Доказано, что все примитивные п-вершинные дихотомические графы с максимальным обхватом, за исключением двух графов с шестью вершинами, имеют экспонент п-1.

1. Берж К. Теория графов и ее применения. - М.: Наука. -1962. - 319 с.

2. Гантмахер Ф. Р. Теория матриц. 4-е изд. М.: Наука, -1988. - 552 с.

3. Голунков Ю. В. О сложности представления симметрической полугруппы через элементы систем образующих // Кибернетика. -1971. -№1. С. 43-44.

4. Григорчук Р. И. К проблеме Милнора о групповом росте // Докл. АН СССР. 1983. - т. 271, № 1. - С. 30-33.

5. Князев А. В. О диаметрах псевдосимметрических графов // Математические заметки. -1987.- т. 41, № 6. С. 829 - 843.

6. Князев А. В. Дихотомические графы с максимальным обхватом // Дискретная математика. -1990.- т. 2, вып. 3. -С. 56 64.

7. Князев А. В. Верхние оценки экспонентов псевдосимметрических графов // Дискретная математика. -1990,- т. 2, вып. 4. С. 63 - 71.

8. Князев А. В. О диаметрах дихотомических графов // Математические заметки. -1991.- т. 50, № 1. С. 46 - 55.

9. Князев А. В. Верхняя оценка а-диаметра и экспонента трихотомического графа. // Сб. тр. 3 Всес. семинара по дискретной математике и ее применению, Москва, 30 января 1 февраля, 1990. 1997. - С. 95.

10. Князев А. В. О дихотомических графах с обхватом на единицу меньшим максимального// Дискретная математика. -2002.- т. 14, вып. 2, С. 119-133.

11. Князев А. В. Экстремальные значения основных метрических характеристик дихотомических графов// Обозрение прикладной и промышленной математики. -2002- т. 9, вып. 1, С. 205-206.

12. Князев А. В. Теоретико-графовое моделирование информационных процессов в АСУ// Информационные процессы и системы. НТИ. Сер. 2,- 2002.- №4. С. 8 - 11.

13. Князев А. В. Теоретико-графовое моделирование информационных процессов в АСУИ// Сборник Московского Авиационного Института.- 2002.- №2, С. 14-31.

14. Коршунов А. Д. О диаметре графов // Докл. АН СССР. -1971. т. 196,№ 5. - С. 1013-1015.

15. Кузин Л. Т. Основы кибернетики: В 2-х т. Т. 1. // Математические основы кибернетики. М.: Энергия, -1973.- 502 с. Т. 2. // Основы кибернетических моделей. М.: Энергия. -1979. 584 с.

16. Ловцов Д. А. Введение в информационную теорию АСУ. М.: ВА им. Ф. Э. Дзержинского -1996. 434 с.

17. Маргулис Г. А. Группы полимиального роста // 15-ая Воронеж, зим. мат. школа. Воронеж -1981. 14 с. - Деп в ВИНИТИ 16.12.1981, №569 - 81 Деп.

18. Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: Наука. -1982. - 384 с.

19. Трофимов В. И. Два замечания о росте групп // Мат. зап. Урал, универ. 1983. т. 13, № з. с. 172 176.

20. Труды по дискретной математике т. 1. 1997 - //Труды Академии криптографии РФ.

21. Труды по дискретной математике т. 2. 1998 - //Труды Академии криптографии РФ.

22. Baskoro Edy Tri, Miller Mirka, Plesnik Jan. On the structure of digraphs with order close to the Moore bond // Graphs and Сотр. -1998. V. 14., №2. С. 109 - 119.

23. Beasley L.B. Kirkland S.J On the exponent of a primitive matrix containing a primitive submatrix. // Linear algebra and its applications. 1997. - v.261. P. 195- 205.

24. Behzad M. Minimal 2-regular digraphs with given girth // J. Math. Soc. Japan. -1973. №5. - P. 1-6.

25. Behzad M., Chartand G., Wall C. E. On minimal regular digraphs with given girth // Fund. Math. 1970. - №69. - P. 227 - 231.

26. Bermond J. C. 1-graphes reguliers minimaux de girth donne // Proc. Journees franco-belges sur les graphes et gypergraphes / Cahiers du CERO. Bruxelles. - 1975.- №17. - P. 125 - 135.

27. Bermond J. C., Thomassen C. Cycles in Digraphs A Survey// Journal of Graph Theory, V. 5.-1981.- P. 1-43.

28. Brualdi R. A., Lian Liu Bo. Generalized exponents of primitive directed graphs// J. Graph Theory. 1990. - 14, №4. - p. 483 - 499.

29. Brualdi R. A., Ryser H. J. Combinatorial Matrix Theory. Cambridge University Press, 1991.

30. Cacceta L., Hâggkvist R. On minimal digraphs with given girth // Proc. 8th Southeasten Conf. on Combinatorics, Graph Theory and Computing: Utilitas Math. Publ., Congressus Numerantum XXI. 1978. - P. 181 -187.

31. Chuny F. R. K., Goddard Wayne, Kleitman Daniel J. Even cycles in derected graphs // SIAM J. Descrete Math. 1994. -7, № 3. - p 474 - 483.

32. Chvatal V., Szemeredi E. Short cycles in directed graph// J. Comb. Theory Ser. B. 1983 - P. 181 - 187.

33. Dankelmann Peter, Entringer Roger. Average distance, minimum degree, and spanning trees.// J. Graph Theory. -2000.- V. 33, №1. C. 1-13.

34. Driscoll J. R., Fürst M. L. Computing Short Generator Sequences // Information and computation. 1987 - №72. P. 117 - 132.

35. Dulmage A. L., Mendelsohn N. S. Gaphs in the exponent set of primitive matrices // Illinois J. Math. 1964. - №8. -P. 642 - 656.

36. Fiduccia Charles M., Forcade Rodney W., Zito Jennifer S. Geometry and diameter bounds of directed Cayley graphs of abelian groups// SIAM J. Discrete Math. 1998. - 1 1, №1, p. 157-167.

37. Frobenius G. Über Matrizen aus nicht negativen Elementen // Sitzungs ber. Pre. Akad, Wiss., Berlin, -1912. P. 456 -477.

38. Hamidoun Y. O., Llado A. S., Serra O. Minimum order of loop networks of given degree and girth // Graphs and Comp. 1995. - 11, №2. - P. 131 - 138.

39. Hoang C. T., Reed B. A note on short cycles in digraphs // Discret Math. 1987. - № - 66. - P. 103 - 107.

40. Holladay, Varga On powers of non-negative matrices // Proc. Am. Math. Soc. 1958. - v. 9, № 4.

41. Huang D. On circulant Boolean matrices// Linear algebra and its applications. 1990. - v.136. P. 107- 117.

42. Jia Xingde. Cayley digraphs of finite ciclic groups with minimal average distance // Interconnect. Networks and Mapp. and Shedul. Parall. Comput.: DIMACS Workshop, Piscataway, N. J., Febr. 7 9 -1994. - Providence (R. I.) -1995. - P. 229 - 250.

43. Kirkland S.J. A note on the eigenvalues of a primitive matrix with large exponent// Linear algebra and its applications. 1997. - v.253. P. 103- 112.

44. Kirkland S.J., Neuman M. Regular Markov chains for wich the transition matrix has large exponent// Linear algebra and its applications. 2000. - v,316 (1-3). P. 45- 65.

45. Kirkland S.J., Olesky D.D., Van Den Driessche P. Digraphs with large exponent// The electronic journal of linear algebra.- 2000. v,7. P. 30- 40.

46. Knor Martin. A note on radially Moor digraphs// IEEE Trans. Comput. 1996. - 45, №3. - p. 381 - 383.

47. Kwasnik Maria. Index of primitivity of the exclusive disjunction of two directed graphs// Discussions Mathematica. v. VII- 1984.- P.32-49.

48. Kwasnik Maria. Primitivity of the exclusive disjunction of two symmetric directed graphs// Discussions Mathematica.v. VII -1984. P.40-59.

49. Kwasnik Maria. Index of primitivity of the disjunction and the composition of two directed graphs// Math. Nachr. 1987.- V.134 P.231-235.

50. Lewin, Vitek Y. A sistem of graphs in the exponent set of primitive matrices// Illinois Journal Math. 1981. - № 25. P.87 - 98.

51. Lian Liu Bo, Wen Jiang. On a conjecture of Lewin's problem// Linear algebra and its applications. 2001. - v.323 (1-3). P. 201- 206.

52. Meng Jixiang, Liu Xin. The diameters of all Cayley digraphs // Acta math. appl. sin. Engl. Ser. 1997. - v. 13, № 4. - P. 410 - 413.

53. Moon J. W. On the diameter of a graph // The Michigan Math. J. Sept. -1965. - v. 12, №3. - P. 349 - 352.

54. Neufeld S. A diameter bound of the exponent of primitive directed graph// Linear algebra and its applications. 1996. -v,245. P. 27- 48.

55. Neufeld S. The concept of diameter in exponents of symmetric primitive graphs // ARS Combinatoria 1999.- № 51. P. 129-142.

56. Nishimura Ts. Short cycles in digraphs// Discrete Mathematics V. 72. 1988.- P. 295-298.

57. Shao Jia-Yu On the exponent of a Primitive digraph // Linear algebra and its applications 1985. - № 64. - P. 2131.

58. Shao Jia-Yu, Dong Wei-Quan, Dong Chun-Fei.On the Exponents of Primitive Digraphs with the Shortest Elementary Circuit Length s// Linear algebra and its applications. 1988.- №104. P. 1- 27.

59. Shao Jia-Yu, Huang Suk Genn. Generalized exponents of non-primitive graphs// Linear algebra and its applications. 1998. - v.279 (1-3). P. 207- 225.

60. Shen Jian. A bound on the exponent of primitivity in terms of diameter// Linear algebra and its applications. 1996. -v,244. P. 21- 34.

61. Shen Jian. A problem on the exponent of primitive digraphs // Linear algebra and its applications. 1996. - v,244. P. 255264.

62. Sylvestr J. J. Math. Questions and their solutions // Edictional Times. 1884. - № 41. - P. 21.

63. Van Nuffelen C. Rank and diameter of a graph // Bull. Soc. math. Belgium. 1982. - v. B34, №1. - P. 105 -111.

64. Vitek Y. Bounds for a linear diophantine problem of Frobenius // J. London Math. Soc. 1975. -№10. - P. 79 -85.

65. Wiegold J. Growth sequences of finite semigroups // J. Austral Math. Soc. 1987. - v. A43, №1. - P. 16-20.

66. Wielandt H. Unzerlegbare nicht negative Matrzen // Math. Zeitschr. 1959. - № 52, - P. 642-648.

67. Xu Sh.-ji. Some parameters of graph and its complement // Discrete Mathematics. 1987. - № 65. P. 197 -207.