Можно доказать, что каждый граф G содержит порожденный подграф H с dmin (H) ?(k + 1) ( (G) -- 1). На этой основе совершенно аналогично тому, как это было сделано в предыдущем случае, может быть доказана следующая теорема.

Теорема 2.17. Для любого графа G с индексом r и любого неотрицательного целого k

Для доказательства следующей теоремы приведем без доказательства лемму.

Лемма 2.2. Пусть А -- действительная симметрическая матрица порядка n и - разбиение множества {1, ..., n} на непустые подмножества. Akk означает подматрицу матрицы А с индексами строк и столбцов из . Тогда, если k= 1, .... t,

(2.17)

где лf (X), i = 1, 2,… -- собственные значения матрицы X в убывающем порядке.

Теорема 2.18. Если r(r?0) и q -- наибольшее и наименьшее собственные значения графа G, то его хроматическое число удовлетворяет неравенству

(2.18)

Доказательство. Пусть ч(G) = t и вершины графа G помечены числами 1, ..., n. Тогда существует разбиение такое, что каждый подграф графа G, порожденный подмножеством не содержит ребер. При ik = 0 (k = 1, ..., t) из (2.17) для собственных значений = q графа G получаем

(2.19)

Так как , то (2.18) следует из (2.19). Это и завершает доказательство теоремы.

Заметим, что из (2.19) можно получить больше информации о хроматическом числе, чем из (2.18). Действительно, (2.19) дает границу

Из следующей теоремы нижняя граница для хроматического числа получается иной.

Теорема 2.19. Если G -- граф с n вершинами, индексом r и хроматическим числом X (G), то

Доказательство. Рассмотрим хроматический многочлен к-полного графа . Многочлен имеет единственный положительный корень -- простой. Действительно, полные многодольные графы являются именно такими связными графами с простым положительным собственным значением. Значит, для х > 0 тогда и только тогда, когда х ?л1. Теперь рассмотрим значения

, л>0, (2.20)

Предположим, что ni могут принимать положительные действительные значения. Тогда (2.20) достигает своего наибольшего значения, когда все ni равны. Действительно, если ni ?nj , то, предполагая, что ) и не изменяя всех других значений, приходим к выводу, что сумма (2.20) является возрастающей. Для частного значения сумма (2.20) равна 1 тогда, когда ni равны Поэтому, когда nt положительные целые числа, то выражение неотрицательно и , следовательно,

(2.21)

Здесь равенство справедливо лишь в случае, когда граф регулярен.

Таким образом, доказан следующий результат.

Лемма 2.3. Индекс r графа Kn.....nk удовлетворяет неравенству

где

Теорема 2.20. Если - число собственных значений графа G, не больших -1, то существует функция f такая, что

Теорема 2.21. Если - собственные значения графа G, a р+, p_, p- числа собственных соответственно положительных, отрицательных и отличных от первых двух на -1 или 0 значений, то

Эта теорема была доказана с помощью неравенств Куранта -- Вейля и используется при доказательстве нескольких лемм.

2.3 РЕГУЛЯРНЫЕ ГРАФЫ

Регулярный граф - граф, степени всех вершин которого равны, т.е. каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается r(G).

Многочисленные теоремы из теории регулярных графов не справедливы для нерегулярных графов. Естественно, все теоремы, содержащиеся в 2.2 , справедливы также для регулярных графов.

Начнем изложение с проблемы: каким образом с помощью спектра графа можно решить вопрос о том, является ли заданный граф регулярным или нет?

Теорема 2.22. Пусть л1=r, л2,…, лn- спектр графа G, а r- его индекс. Граф G регулярен степени r тогда и только тогда, когда

(2.22)

Доказательство. Так как среднее значение степени вершины в G определяется формулой (m - число ребер), то теорема 2.22 является следствием теоремы 2.8.

Ее можно легко распространить на случай, когда допускается существование петель у некоторых вершин графа G. Если G содержит кратные ребра или петли, то для установления регулярности может быть использована теорема 2.33. Очевидна

Теорема 2.23. Число компонент регулярного графа равно кратности его индекса.

Теоремы 2.22 и 2.23 в дальнейшем неоднократно используются. Во многих теоремах от графа G требуется, чтобы он был либо регулярным, либо регулярным и связным. Эти условия могут быть заменены следующими:

1) спектр графа G удовлетворяет (2.22)

2) спектр графа G удовлетворяет (2.22) и r является простым собственным значением. Таким образом, в подобных теоремах предположения, относящиеся к общей структуре графа, имеют, по-видимому, «неспектральный» характер.

Теорема 2.24. Если z -- число простых циклов С2 длины 2 в регулярном мультиграфе G степени r с n вершинами без петель, то 4z = -2а2 -nr, где а2 -- коэффициент при в характеристическом многочлене мультиграфа G.

Доказательство. Пусть - элемент матрицы смежности. Тогда

Если -число простых циклов С2, содержащих вершины i и j, то

и =

Теорема 2.25. Для графа G с матрицей смежности А существует многочлен Р (х) такой, что Р (А) = J тогда и только тогда, когда G регулярен и связен. В этом случае

где n -- число вершин, r -- индекс, - все различные собственные значения графа G.

