числу ребер (дуг), що починаються в вершині хi, і закінчуються в вершині xj. Будемо позначати її А=(аij)=(а); іноді елемент aij буде зручно позначати через (A) ij. Наприклад,
X1 X2 X3 X4
рис1.1.
матриця суміжності графа, зображеного на рис.1.1, має вигляд
Для мультиграфом значення аij одно подвоєному числу петель (неорієнтованих), приєднаних до вершини xi.
Іноді зручно ототожнювати мультіграф G з мультіорграфом, матриця суміжності якого така ж, як і у графа G. Пояснимо це докладніше: будь неорієнтоване ребро, що з'єднує різні вершини, може розглядатися як пара дуг, що з'єднують ті ж самі вершини, але мають взаємно протилежні напрямки, і навпаки. Аналогічно, будь-які дві «орієнтовані петлі», приєднані до однієї і тієї ж вершині, можна замінити однією неориентированной петлею і навпаки.
мультиграфом (мультіорграфи) G=(X, U) і Н=(У, V) називаються ізоморфними, якщо існує (1, 1) -Відображення у =? (х) Х на Y таке, що для будь-якої пари вершин х laquo ;, x Х в Н є стільки ж ребер (дуг), що прямують з у =? (х ) в у =? (х ), скільки їх в G випливає з х в х raquo ;. Таке (1,1) -Відображення?, Що зберігає суміжність, називається ізоморфізмом. Очевидно, G і Н ізоморфні тоді і тільки тоді, коли їх вершини можна позначити (занумерувати) так, що відповідні матриці суміжності будуть рівні. Ясно, що ставлення ізоморфізму є відношенням еквівалентності, розбиває безліч всіх мультиграфом (мультіорграфов) на класи еквівалентності, які можна розглядати як абстрактні мультиграфом (мультіорграфи). Таким чином, ізоморфні мультиграфом (мультіорграфи) представляють один і той же абстрактний мультіграф (мультіорграф). Якщо G і Н ізоморфні, будемо писати GН, якщо ж G і Н розглядаються як абстрактні мультиграфом (мультіорграфи), то G=Н,
Визначник квадратної матриці А позначається через або det А.
Характеристичний многочлен матриці суміжності А графа G називається характеристичним многочленом графа G і позначається через PG (?). Власні значення матриці А (т. Е. Нулі многочлена) і спектр матриці А (що складається з власних значень) називаються відповідно власними значеннями і спектром графа G. Якщо? 1, ...,? N - власні значення графа G, то весь спектр позначається через Sp (G)=[? 1, ...,? n]. Ясно, що ізоморфні мультиграфом (мультіорграфи) мають один і той же спектр.
Власні значення матриці А можна визначити також як такі числа?, що задовольняють рівнянню Ах =? х, для яких є ненульовий вектор х. Кожен такий вектор х називається власним вектором матриці А (або графа G), відповідним власному значенню?.
Для графа G, зображеного на рис. 1.1, маємо
;
Спектр повного графа Кn на n? 1 вершинах складається з числа n - 1 і n - 1 чисел, рівних - 1.
Спектри графів увійшли в математичну літературу починаючи з фундаментальних робіт Л. М. Ліхтенбаума і Л. Коллацо і У. Сіноговіца. Але хіміки-теоретики почали цікавитися спектрами графів ще раніше, після появи роботи Е.Хюккеля в 1931р.
Перерахуємо причини проявляемого інтересу до спектрами графів.
. У квантової хімії скелети деяких ненасичених вуглеводнів представляються у вигляді графів. Енергетичні рівні електронів в такій молекулі насправді є власними значеннями відповідного графа. Стійкість молекули, а також інші важливі хімічні властивості тісно пов'язані зі спектром графа і відповідними власними векторами.
. У теорії графів і комбінаториці є багато теорем, при доказі яких застосовуються спектри графів, хоча вони і не зустрічаються у формулюванні теорем. Отже, використання спектрів графів відіграє роль вельми важливого методу, який називається спектральним.
. І нарешті, ще один аспект - обчислювальний: спектр - кінцева послідовність числових інваріантів. Виходячи з того, що цікавить нас (або її значна частина) міститься в спектрі, ми можемо замість графа використовувати його спектр, оскільки кінцеву послідовність чисел легко обробляти на обчислювальній машині. Останнє, зрозуміло, має сенс тільки тоді, коли існують ефективний метод обчислення спектрів для досить широкого класу графів і зворотний метод - «декодування» спектру, т. Е. Відновлення цікавлять нас властивостей графа з його спектру за допомогою алгебраїчних обчислень.
Слід зазначити, що хіміки та фізики зазвичай знають структуру графа і цікавляться його спектром, в той час як фахівці в області теорії графів і комбінаторики в більшості випадків припускають, що спектр графа відомий і при цьому задаються питанням про те, що можна сказати про структуру графа.
Ці питання спільно із загальним завданням теорії графів про знаходження і дослідженні інваріантів графа, а також деякі інші вельми цікаві факти, які стоять за цією темою, стимулювали дослідження взаємозв'язків між спектральними та структурними властивостями графів. Представляє також...
