егко вивести таку теорему.
Теорема 2.3. Орграф G не має контурів непарної довжини тоді і тільки тоді, коли його характеристичний многочлен має вигляд
РG (?) =? n + а2? n - 2 + а4? n - 4 + =? p Q (? 2),
де Q - многочлен, а р=0 при парному n і р=1 в інших випадках.
Неважко довести також таку теорему.
Теорема 2.4. Сильно зв'язний орграф G з найбільшим власним значенням r не має контурів непарної довжини тоді і тільки тоді, коли -r також є власним значенням орграфа G.
Доказ. Якщо G не має контурів непарної довжини, то тоді згідно теоремі 2.3 - r також є власним значенням графа G.
Назад, якщо - r належить спектру орграфа G, то матриця суміжності орграфа G імпрімітівна. У цьому випадку індекс імпрімітівності n може бути лише парним числом і існує матриця перестановки Р така, що РАР - 1 має вигляд (1.1). А так як h - парне, то G, очевидно, не містить контурів непарної довжини, що й доводить теорему.
Орграф G назвемо циклічно k-долинним, якщо безліч його вершин може бути розбите на непорожні взаємно непересічні безлічі таким чином, що якщо (х, у) () - дуга орграфа G, то ji (mod k). Зауважимо, що циклічно k-дольний орграф є також циклічно l -дольним, якщо k ділиться на l. Матриця суміжності циклічно h-дольного орграфа має вигляд (1.1). Можна сформулювати таку теорему.
Теорема 2.5. Характеристичний многочлен циклічно k-дольного орграфа G має вигляд
РG (?) =? p Q (? 2), (2.3)
де Q - нормалізований многочлен, Q (0)? 0, а р - невід'ємне ціле число.
Якщо G -сильно зв'язний орграф, характеристичний многочлен якого має вигляд (2.3), то G - циклічно k-дольний орграф.
Наступна теорема взята безпосередньо з теорії матриць.
Теорема 2.6. Нехай d, ..., і, ..., - полустепені відповідно заходу і результату вершин орграфа G. Тоді для індексу r орграфа G справедливі наступні нерівності:
(2.4)
(2.5)
Якщо G сильно зв'язний, то рівність в правій або лівій частині нерівності (2.4) або (2.5) справедливо тоді і тільки тоді, коли всі величини d, ..., (або, ...,) дорівнюють.
Теорема 2.7 Для орграфа G з матрицею суміжності А справедливі наступні твердження:
1) існує многочлен Р (х) такий, що рівність
=P (A) (2.6)
має місце тоді і тільки тоді, коли граф G сильно зв'язний і регулярний;
єдиним многочленом Р (х) найменшій мірі, для якого виконується (2.6), є nS (x)/S (d), де (х- d) S (х) - мінімальний багаточлен матриці A, ad - ступінь орграфа G;
якщо Р (х) - многочлен найменшій мірі, для якого виконується (2.6), то ступінь орграфа G є найбільшим дійсним коренем рівняння Р (х)=n.
О=R (А)=(А - dI) S (A). (2.7)
Якщо про - нульовий вектор, то, оскільки R (A)? =О для всіх векторів? , З (2.7) випливає, що (А - dI) S (A)? =О,
тому S (A) =? u для деякого?.
Нехай (і,) - скалярний добуток векторів і і?. Якщо і і? такі, що то для кожного k і, таким чином,. Тому, т. Е.? =0.
Таким чином, для всіх таких, що (, і)=0; далі, Отже, тобто (2.6) виконується для
(2.8)
Це завершує доказ твердження 1; частина 2 випливає з того, що ступінь многочлена (2.8) менше ступеня мінімального многочлена матриці А. Щоб довести 3, зауважимо, що А - неотрицательная матриця, всі рядкові і стовпові суми якої рівні d. Таким чином, всі власні значення матриці А по абсолютною величиною не більше d. Корені многочлена Р (х) є власними значеннями матриці А, і, отже, для дійсного х gt; d Р (х) є зростаючою функцією по х. З (2.8) випливає, що Р (d)=n, і тому, оскільки Р (х) дійсний многочлен, Р (х) gt; n для х gt; d.
Це завершує доказ теореми 2.7.
Зауважимо, що многочлен (2.8) називається відповідним орграфа G, і будемо говорити, що орграф G відповідає многочлену (2.8).
Деякі нерегулярні графи можуть мати багаточлени з подібними властивостями.
. 2 ГРАФИ
Граф включає безліч вершин і безліч ребер, що є підмножиною декартова квадрата безлічі вершин (тобто кожне ребро з'єднує рівно дві вершини).
Якщо мультіграф Н має симметрическую матрицю суміжності А з парними значеннями діагональних елементів, то матрицю А можна інтерпретувати як матрицю суміжності неорієнтованого графа (мультиграфом) G. У цьому сенсі до графів можуть бути застосовані результати попереднього параграфа. Власні значення графа є дійсними числами, які можна впорядкувати таким чином, щоб послідовність? 1, ...,? n була спадною. У подальшому завжди буде використовуватися зазначену угоду.
Далі розглядаються тільки неорієнтовані графи без кратних ребер і петель.
