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