Графы, методы и приложения
Также рекомендовано для лучшего понимания: базовые знания теории вероятностей, статистики, дифференциальных уравнений и Python (numpy, pandas).
Алгебраические характеристики: матрица смежности, инцидентности, теорема о степени матрицы смежности.
Связность, необходимые и достаточные условия связности, деревья, остовные деревья, минимальные остовные деревья.
Жадные алгоритмы, дерево Хаффмана, алгоритмы построения минимальных остовных деревьев.
Матрица Лапласа, терема Киргхофа, теорема Кэли.
Двудольный граф, алгоритм проверки на двудольность, теорема Кэли для двудольного графа.
Алгоритмы поиска кратчайшего пути.
Планарные графы и многогранники, теоремы Эйлера, классификация Платоновых многогранников.
Вершинная и реберная связность, теорема Менгера, теорема о (k, l, d)-графе, алгоритм Траяна (поиска моста в графе).
Эйлеровы графы, критерий Эйлеровости, алгоритмы поиска Эйлерова цикла.
Гамильтоновы графы, теоремы Ори, Дирака, Бонди-Хватала, Уинтни.
Планарность и к-связность, теорема Понтрягина-Куратовского о подразбиениях, алгоритмы определения планарности.
Двойственный граф, теорема Штайница, двойственные многогранники, алгоритм построения двойственного графа, алгоритм Ли.
Потоки в графах, теорема о декомпозиции, теорема Форда-Фалкерсона, алгоритмы построения максимального потока.
Потоки минимальной цены, алгоритмы построения максимального потока минимальной цены.
Локальные и глобальные характеристики графов, центральности и связь между ними.
Свойства серий графов, сети Эрдёша-Реньи, Уоттса-Строгаца, Барабаши-Альберта.
Спектральные характеристики графов.
Биологические нейроны, одномерные и двумерные биффуркации.
Нейронные сети.
Tuzhilin M., Zhang D. Introduction to graph theory and basic algorithms //arXiv preprint arXiv: 2312.11543v2. – 2024.
Курс поделен на две части: теоретическую и практическую. Теоретическая часть начинается с базовой теории графов, включая доказательства классических теорем, таких как теорема Понтрягина-Куратовского, Штайница, Менгера и др. и базовые алгоритмы на графах (Белмана-Форда, Траяна, Флери, Аусладнера-Партера и т.д.), и заканчивается теорией графов в современной науке (Социальные сети, случайные графы, спектральные методы, спайковые нейронные сети и синхронизация). Каждая тема сопровождается примерами и различными приложениями теории графов в современной науке и жизни.
В практической части каждому студенту выдается преподавателем свой собственный граф для изучения и отработки всего пройденного в течение курса материала (например, нужно будет посчитать различные центральности у этого графа, использовать алгоритм для проверки является ли граф плоским и др.), а также в конце курса небольшой проект на языке Python по изучению синхронизации в спайковых нейросетях.