justify"> Наступна теорема може бути доведена із залученням міркувань безпосередньо з теорії матриць.
Теорема 2.8. Якщо - середнє значення валентності, а r найбільше власне значення графа G, то
(2.9)
де рівність має місце тоді і тільки тоді, коли граф G регулярний.
Доказ. Оскільки, як відомо, матриця суміжності А=(aij) графа G ермітовим, то завдання знаходження максимального значення відносини Релея
(2.10)
(xi - довільні дійсні числа, не рівні одночасно нулю) має рішення R=r. Максимум досягається тоді і тільки тоді, коли xi (i=1, .... n) є координатами власного вектора матриці А, відповідного r.
Якщо в (2.10) покласти хi=1 (i=1, ..., n), то
де di=- валентність вершини i. Таким чином, - приватне значення відносини Релея, що доводить (2.9).
Для регулярних графів рівність у виразі (2.9) досягається, оскільки в цьому випадку найбільше власне значення графа G збігається з його ступенем. Зворотно, нехай справедливо рівність (2.9). Тоді значення xi=1 (i=1, ..., n) утворюють власний вектор матриці А, відповідний r, і з=r xi (i=1, ..., n) слід di== r (i=1..... n). Тому граф G регулярний. Це і завершує доказ теореми.
Застосовуючи до графів теорему 2.6 і використовуючи теорему 2.8, отримуємо нерівності
???
де і - відповідно мінімальне і максимальне значення валентностей в G.
Розглянемо ще кілька реченні, встановлюють зв'язок між коефіцієнтами аi многочлена РG (?) і деякими структурними властивостями графа G. Завдяки відсутності петель завжди а1=0. Число замкнутих маршрутів довжини 2 одно, очевидно, подвоєному числу ребер m, тому m= . Аналогічним чином може бути знайдена і формула для числа t трикутників. Виходить і. Коефіцієнт а4 дорівнює числу пар несуміжних ребер без подвоєного числа простих циклів С4 довжини 4, що містяться в G. Аналогічним чином знаходимо, що коефіцієнт а5 дорівнює подвоєному числу фігур, що складаються з трикутника і ребра (вони не мають спільних елементів) без подвоєного числа простих циклів С5 довжини 5.
Якщо G - ліс, то, очевидно, число 1-факторів дорівнює аn ; аn=(- 1) n/2, якщо є 1-фактор, і аn=0 в іншому випадку.
Для доказу наступної теореми потрібно проста лема, яку наведемо без доведення.
Лемма 2.1. Нехай? 1, ...,? K -дійсно числа і r, s (r - парне, r lt; s) - невід'ємні цілі числа. Тоді для а gt; 0 справедлива наступна імплікація:
Рівність з правого боку імплікації має місце тоді і тільки тоді, коли абсолютне значення точно одного з кванторів? 1, ...,? k одно а, а всі інші квантори дорівнюють нулю. З строгої нерівності з лівого боку слід суворе нерівність з правого боку імплікації.
Teopeма 2.9. Якщо [? 1, ...,? N] - спектр графа G, то з нерівності
(2.11) випливає, що G містить принаймні один трикутник.
Доказ. Згідно лемі (2.1) з (2.11) отримуємо
Тоді число трикутників
що і завершує доказ.
Так як, де т - число ребер графа G, то справедливо
Слідство. Якщо, то G містить принаймні один трикутник.
Наслідок теореми 2.2 може бути переформулювати для неорієнтованих графів наступним чином. Поряд з графом G розглянемо орграф Н, який має таку ж матрицю суміжності, як і G. Кожному найкоротшому простому циклу непарної довжини графа G відповідає в точності дві найкоротших циклу непарної довжини (з протилежного орієнтацією) орграфа Н, і, отже, число найкоротших простих циклів непарної довжини графа G дорівнює половині числа найкоротших контурів непарної довжини Н. Таким чином, доведена
Теорема 2.10. Нехай G - граф з характеристичним многочленом (2.1). Тоді довжина f найкоротшого простого циклу непарної довжини в G дорівнює індексу Перший не рівного нулю коефіцієнта серед а1, а3, а5, ... Число найкоротших простих циклів непарної довжини одно.
З цієї теореми негайно слід
Теорема 2.11. Граф, що містить, принаймні, одне ребро, є дводольним тоді і тільки тоді, коли його спектр, що розглядається як безліч точок дійсної осі, симетричний по відношенню до нульової точки.
Теорема 2.11 є однією з найбільш відомих теорем, що встановлюють очевидну тісний зв'язок між структурою та спектром графів. Мабуть, важливість цієї теореми вперше була відзначена в хімічній літературі Коулсон і Рашбрук (хіміки зазвичай називають її «теоремою парності»). Повністю ця теорема була доведена Захсен у формі теореми 2.3.
Цікаво відзначити, що теорема 2.11 неодноразово перевідкривається.
Характеризація зв'язкового двудольного графа можлива також за допомогою теореми 2.4.
Розглянемо задачу визначення обхвату графа. Як і у випадку орграфа, обхват графа G - це довжина найкоротшого з прост...
