Бакалавриат
2024/2025
Графы и матрицы
Статус:
Курс по выбору (Совместная программа по экономике НИУ ВШЭ и РЭШ)
Кто читает:
Факультет математики
Когда читается:
3-й курс, 3, 4 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Программа дисциплины
Аннотация
Теория графов являются одним из основных инструментов в приложениях математики к другим областям знания. Матрицы являются основным объектом изучения в линейной алгебре, где они появляются как формулы для описания линейных отображений и объекты, связанные с ними - детерминант, собственные числа, собственные вектора и т.д. имеют прозрачный геометрический смысл.С другой стороны есть много интересных матриц, связанных с графами. Возникает естественный вопрос, каков смысл перечисленных выше объектов в терминах графа, для которого определены эти матрицы. Ответ на этот вопрос неожиданно и элегантно связывает различные области математики. Курс будет посвящен обсуждению некоторых таких связей, элементарных по формулировке, но фундаментальных по их значению.
Цель освоения дисциплины
- Изучить как различные результаты из задачи теории графов (ориентированные графы, связности, электрические сети, филогенетические сети) могут быть переформулированы на языке линейной алгебры и теории матрицы. Научиться решать задачи этих теорий с помощью методов линейной алгебры и метрической геометрии.
Планируемые результаты обучения
- Освоить основы теории графов, электрических сетей и их основные приложения.
- Научиться находить связности графов (реберную, вершинную и алгебраическую).
- Научиться находить матрицу отклика и эффективных сопротивлений электрических сетей.
- Научиться находить матрицу отклика и эффективных сопротивлений электрических сетей. Научиться считать индекс Кирхгофа.
- Научиться считать индекс Кирхгофа.
- Научиться находить матрицу расстояний филогенетической сети.
- Научиться восстанавливать филогенетическую сеть по ее матрице расстояний.
Содержание учебной дисциплины
- Положительные матрицы и ориентированные графы.
- Связности.
- Электрические сети
- Метрические свойства электрических сетей.
- Геодезическое расстояние, его сравнение с расстоянием эффективных сопротивлений.
- Филогенетические сети, их метрические свойства.
- Восстановление филогенетической сети по ее матрице расстояний.
Элементы контроля
- ColloquiumОценка формируется на основании результатов коллоквиума и экзамен. Оба будут проводится устно, в билете будет зада- ча и теоретический материал-определения, формулировки, некоторые доказательства, возможны дополнительные вопросы. Так как темы курса для коллоквиума и экзамена независимы, веса этих оценок для формирования окончательной оценки будут одинаковыми. Пересдача возможна при наличии уважительной причины отсутствия на коллоквиуме/экзамене.
- ЭкзаменОценка формируется на основании результатов коллоквиума и экзамен. Оба будут проводится устно, в билете будет задача и теоретический материал-определения, формулировки, некоторые доказательства, возможны дополнительные вопросы. Так как темы курса для коллоквиума и экзамена независимы, веса этих оценок для формирования окончательной оценки будут одинаковыми. Пересдача возможна при наличии уважительной причины отсутствия на коллоквиуме/экзамене.
