- Лемма
о рукопожатиях, следствия. Число ребер в полном графе.
- Матрица смежности, матрица Кирхгофа и ее свойства, список ребер,
матрица инцидентности. Связность. Связь матриц Кирхгофа, инцидентности
и смежности (две формулы).
- Теорема о двухсторонней оценке числа ребер в обыкновенном
графе. Условие на число ребер графа для связного графа.
- Спектр графа, регулярный граф. Дополнение графа.
- Центр графа.
- Ранг-полином. Ранг и коранг.
- Теорема о числе маршрутов определенной длины в графе.
- Теорема о числе ребер в произвольном графе.
- Теорема об алгебраических дополнениях в матрице
Кирхгофа. Число остовов.
- Кодировка дерева. Двоичная кодировка.
- Число остовов в полном графе (с доказательством).
- Дерево. Листья. Лес. Ярус. Ствол. Высота. Код Прюфера. Десятичная
кодировка.
- Сеть. Алгоритм Форда-Фалкерсона. Топологическая сортировка сети.
- Двудольный граф. Покрытие. Максимальное и наибольшее покрытие. Перманент.
- Два метода нахождения совершенного покрытия в двудольном графе. Необходимое
и достаточное условие равенства нулю перманента матрицы.
- Задача о назначениях. Венгерский алгоритм.
- Кратчайший путь в орграфе. Алгоритм Дейкстры. Алгоритм Флойда.
- Остов минимального веса. Два алгоритма решения задачи.
- Планарность. Плоский граф. Жорданова кривая. Подразбиение.
Гомеоморфность.
Теорема Понтрягина-Куратовского.
- Теорема
Эйлера о плоском графе.
- Раскраски. Хроматический индекс и хроматическое число. Оценки. Теорема
о редукции (с доказательством).
- Числа Стирлинга. Теорема Визинга. Теорема
Кенига.
- Связность. Разрез, мост.
- Центроид. Теорема Жордана о центре и центроиде.
- Основание графа. Сильно связный граф. Евклидов граф.
- Гамильтоновы графы. Теоремы Дирака. Теорема Оре.
Теорема Гуйя-Ури. Задача коммивояжера.
- Муравьиный алгоритм.
- Доминирующее множество. Число доминирования. Полностью зависимое и
полностью независимое множество вершин. Число вершинной независимости.
Реберная независимость. Теорема о связи независимости
и доминирования. Клики.
- Реберный граф. Число ребер (с доказательством). Собственные числа
реберного графа.
- Триангуляция. Теорема о максимальном планарном графе.
Число ребер максимально планарного графа.
|