позначається через Кт, n; K1, n називається зіркою. Повний k-дольний граф з n1 + n2 + ... + nk вершинами позначається.
Ліс - це граф без циклів, дерево - зв'язний ліс.
Доповненням графа G називається граф, у якого безліччю вершин є безліч вершин графа G і дві вершини суміжні в тоді і тільки тоді, коли вони не суміжні в графі G. Очевидно,=G. Граф, що не має жодного ребра, називається цілком незв'язним; його доповненням є повний граф.
Граф подразбіеній S (G) графа G виходить з G, якщо кожне ребро графа G замінити простий ланцюгом довжини 2, або, що рівносильно, помістити одну додаткову вершину на кожному ребрі графа G. Ясно, що S (G) є дводольним графом (Х, Y; U), де Х і Y безлічі відповідно вихідних і додаткових вершин.
Ребровим графом L (G) графа G називається граф, вершинами якого є ребра графа G, і дві вершини графа L (G) суміжні тоді і тільки тоді, коли відповідні їм ребра графа G мають спільну вершину.
Вершино-реберна матриця інціденцій R мультиграфом G=(Х, U) без петель визначається наступним чином. Нехай
Х={x1, x2, ..., XТ}, U={u1, u2, ..., Uт}
Тоді R=(bij) є nт-матрицею, де bij=1, якщо xi инцидентна ui (т. е. є кінцевий вершиною ребра ui), і bij=0 В іншому випадку. Реберно-вершинна матриця інціденцій - це матриця, транспонована до матриці R.
Матриця суміжності мультиграфом (мультіорграфа) G позначається через А=А (G). Матрицею ступенів (або валентностей) D мультиграфом називається діагональна матриця, у якої на (i, i) -Місця знаходиться значення ступеня? I вершини хi.
Для графа G вершинно-реберна матматриця інціденцій R, матриця ступенів D і матриці суміжності графів G, L (G) і S (G) зв'язані наступними співвідношеннями:
Наведені вище визначення та формули легко узагальнюються на довільні мультиграфом.
Матриця (0,1, - 1) -інціденцій V мультіорграфа G без петель з безліччю вершин x1, x2, ..., XТ і безліччю дуг u1, u2, ..., Uт визначається наступним чином: V=(? ij) -це nт-матриця, у якої
? ij=1, якщо uj; виходить з xi;
? ij=- 1, якщо і, заходить в xi;
? ij=О у всіх інших випадках.
У більшості випадків ми будемо користуватися наступними типовими позначеннями: n- число вершин графа, m - число його ребер або дуг; r - ступінь регулярного графа, а також його індекс; I - одинична матриця, In - одинична матриця порядку n; J - квадратна матриця, всі елементи якої рівні 1. Матриця, транспонована до матриці X, позначається через Хт, rk Х - ранг матриці Х.
Символ Кронекера? ij визначається наступним чином:? ij=1 і? ij=О, якщо j? i. Запис a/b означає, що а ділить b.
Спектр неорієнтованих мультиграфом складається з дійсних чисел. У цьому випадку власні значення? 1,? 2, ...,? N впорядковані таким чином, що? 1=r? ? 2,? ...? ? n
Інші теоретико-графові поняття і позначення будуть приводитися в тих місцях, де вони безпосередньо використовуються.
1.3 ДЕЯКІ ТЕОРЕМИ ТЕОРІЇ МАТРИЦЬ ТА ЇХ ЗАСТОСУВАННЯ ДО ДОСЛІДЖЕННЯ СПЕКТРІВ ГРАФІВ
Ряд фундаментальних властивостей спектрів графів (або, в більш загальному випадку, мультіорграфов) можна встановити на основі деяких теорем теорії матриць. У цьому параграфі представлені лише найбільш важливі матричні теореми, інші твердження з теорії матриць наводяться у вигляді лем в наступних розділах.
Безліч власних векторів, відповідних власному значенню? , Разом з нульовим вектором утворюють власний простір, відповідне?. Геометрична кратність власного значення?- Це розмірність відповідного йому власного простору. Алгебраїчної кратністю власного значення? називається його кратність як кореня відповідного характеристичного многочлена. Алгебраїчна кратність власного значення? завжди не менше за нього геометричній кратності.
Матриця Х називається симетричної, якщо ХТ=Х.
Теорема 1.1. Геометрична кратність власного значення симетричної матриці дорівнює його алгебраїчної кратності.
Надалі термін «кратність власного значення» означатиме алгебраїчну кратність. Матриця називається неотрицательной, якщо її елементами є невід'ємні числа.
Так як матриця суміжності мультиграфом (мультіорграфа) G неотрицательна, то спектр графа G має властивості спектра невід'ємних матриць. Для цих матриць справедливі наступні твердження.
Теорема 1.2. Ненегативна матриця завжди має невід'ємне власне значення r таке, що модулі всіх її власних значень не перевищують числа r. Цьому «максимальному» власному значенню відповідає власний вектор з невід'ємними координатами.
Вектор з позитивними (ненегативними) координатами надалі будемо називати позитивним (ненегативним) вектором. Матриця А називається разложимой, якщо є матриця перестановок Р така, що матриця Р - 1 АР має в...
