их циклів цього графа.
Якщо спробувати сформулювати теорему для графів, подібну теоремі 2.1, то виникнуть наступні труднощі. Поряд з графом G розглянемо орграф H, який має ту ж матрицю суміжності, що і G. Якщо граф G містить принаймні одне ребро, то g (H)=2, тоді як g (G) при цьому може бути як завгодно великим. Тому обхвати графів G і H не пов'язані один з одним. Однак легко переконатися ось у чому. При i lt; g (G) базисна фігура існує лише для парного i=2q і кожна базисна фігура U2q складається з q несуміжних ребер, так що р (U2q)=q і з (U2q)=0. Отже,
(i lt; g (G)),
де bq - число базисних фігур, що складаються в точності з q несуміжних ребер.
Для i=g (G) базисні фігури можуть бути або фігурами описаного вище виду (що складаються з несуміжних ребер і лише для парних i), або це можуть бути прості цикли довжини g (G). У другому випадку внесок кожної такої базисної фігури в ai дорівнює - 2. Якщо
,
то=0 для i lt; g (G) і дорівнює подвоєному числу простих циклів довжини g (G)
Отже, отриманий наступний результат.
Теорема 2.12. Нехай G - граф (мультіграф) з характеристичним многочленом (2.1) і bq - число базисних, фігур, що складаються з q несуміжних ребер. Нехай, далі,
Тоді g (G) дорівнює індексу першого відмінного від нуля числа серед число простих циклів довжини g (G) одно -
Так як матриця суміжності А графа є симетричної, можна на основі спектра визначити її мінімальний багаточлен. Якщо, як відомо, {? (1), ...,? M} - множина всіх різних власних значень матриці А, то відповідний мінімальний багаточлен
Нехай Тоді справедливе співвідношення
(k=0,1, ...) (2.12)
Використовуючи його, можна довести наступну теорему.
Теорема 2.13. Якщо зв'язний граф G має точно m різних власних значень, то його діаметр D задовольняє нерівності.
Доказ. Припустимо, що теорема невірна. Тоді для деякого зв'язного графа G маємо D=s? m. З визначення діаметра випливає, що для деяких i і j елементи а з i-го рядка і j-го стовпця матриці Аk (k=1, 2, ...) дорівнюють нулю при k lt; s, тоді як а=0.
Покладемо в (2.12) k=s - m. Використовуючи певний таким чином співвідношення, з а? 0 (k=1, ..., s - 1) виводимо а=0, що суперечить припущенню.
Це і завершує доказ теореми.
Кількість внутрішньої стійкості? (G) графа G визначається як найбільше число вершин, які можуть бути обрані в G таким чином, що жодна пара з них не з'єднана ребром в G.
Теорема 2.14. Число внутрішньої стійкості? (G) графа G задовольняє нерівності
? (G)? po + min (р-, р +), (2.13)
де p-, р0, р + - відповідно числа власних значень графа G, менших нуля, рівних нулю і великих нуля. Існують графи, для яких в (2.13) має місце рівність.
Доказ. Нехай s=р0 + min (p-, р +). Припустимо, що існує граф G, для якого? (G) gt; s. Тоді існує породжений підграф графа G з? (G) вершинами, що не містить ребер. Звідси випливає, що головна подматріца порядку? (G) матриці суміжності графа G є нульовою матрицею. А так як всі власні значення нульовий матриці дорівнюють нулю, то для власних значень? 1, ...,? n графа G дає нерівності
?? 0, (i=1, ...,? (G)).
Однак це суперечить припущенню a (G) gt; s. Тому (2.13) справедливо.
Рівність у (2.13) має місце, наприклад, для повних графів. Це і завершує доказ теореми 2.14.
Теорема 2.15. Нехай і означають числа власних значень графа G, які менше - 1, дорівнюють - 1 і більше - 1; ? * Означає найменшу власне значення, більше - 1. Нехай, далі, р=+ 1 і s=min (p,, r + 1), де r - індекс (максимальне власне значення) графа G, і
Якщо K (G) означає максимальне число вершин в повному підграфі графа G, то
(2.14)
Існують графи, для яких рівність у (2.14) досягається.
Доказ. Якщо G містить повний підграф з k вершинами, то виходять наступні нерівності:
Найбільше значення k, яке задовольняє цим нерівностям, дається виразом в правій частині нерівності (2.14). Рівність у (2.14) досягається, наприклад, для повних многодольний графів. Це і завершує доказ теореми 2.15.
А тепер обговоримо співвідношення між спектром графа і його хроматичним числом. Представляється дивним, що деяка інформація про хроматическом числі - величині, визначення якої в загальному випадку пов'язане зі значними труднощами, - може бути отримана на основі спектра. Для окремих спеціальних класів графів хроматичної число може бути навіть точно обчислено із спектру, наприклад для біхроматичним графів (див. Теорему 2.11), для регулярних графів ступеня n - 3, де n - число вершин. Однак у більшості випадків вдається отримати лиш...