Эта важная теорема представляет большие возможности для исследования структуры графов посредством спектров и поэтому неоднократно используется в дальнейшем.

ГЛАВА 3. ПРЕДФРАКТАЛЬНЫЙ ГРАФ С ЗАТРАВКОЙ РЕГУЛЯРНОЙ СТЕПЕНИ

3.1 ОПРЕДЕЛЕНИЕ ПРЕДФРАКТАЛЬНОГО И ФРАКТАЛЬНОГО ГРАФА

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

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

Предфрактальный ориентированный граф условимся называть -орграфом, если он порожден -вершинной -дуговой связной затравкой , и -орграфом, если затравка - регулярный орграф.

Использование операции ЗВЗ в процессе порождения предфрактального ориентированного графа , для элементов , , его траектории позволяет ввести отображение или , а в общем виде

, . (3.1)

В выражении 1 множество ? образ множества , а множество прообраз множества . Для предфрактального ориентированного графа , дуги, появившиеся на -ом, , этапе порождения, будем называть дугами ранга . Новыми дугами предфрактального ориентированного графа назовем дуги ранга , а все остальные дуги назовем старыми.

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

Уточним для отображения в (2.1) ряд подробностей. Для любой вершины , предфрактального орграфа , , из траектории орграфа , справедливо

, (3.2)

, где , .

Аналогично,

, (3.3)

, , .

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

Утверждение 1. Всякий предфрактальный ориентированный граф можно представить в виде множества подграф-затравок , соединенных старыми дугами разных рангов. А именно, старые дуги -го ранга объединяют множество подграф-затравок в множество блоков второго ранга, их в свою очередь, старые дуги -го ранга объединяют в множество блоков третьего ранга и т.д. Окончательно, старые дуги первого ранга объединяют множество блоков -го ранга в связный предфрактальный ориентированный граф .

Подграф-затравки предфрактального ориентированного графа. Термином подграф-затравка будем называть блок , первого ранга предфрактального орграфа , из траектории. Последовательное выделение подграф-затравок на графах из траектории предфрактального ориентированного графа разбивает множество дуг на непересекающиеся подмножества подграф-затравок , где , ? ранг подграф-затравки, а ? ее порядковый номер. Такое разбиение на подмножества позволит нам сохранить информацию смежности старых дуг на момент их появления в предфрактальном графе. В траектории переход от графа к осуществляется операциями ЗВЗ, поэтому общее число использованных затравок в порождении предфрактального графа равно . Тогда мощность множества всех подграф-затравок из траектории графа также равно .

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

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

Определим операцию “склеивания” двух произвольных графов

и .

Рисунок 1. Склеивание графов

Выбираются две вершины для слияния - и (см. рис. 2.2). Граф , полученный из графов и слиянием вершин и в некоторую вершину так, что все ребра, инцидентные вершинам и , становятся инцидентными вершине , называется склеенным из графов и .

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

В том случае, когда на каждом этапе порождения предфрактального ориентированного графа подграф-затравки склеиваются с подграф-затравками ранних рангов в различных своих вершинах будем говорить, что предфрактальный ориентированный граф порожден с обязательным сохранением смежности старых дуг только одного ранга. Это условие порождения предфрактального ориентированного графа является более “мягким”, нежели предыдущее.

3.2 СПЕКТР ПРЕДФРАКТАЛЬНОГО ГРАФА С ЗАТРАВКОЙ РЕГУЛЯРНОЙ СТЕПЕНИ

Метод блочно- треугольный

Блочная матрица -- вид квадратной матрицы, каждый элемент которой является квадратной подматрицей меньшей, кратной размерности.

Пример записи

Матрица размерностью 4Ч4

является блочной, состоящей из четырех подматриц-блоков размерностью 2Ч2

Если каждый блок будет определен как

то, блочная матрица может быть записана в следующем виде

Рассмотрим спектр степени S=1

2

1Размещено на http://www.allbest.ru/

3

D = 1+8 = 9

Рассмотрим спектр предфрактального графа с затравкой степени S=2

Размещено на http://www.allbest.ru/

Ответ:

ВЫВОДЫ

1. Рассмотрено понятие спектра графа

2. Рассмотрены связи между спектральными и структурными свойствами графов

3. Рассмотрен предфрактальный граф с затравкой регулярной степени

4. Подсчитан спектр предфрактального графа с затравкой регулярной степени S=1 и S=2

СПИСОК ЛИТЕРАТУРЫ

1. Емеличев В. А., Мельников О. И., Сарванов В.И., Тышкевич Р. И. и др. Лекции по теории графов М.:Наука, 1990.

2. Кочкаров А. М. , Перепелица В. А. , Сергеева Л. Н. Фрактальные графы и их размерность. Черкесск , 1996.

3. Кочкаров А.М.,Перепелица В.А. Метрические характеристики

фрактального и предфрактального графа . Сб.РАН САО .-1999.

4. Федер Е. Фракталы .-М.:Мир,1991

5. Харари Ф., Палмер Э. Перечисление графов. -М.: Мир, 1977.

6. Кочкаров А. М. Распознавание фрактальных графов. -Нижний Архыз: РАМ САО, 1998.

7. Харари Ф.Теория графов. - М:Мир, 1973

Размещено на Allbest.ru