них відповідно позитивних, негативних і відмінних від перших двох на - 1 або 0 значень, то
Ця теорема була доведена за допомогою нерівностей Куранта - Вейля і використовується при доказі декількох лем. ??
. 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 потрібно, щоб він був або регулярним, або регулярним і зв'язковим. Ці умови можуть бути замінені наступними:
) спектр графа G задовольняє (2.22)
) спектр графа 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. ПРЕДФРАКТАЛЬНИЙ ГРАФ з запалом регулярної СТУПЕНЯ
. 1 ВИЗНАЧЕННЯ ПРЕДФРАКТАЛЬНОГО І фрактальної ГРАФА
Терміном затравка домовимося називати будь-якої зв'язний орієнтований граф. Для визначення орієнтованого фрактального (предфрактального) графа нам знадобиться операція заміни вершини затравкой (ЗВЗ). Суть операції ЗВЗ полягає в наступному. У даному графі у наміченої для заміщення вершини виділяється безліч, суміжних їй вершин. Далі з графа видаляється вершина і всі інцідентние їй дуги. Потім кожна вершина, з'єднується дугою з однією з вершин затравки. Вершини з'єднуються довільно (випадковим чином) або за певним правилом.
Предфрактальний орієнтований граф будемо позначати через, де? безліч вершин графа, а? безліч його дуг. Визначимо його рекуррентно, поетапно, замінюючи кожен раз в побудованому на попередньому етапі орграфе кожну його вершину затравкой. На етапі предфрактальному орієнтованому графу відповідає приманка. Про описаному процесі кажуть, що предфрактальний орієнтований граф породжений затравкой. Процес породження предфрактального орграфа, по суті, є процес побудови послідовності предфрактальних орграфів, званої траєкторією. Фрактальний орієнтований граф, породжений затравкой, визначається нескінченною траєкторією.
Предфрактальний орієнтований граф домовимося називати -орграфом, якщо він породжений -вершиною дугова зв'язковий затравкой, і -орграфом, якщо затравка - регулярний орграф.
Використання операції ЗВЗ в процесі породження предфрактального орієнтованого графа, для елементів,, його траєкторії дозволяє ввести відображення або, а в загальному вигляді
,. (3.1)
У виразі 1 безліч? образ множини, а безліч прообраз множини. Для предфрактального орієнтованого графа, дуги, що з'явилися на -ом,, етап породження, називатимемо дугами рангу. Новими дугами предфрактального орієнтованого графа назвемо дуги рангу, а всі інші дуги назвемо старими.
Блоки предфрактального орграфа. Якщо з предфрактального орграфа, породженого -вершиною затравкой, послідовно видалити всі старі ребра (ребра рангу,), то вихідний граф розпаде...
