афом, то вона симетрична і, отже, подібна діагональної матриці D, а саме D=(? Ij,? I).
Звернемося до відомій теоремі Гамільтона - Келі, яка стверджує, що всяка квадратна матpіца А задовольняє своєму характеристическому рівнянню, т. е. якщо f (?)=I, то f (А)=О.
Мінімальний многочлен m (?) матриці А - це многочлен m (?)=?? + ... Такий, що: (i) m (А)=О; (i) ступінь? многочлена m (?), що задовольняє умові (i), є мінімальною.
Крім того, справедливі наступні пропозиції.
. Многочлен m (?) Однозначно визначається матрицею А.
. Якщо F (?) - Многочлен, для якого F (А)=О, то m (?) | F (?) І, зокрема, m (?) | F (?).
. Нехай {? (1),? (2), ...,? (K)} - безліч різних власних значень матриці А і - алгебраїчна кратність власного значення. Тоді
,
і
причому 0 lt; (= 1, 2, ..., k).
. Якщо А подібна діагональної матриці, то всі рівні 1 і
. Нехай n - порядок матриці А. Якщо всі власні значення матриці А різні, то
Квадратна матриця, мінімальний і характеристичний многочлени якої тотожні, називається простою. Таким чином, пропозиція 5 стверджує, що квадратна матриця, всі власні значення якої різні, є простою.
А тепер опишемо деякі основні властивості спектра неорієнтованого мультиграфом. Для зручності викладу результати в більшості випадків будемо приводити без доказів, так як їх можна знайти у відповідних місцях в наступних розділах.
Матриця суміжності неорієнтованого мультиграфом G є симетричної і, отже, ермітової. Тому спектр графа G містить лише дійсні числа, які згідно теоремі 1.8 належать відрізку [-r, r].
Нехай [] - спектр мультиграфом. Так як подвоєне число петель одно сліду матриці суміжності, то у випадку мультиграфом без петель tr А=о, т. Е.=О. Число вершин, зрозуміло, одно n, і тог да число ребер m неорієнтованого графа без петель і кратних ребер визначається формулою.
Для індексу r зв'язного графа виконується нерівність. Нижня межа досягається у випадку, коли граф є простою ланцюгом, верхня при повному графі. Якщо припущення про зв'язності графа не береться до уваги, то для графа без ребер r=0, в іншому випадку r? 1,
Для найменшого власного значення q спектра графа G справедливо нерівність. Для графа без ребер q=0, в іншому випадку q?- 1. Це випливає з теореми 1.9, так як подграф К2 відповідає головній подматріцей, найменше власне значення якої дорівнює - 1. Значить, q=- 1 тоді і тільки тоді, коли всі компоненти графа G є повними графами. Нижня межа q=-r досягається у випадку, коли компонента графа G з найбільшим індексом є дводольним графом. Резюмує сказане вище наступна теорема, що описує фундаментальні спектральні властивості неорієнтовані графів.
Теорема 1.13. Для спектра [] неорієнтованого графа G справедливі наступні твердження:
- справжні числа і=0;
якщо граф G не містить ребер, то=0;
якщо граф G містить щонайменше одне ребро, то
(1.2)
? q?- 1 (1.3)
Верхня межа в (1.2) досягається тоді і тільки тоді, коли G - повний граф, в той час як нижня межа досяжна тоді і тільки тоді, коли компонентами графа G є графи К2 і, возможноК1. Верхня межа в (1.3) досягається тоді і тільки тоді, коли компонентами графа G є повні графи; нижня межа досягається тоді і тільки тоді, коли компонента графа G з максимальним індексом є дводольним графом. Якщо G - зв'язний граф, то нижня межа в (1.2) замінюється на 2соs; Рівність справедливо тоді і тільки тоді, коли G - проста ланцюг.
А тепер перерахуємо деякі спектральні властивості регулярних мультиграфом. Індекс мультиграфом дорівнює його ступеня. Легко бачити, що це твердження справедливе і для незв'язних мультиграфом, за винятком випадку, коли індекс не є простим власним значенням. Кратність індексу дорівнює числу компонент. Очевидно, що вектор, у якого всі координати рівні 1, є власним вектором, відповідним індексом.
Власні вектори, що відповідають іншим власним значенням, ортогональні цьому вектору, т. е. сума їх координат дорівнює О.
Подальші спектральні властивості графів можуть бути отримані в результаті використання того факту, що коефіцієнти характеристичного многочлена є цілими числами. Звідси випливає, що елементарні симметрические функції та суми kx ступенів (k натуральне число) власних значень також є цілими числами. Так як старший коефіцієнт характеристичного многочлена дорівнює 1, то раціональні власні значення (якщо тільки вони існують) є цілими числами.
РОЗДІЛ 2. ЗВ'ЯЗКУ МІЖ спектрального ВЛАСТИВОСТЯМИ ГРАФІВ
У цій главі описується лише частина відомих зв'язків між спектром і структурою графів. Відомо, що деякі структурні властивості не визначаються однозначно спектром, проте навіть в таких випадках можна, використовуючи спектр, уточни...
