====== Матрицы и графы ====== === А.Э.Гутерман, Е.М.Крейнес === ---- **В этом учебном году спецкурс начнется дистанционно с использованием Zoom. Если Вы хотите участвовать, напишите на elena -dot- kreines @ gmail -dot- com, укажите, кто Вы, с какого курса, из какой группы, и кто Ваш научный руководитель, если есть**. ---- **Аннотация курса**: В центре внимания связь теории графов и теории матриц и их приложения. Среди прочего будет рассказано о матрицах над макс-алгебрами и их связи с графами. Будут сформулированы открытые проблемы для самостоятельного исследования, доступные студентам. В этом году курс рассчитан на студентов 2-4 курса. ---- == Тематическое содержание курса == - Графы. Основные понятия - Присоединенная матрица графа. Матрица инцидентности - Матрица Лапласа. Паросочетания - Ориентированные графы и их матрицы. Лемма о степени и ее следствия - Неразложимые матрицы. Эквивалентные определения - Вполне неразложимые матрицы - Примитивные матрицы. Теорема Виландта об экспоненте примитивной матрицы - Многомерная матричная экспонента и обобщения теоремы Виландта - Положительные матрицы и теорема Перрона - Спектральный радиус неотрицательных матриц и теорема Фробениуса - Регулярные и строго регулярные графы - Потоки в сетях - Потоки в сетях. Продолжение - Функция перманента и ее приложения - Скрамблинг индекс неотрицательных матриц - Латинские квадраты и прямоугольники. Частичные трансверсали - Графы и конечные автоматы. Гипотеза Черни ---- == Типовые контрольные задания == * Графы и операции над графами * Матрицы графа и их свойства * Неразложимые и вполне неразложимые матрицы * Примитивные матрицы * Теорема Перрона и теорема Фробениуса * Поиск перроновых векторов и чисел * Свойства перманента * Потоки в сетях * Скрамблинг-индекс * Трансверсали и частичные трансверсали * Графы и конечные автоматы ---- == Перечень учебной литературы == * 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.