Матрицы и графы

Аннотация курса: В центре внимания связь теории графов и теории матриц и их приложения. Среди прочего будет рассказано о матрицах над макс-алгебрами и их связи с графами. Будут сформулированы открытые проблемы для самостоятельного исследования, доступные студентам.

1. Определение графа и операции над графами
2. Циклы и компоненты связности. Валентность
3. Диаметр и охват графа. Вычисление
4. Матрицы ассоциированные с графами. Применение
5. Метрические характеристики графа
6. Автоморфизмы графа
7. Деревья. Остов минимального веса
8. Матроиды и трансверсали
9. Паросочетания и функция перманента
10. Планарность графа и формула Эйлера
11. Критерий планарности
12. Эйлеровы и гамильтоновы обходы. Существование
13. Графы и матрицы над макс-алгеброй
14. Системы уравнений над макс-алгеброй и их приложения
15. Методы решения систем линейных уравнений над макс-алгеброй
16. Спектр линейного оператора над макс-алгеброй
17. Теорема Перрона-Фробениуса для матриц над макс-алгебрами. Индекс цикличности. Теорема цикличности

• Графы и операции над графами
• Диаметр и охват графа
• Метрические характеристики графа
• Поиск остова графа минимального веса
• Свойства перманента
• Критерий планарности графа
• Поиск эйлеровых и гамильтоновых обходов
• Свойства матриц над макс-алгеброй
• Поиск спектра линейного оператора над макс-алгеброй
• Теорема Перрона-Фробениуса для матриц над макс-алгебрами и ее приложения

• R.A. Brualdi, H.J. Ryser, Combinatorial matrix theory, Cambridge University Press, Cambridge, 1991
• J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, MacMillan Press ltd., London, 1976
• J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, Graduate Texts in Mathematics v. 244, 2008
• О. Оре, Теория графов, Либроком, 2009
• Ф. Харари, Теория графов, Либроком, 2009
• P. Butkovič, Max-linear Systems: Theory and Algorithms, Springer Monographs in Mathematics, Springer-Verlag, 2010
• В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич, Лекции по теории графов, Москва «Наука», 1990
• R.B. Bapat, Graphs and Matrices, Springer, 2012