Код: 316155

Назва:

Спектральна теорія графів

Анотація: Спектральна теорія графів - глибокий, сучасний розділ математики, який вивчає взаємозв'язок мiж спектральними та структурними властивостями графiв. Активний розвиток спектральної теорії графів пов'язаний з обширними можливостями застосувань у науці та техніці, наприклад, у хiмiї, фізиці, інформатиці, біології, географії, економіці, соціальних науках та ін. Базовими спектральними характеристика графа є значення власних чисел його матриці суміжності (або коефіцієнти характеристичного полінома) та власних векторів. Метою курсу є оволодіння фундаментальними поняттями спектральної теорії графів; дослідження спектрів відомих класів графів. Також під час вивчення курсу студенти ознайомляться із поняттям індексу графа, теоремою Сміта та теоремою Перрона-Фробеніуса, що застосовується для розв'язання проблеми ранжування, зокрема - при побудові алгоритму Google Page Rank.

Тип дисципліни: вибіркова

Рік навчання: 2

Семестр: 4 (весняний)

Кількість кредитів: 3

Форма контролю: залік

Викладач(і): ст. викл. , к. ф-м.н. Тимошкевич Л.М.

Результати навчання: Знати: поняття матриці суміжності графа, характеристичного полінома, спектру та індексу графа, методи обчислення характеристичного полінома, формули для вираження коефіцієнтів характеристичного поліному через структурні властивості графа, формулювання теореми Перрона-Фробеніуса, методи оцінки індексу графа, теорему Сміта, теорему парності для двочасткових графів.
Володiти: навичками та методами обчислення характеристичних поліномів графів, їх спектрів та індексів.
Вмiти: застосовувати свої знання до вiдповiдних математичних задач.


Спосіб навчання: дистанційний (аудиторний)

Необхідні обовязкові попередні й супутні модулі: лінійна алгебра, дискретна математика, математичний аналіз.

Зміст дисципліни: Основні поняття спектральної теорії графів. Властивості матриці суміжності, спектру та індексу графа. Невід'ємні, нерозкладні матриці, теорема Перрона-Фробеніуса. Методи обчислення характеристичного полінома: розклад за висячою вершиною, розклад за мостом. Спектри графів Динкіна. Методи оцінки індексу графа, теорему Сміта. Формули для вираження коефіцієнтів характеристичного поліному через структурні властивості графа. Теорему парності для двочасткових графів.


Рекомендована література: 1. Cvetkovic D. M., Doob M., Sachs H. Spectra of graphs. Theory and
Applications, - Johann Ambrosius Barth, Heidelberg. - 1995. - 447 pp.
2. Cvetkovic D., Doob M., Gutman I., Torgasev A. Recent Results in the Theory of Graph Spectra. - Annals of Discrete Mathematics. - vol. 36.- 1988. - 306 pp.
3. Biggs N. Algebraic Graph Theory. - Cambridge University
Press - 1974. - 216 pp.
4. Brouwer A.E., Haemers W.H. Spectra of Graphs Springer. - New York Dordrecht Heidelberg London. - 2012. - 245 pp.


Форми та методи навчання: лекції, практичні заняття, виконання індивідуальних завдань.

Методи й критерії оцінювання: рейтингова система оцінювання за 100-бальною шкалою: - робота в семестрі (індивідуальні завдання, контрольні роботи, домашні роботи) - 70 %; - залік - 30 %.

Мова навчання: українська