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