ти область зміни цих властивостей.
У даній главі міститься багато нерівностей і для різних чисельних характеристик. В усіх наведених нижче теоремах передбачається, що задані або спектр, або власні вектори матриці суміжності графа, або і те й інше разом і зазначений деякий клас, до якого належить граф. Якщо заданий спектр графа, передбачається, що відомий його характеристичний многочлен, і навпаки. У деяких випадках клас графів, до якого належить граф із заданим спектром, може бути визначений за допомогою спектра.
. 1 орграфа
Орграф G=(V, E) є пара множин, V- безліч вершин, Е- безліч дуг.
Будемо думати, що А - матриця суміжності,
РG (?) (2.1)
характеристичний многочлен, а - спектр графа G.
З самого початку будемо припускати, що в розглянутих орграфа допускаються кратні орієнтовані ребра і петлі. Перш ніж формулювати деякі теореми, відзначимо кілька простих результатів.
Кількість вершин орграфа G дорівнює ступеню n його характеристичного многочлена, т. е. числу власних значень орграфа G. Число орієнтованих петель одно сліду матриці суміжності - сумі? 1 + ... +? n, тобто величині - al. Якщо всі вершини орграфа G мають одне і те ж число петель, то характеристичний многочлен рн (?) Орграфа Н, получающегося з G в результаті видалення всіх його петель, повністю визначається многочленом РG (?): Якщо кожна вершина орграфа G має точно h орієнтованих петель, то і Рн (?)=РG (? + h).
Якщо G - орграф без петель, то жодна пара вершин орграфа G не вставлений двома протилежно орієнтованими ребрами тоді і тільки тоді, коли а2=0. Цей результат можна легко пояснити при розгляді всіх головних мінорів другого порядку матриці суміжності.
Безпосередньо слід: орграф G не містить контурів тоді і тільки тоді, коли всі коефіцієнти aI (i=1, ... ..., n) рівні 0, т. е. тоді і тільки тоді, коли спектр орграфа G не містить відмінних від нуля власних значень.
Кількість замкнутих маршрутів заданої довжини k в орграфе G може бути визначене за допомогою спектра орграфа G;
це число дорівнює tr Aк=
Застосовуючи теорему Гамільтона - Келі, з характеристичного многочлена (3.1) виводимо наступне співвідношення:
+ k + аiAn + k - 1} + + а nАк=О (к=0, 1, ...). (2.2)
З (2.2) можна отримати деяку інформацію щодо структури орграфа.
А тепер сформулюємо кілька теорем про цікловідной структурі орграфа G без кратних ребер. Окремі твердження наводяться надалі як окремі випадки цих теорем.
Довжина g (G) найкоротшого контуру в орграфе G (якщо тільки він існує) називається обхватом орграфа G. Якщо G не має контурів, то g (G)=+ ?. Очевидно, кожен лінійний орієнтований підграф орграфа G з менш ніж 2g вершинами, де g=g (G), необхідно є контуром.
Виводимо
=(i lt; 2g).
спектр граф теорія матриця
Таким обра?? ом, -ai є числом контурів довжини i, що містяться в G.
Теорема 2.1. Нехай G - орграф з характеристичним многочленом (2.1) і g (G)=g. Нехай, далі, i? min (2g - 1, n). Тоді число циклів довжини i, що містяться в G, одно - ai. Обхват g орграфа G дорівнює найменшому індексом i, для якого ai? 0.
Цей результат узагальнюється і на той випадок, коли можна визначити число контурів довжини i для деякого i gt; 2g - 1. Введемо нове поняття: d-обхват орграфа. Для довільного цілого числа d gt; 1 d-обхват gd (G) орграфа G визначається як довжина найкоротшого контуру серед тих контурів, довжини яких не діляться на d. Якщо ж таких контурів немає, то gd (G)=+ ?.
Теорема 2.2. Якщо G - орграф з характеристичним многочленом (2.1), g (G)=g, gd (G) - gd і, крім того, i? min (g + gd - 1, n), i0 (mod d), то число контурів довжини i, що містяться в G, одно -; d-обхват gd орграфа G дорівнює найменшому індексом, що не діляться на d, для якого at? 0.
Зауваження. Якщо g не ділиться на d, то, очевидно, gd=g і теорема 2.2 стверджує менше, ніж теорема 2.1. В іншому випадку, коли d є множником в g, зрозуміло, gd gt; g. Якщо ж gd gt; g + 1, теорема 2.2 дає нову інформацію, яку неможливо одержати з теореми 2.1.
Приклад. Нехай g=9, gg=15, gg=20. Теорема 2.1 дає числа контурів довжини з для с? 17. При d=9 теорема 2.2 дає ці числа додатково для с=19, 20, 21, 22, 23, а при d=3 - також і для с=25, 26, 28.
При d=2 отримуємо
Слідство. Довжина g2 найкоротшого контуру непарної довжини в G дорівнює індексу перше відмінного від нуля коефіцієнта серед a1 a3, а5, ...; число найкоротших контурів непарної довжини одно -аg2.
Доведення теореми 2.2. Нехай i? min (g + gd - 1, n), i 0 (mod d). Тоді кожен лінійний орієнтований підграф в G з i вершинами необхідно є контуром. Як і в наведених вище міркуваннях,
що і завершує доказ.
З слідства теореми 2.2 можна л...
