Матрицы и графы
А.Э.Гутерман, Е.М.Крейнес
Аннотация курса: В центре внимания связь теории графов и теории матриц и их приложения. Среди прочего будет рассказано о матрицах над макс-алгебрами и их связи с графами. Будут сформулированы открытые проблемы для самостоятельного исследования, доступные студентам.
Тематическое содержание курса
- Определение графа и операции над графами
- Циклы и компоненты связности. Валентность
- Диаметр и охват графа. Вычисление
- Матрицы ассоциированные с графами. Применение
- Метрические характеристики графа
- Автоморфизмы графа
- Деревья. Остов минимального веса
- Матроиды и трансверсали
- Паросочетания и функция перманента
- Планарность графа и формула Эйлера
- Критерий планарности
- Эйлеровы и гамильтоновы обходы. Существование
- Графы и матрицы над макс-алгеброй
- Системы уравнений над макс-алгеброй и их приложения
- Методы решения систем линейных уравнений над макс-алгеброй
- Спектр линейного оператора над макс-алгеброй
- Теорема Перрона-Фробениуса для матриц над макс-алгебрами. Индекс цикличности. Теорема цикличности
Типовые контрольные задания
- Графы и операции над графами
- Диаметр и охват графа
- Метрические характеристики графа
- Поиск остова графа минимального веса
- Свойства перманента
- Критерий планарности графа
- Поиск эйлеровых и гамильтоновых обходов
- Свойства матриц над макс-алгеброй
- Поиск спектра линейного оператора над макс-алгеброй
- Теорема Перрона-Фробениуса для матриц над макс-алгебрами и ее приложения
Перечень учебной литературы
- 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