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

В этом учебном году спецкурс начнется дистанционно с использованием Zoom. Если Вы хотите участвовать, напишите на elena -dot- kreines @ gmail -dot- com, укажите, кто Вы, с какого курса, из какой группы, и кто Ваш научный руководитель, если есть.

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

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
• Ф. Харари, Теория графов, Либроком, 2009
• В.Н. Сачков, В.Е. Тараканов, Комбинаторика неотрицательных матриц, Научное издательство «ТВП», Москва, 2010
• В.Е. Тараканов, Комбинаторные задачи и (0,1)-матрицы, Москва «Наука», 1985
• Х. Минк, Перманенты, Москва «Мир», 1982
• Ландо С.К Введение в дискретную математику. М.: МЦНМО, 2012.
• Ландо С. К., Звонкин А. Графы на поверхностях и их приложения. М.: МЦНМО, 2010.
• P. Butkovič, Max-linear Systems: Theory and Algorithms, Springer Monographs in Mathematics, Springer-Verlag, 2010.
• J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, Graduate Texts in Mathematics v. 244, 2008
• О. Оре, Теория графов, Либроком, 2009

Курс проходит по понедельникам, 15.00 - 16.30.